Initializing a generic cost matrix

[Gaminic]

Hey guys,

I'm working on a piece of code where there are several cost matrices, with different cost types. To reduce code bloat/inconsistencies, I made the a generic matrix:

template <typename T>
struct Matrix {
	const SIZE S;
	vector<T> c;

	Matrix(SIZE _S) : S(_S) {}

	inline T operator()(INDEX i, INDEX j) const { return c[i * S + j]; }
};

Different classes have their own cost matrix. The problem now is initializing the data. Since the Matrix class is in some global/namespace scope, it can't directly access the cost function needed to generate the data. Most of those functions look like this:

SOME_TYPE cost(INDEX i, INDEX j) { return some_value_based_on_i_and_j; }

I could set values from outside by accessing the c vector directly (keep it public) or by providing an operator() that returns a T&. However, the first is messy and the second just seems wrong entirely, since for most of the matrices the data will be set once and never changed.

Logically there must be some way to pass a CostFunction to the initializer, but I'm not sure what the options (functors? lambdas?) are, let alone what the best option is. The code uses transformations of cost matrix regularly so new cost matrices are constructed quite often.

Can someone provide me with some ways of doing this? Speed is a must, flexibility is optional; most use cases are very straightforward.

[LB]

You could pass the cost function to the constructor, could you not? Look up std::function if you can use C++11, or consider boost::function in C++03. Otherwise you will have to use function pointers which are messy and slightly limited.

[JLBorges]

This thread could be of interest: http://www.cplusplus.com/forum/general/121300/

[Gaminic]

@ L B: I think that's exactly what I'm looking for: a modern way of passing functions. Thanks for the suggestion, I'll give it a shot!

Is this the correct usage? (S being 'row size', c being the vector for the linearized S x S matrix)

 // Matrix constructor
Matrix(SIZE _S, std::function<T(INDEX, INDEX)> calc) : S(_S), c(_S * _S) {
for (INDEX i = 0; i < S; ++i) { 
    for (INDEX j = 0; j < S; ++j) {
        c(i, j) = calc(i, j);
    }
}

@JLBorges: That is a massively impressive trick, but if I understand correctly that would only work for a size set at compile time, no? I'm hoping to keep my code flexible. (I could work around it, but I don't think there's a clean/safe solution.)

Also, my explanation was unclear: the shape c(i, j) = CostFunction(i, j) is predictable, but different instances of the cost matrix will have a different ConstFunction attached to it (eg. one with c(i, j) = i + j, another with c(i, j) = i * j; the functions are quite complex, but the only input is i and j). I think I can expand the template with the std::function suggested by L B and have them generated at compile time (barring the "flexible size")? I'm very new to generic programming (and C++11), so I'm not sure what restrictions this method would put on the shape of my CostFunctions.

[JLBorges]

> I think I can expand the template with the std::function suggested by L B
> and have them generated at compile time

No. We need a constexpr function for that.

For instance (sans the "flexible size"):

#include <iostream>

template < std::size_t NROWS, std::size_t NCOLS, typename FUNCTION >
struct cost_matrix
{
    struct row
    {
        constexpr explicit row( std::size_t r ) : i(r) {}

        constexpr std::size_t operator[] ( std::size_t j ) const
        { return i<NROWS && j<NCOLS ? FUNCTION{}(i,j) : throw "std::out_of_range" ; }

        const std::size_t i ;
    };

    constexpr row operator[] ( std::size_t i ) const { return row(i) ; }
};

struct fn_one
{
    constexpr std::size_t operator() ( std::size_t i, std::size_t j ) const
    { return i*i + j ; }
};

struct fn_two
{
    constexpr std::size_t operator() ( std::size_t i, std::size_t j ) const
    { return 2*i + 3*j ; }
};

int main()
{
    cost_matrix< 3, 4, fn_one > cm1 ;
    cost_matrix< 5, 5, fn_two > cm2 ;

    int test[ cm1[2][1] * cm2[2][2] ] ;
    std::cout << sizeof(test) << '\n' ;
}

http://coliru.stacked-crooked.com/a/9bdcf8659a5de8aa

[Gaminic]

Thanks for the code example! I'm pretty sure I can adapt this to my problem now.

I have a few more questions, but they're entirely out of interest, so please don't feel obligated to put extra time into this topic.

1) I understand you're using objects as functions through their operator(), but what is this syntax exactly?
FUNCTION{}(i,j)
Am I correct in saying that it's telling the compiler that FUNCTION is a class, not a function? It looks like it would construct a temporary object and then call its operator(). But this would be evaluated at compile time, so why does it allow objects anyway?

