optimized handling of 2D arrays

[Yos P.]

I'm using a 3D matrix, which is actually a three 2D arrays, in a
dinamic programing that runs many times. The 2D arrays are being filled
and sometimes deallocated in each run.
I need to optimize the accessing (filling up the 2D array) part, making
it as fast as possible, while allocating is less important since it is
done less often.
Any suggestion of the fastest way to do so are welcomed.

Here is the naive approach:
F = new int**[3];
for(int i=0; i<3; ++i) {
F = new int*[Rows];
for(int j=0; j < Rows; ++j) {
F[j]= new int[Cols];
}
}

for (int i = 1; i < Rows; ++i) {
for (int j = 1; j < Cols; ++j) {
F[0][j] = .... F[0][i-1][j] ....
F[1][j]...
...

Thanks.

 

[Michael DOUBEZ]

Yos P. a écrit :

I'm using a 3D matrix, which is actually a three 2D arrays, in a
dinamic programing that runs many times. The 2D arrays are being filled
and sometimes deallocated in each run.
I need to optimize the accessing (filling up the 2D array) part, making
it as fast as possible, while allocating is less important since it is
done less often.
Any suggestion of the fastest way to do so are welcomed.

Obviously, the fastest way is to use an existing matrix library (and
there are a *huge* amount of them - don't know why, perhaps it is like
the "hello world", it is the first library people think of with C++)
like blitz++ or newMat.

Overwise, an efficient approach (in your case) is to allocate the matrix
as a 1D array and then access elements by computing the index.

template <typename T>
class DumbMatrix
{
// Build array of N*M size for matrix NxM
DumbMatrix(int nbrow,int nbcol):N(nbrow),M(nbcol),matrix(N*M){}

// Constructor from initializer - If you have a fonction pattern
template<typename initializer>
DumbMatrix(int nbrow,int nbcol,initializer& matInit):N(nbrow),M(nbcol)
{
this->matrix.reserve(N*M);
for(int i=0;i<N;++i)
{
for(int(j=0;j<M;++j)
{
this->matrix.push_back(initializer(i,j));
}
}
}

//other...

//accessor
T& operator()(int i, int j){return matrix[i*M+j];

private:
int N; //number of row
int M; //number of column
std::vector<T> matrix;
};

If you want to keep the [][] notation there has been a thread about it
recently and you can find related code. Google for "My first project" in
subject for it.

There is also the FAQ that deals with general matrix design:
http://www.parashift.com/c++-faq-lite/input-output.html#faq-15.3

Michael

 

[Dizzy]

Yos P. a écrit :

Obviously, the fastest way is to use an existing matrix library (and
there are a *huge* amount of them - don't know why, perhaps it is like
the "hello world", it is the first library people think of with C++)
like blitz++ or newMat.

I would add to that list Boost.uBLAS which offers the quality of code one is
used with the Boost libraries in general. You will have many options for
many types of matrices (sparse or not, bounded or not, etc).