2) How does this work behind the scenes? The compiler doesn't know which of the elements will be used, so I imagine it must generate and store all elements. It seems pretty risky to support this kind of "implicit storage". If some of these matrices are only used from time to time, would it be better to use a more classical storage model so the data can be freed when it's not longer needed?

(All this under the assumption that this does indeed perform the calculations at compile time; or does it only bind the shape FUNCTION(i, j) to c(i, j) and perform calculate "on demand"/at runtime?)

[JLBorges]

> It looks like it would construct a temporary object and then call its operator().

Yes. FUNCTION{} is an anonymous value-initialized object of type FUNCTION (must be DefaultConstructible)
http://en.cppreference.com/w/cpp/language/value_initialization


> But this would be evaluated at compile time, so why does it allow objects anyway?

Compile-time evaluation of an object is possible if its constructor (implicit or explicit) is a constexpr constructor.
http://en.cppreference.com/w/cpp/language/constexpr


> How does this work behind the scenes? The compiler doesn't know which of the elements will be used,
> so I imagine it must generate and store all elements.

Where the indices used are compile-time constants, the compiler knows which elements are being used.

cost_matrix<> is a chimerical matrix; no values are actually stored in it.

int main()
{
    cost_matrix< 10000, 20000, fn_one > cm ;
    std::cout << sizeof(cm) << '\n' ; // 1 (typical, because an object can't have a size of zero)
}

http://coliru.stacked-crooked.com/a/7cb5fc7a7de12024

However, it gives the illusion of a matrix; cm[i][j] is supported.
The value is computed on the fly (call fn_one(i,j)).
If i and j are compile time constants within range, the result of the call is evaluated at compile-time.

[Gaminic]

Thanks for the info!

> Where the indices used are compile-time constants, the compiler knows which elements are being used.
> cost_matrix<> is a chimerical matrix; no values are actually stored in it.
>If i and j are compile time constants within range, the result of the call is evaluated at compile-time.

So if indeces are known/constants, the value is computed at compile-time? That means they must be stored somewhere, no?


> [...]The value is computed on the fly (call fn_one(i,j)).

So, if my access calls are random/unpredictable (e.g. literally cm[rand()%n][rand()%n]), the function fn_one(i, j) has to be called on every lookup? If the lookup matrices are extensively used, this method will cause a performance hit, wouldn't it?

[JLBorges]

> That means they must be stored somewhere, no?

No. In http://coliru.stacked-crooked.com/a/9bdcf8659a5de8aa
cm1[2][1] * cm2[2][2] is evaluated at compile time (50 is substuted for that expression).



> So, if my access calls are random/unpredictable (e.g. literally cm[rand()%n][rand()%n]),
> the function fn_one(i, j) has to be called on every lookup? If the lookup matrices are extensively used,
> this method will cause a performance hit, wouldn't it?

Yes. They would not be constexpr and have to be evaluated at run-time. In this case (the cost matrix is not made up of compile-time constants), the std::function<> approach - compute the values once, and store the results in an actual matrix) would be appropriate.

[Gaminic]

Alright, I think I now have a basic understanding of the differences between both methods. Thank you for taking the time to explain!