Sign in to follow this  

Iterating through separate matrices as if they're one

This topic is 3790 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Here's the variables in question: One matrix holds a bunch of variables, we'll call them T A second matrix holds a grid for the layout of the former matrix There is also a class of variables. A top coordinate called 1, a left coordinate called 2, a bottom coordinate called 3, and a right coordinate called 4. Here is how all the information is layed out:
 [T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T] 
 [T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T] 
 [T] [T] [T] [1] [T]|[T] [T] [1] [T] [T]|[T] [1] [T] [T] [T] 
 [T] [T] [2] [T] [4]|[2] [T] [T] [T] [4]|[2] [T] [4] [T] [T] 
 [T] [T] [T] [3] [T]|[T] [T] [3] [T] [T]|[T] [3] [T] [T] [T] 
 -------------------+-------------------+------------------- 
 [T] [T] [T] [1] [T]|[T] [T] [1] [T] [T]|[T] [1] [T] [T] [T] 
 [T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T] 
 [T] [T] [T] [2] [4]|[2] [T] [T] [T] [4]|[2] [T] [4] [T] [T] 
 [T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T] 
 [T] [T] [T] [3] [T]|[T] [T] [3] [T] [T]|[T] [3] [T] [T] [T] 
 -------------------+-------------------+------------------- 
 [T] [T] [T] [1] [T]|[T] [T] [1] [T] [T]|[T] [1] [T] [T] [T] 
 [T] [T] [2] [T] [4]|[2] [T] [T] [T] [4]|[2] [T] [4] [T] [T] 
 [T] [T] [T] [3] [T]|[T] [T] [3] [T] [T]|[T] [3] [T] [T] [T] 
 [T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T] 
 [T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T] 
Each [] represents a position in the first matrix. The -, |, and + are positions in the second matrix. The letter or number within each [] is the variables as described above. How this needs to be iterated through is the top line is read in order from left to right, then go to the next line and begin anew, all the way to the bottom right. The order in which this is read is of utmost importance, so you can't read one of the first matrices all at once before moving to the next one. Instead it needs to, for example, start in the matrix in the top left, read to the right until it reaches the border of the middle matrix, read the line through that etc to the right. Then start a new line and start over at the first matrix over to the third. Continue down until the bottom of the matrices are reached and transfer to the second row of matrices. The most obvious solution, make a mega-matrix and draw them all into the correct positions in the big one, then read through that, isn't an acceptable solution. The reading from top left to bottom right needs to be O(n). Additional storage in certain parts may be needed, but hopefully a sophisticated iterative approach is usable.

Share this post


Link to post
Share on other sites
... sorry, *what*???

Could you try showing the declarations of the original matrices, and a list of the elements you want to iterate over, in order?

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
... sorry, *what*???

Could you try showing the declarations of the original matrices, and a list of the elements you want to iterate over, in order?


Here's a smaller example that's easier to read:
I have 4 small matrices, 3x3 in size, each cell of which represented by []
So here is what one of the matrices will look like:


[ ] [ ] [ ]
[ ] [ ] [ ]
[ ] [ ] [ ]


I have 1 large matrix that stores the read order of the 4 smaller matrices. It looks like this:


|
1 | 2
----+----
3 | 4
|


Here's the whole thing together:


[ 1] [ 2] [ 3] | [ 4] [ 5] [ 6]
[ 7] [ 8] [ 9] | [10] [11] [12]
[13] [14] [15] | [16] [17] [18]
---------------+---------------
[19] [20] [21] | [22] [23] [24]
[25] [26] [27] | [28] [29] [30]
[31] [32] [33] | [34] [35] [36]


The numbers in the above example represent the order in which the cells should be read. That's the first challenge.

Got that? Now let's expand it a step further.

I have a set of variables that store positions in the 4 small matrices. There are two positions per matrix, a top left square and a bottom right square. Essentially, I'm drawing a smaller matrix within it. It may look something like this:


[ ] [ ] [ ] | [ ] [ ] [ ]
[ ] [TL] [ ] | [TL] [ ] [ ]
[ ] [ ] [BR] | [ ] [BR] [ ]
---------------+---------------
[ ] [TL] [ ] | [TL] [ ] [ ]
[ ] [ ] [BR] | [ ] [BR] [ ]
[ ] [ ] [ ] | [ ] [ ] [ ]


TL = Top Left
BR = Bottom Right

The function needs to iterate through the matrices in the top left to bottom right manner I explained first, but ONLY the squares within the top left and bottom right. Thus, putting everything together, here's the final iteration order:


[ ] [ ] [ ] | [ ] [ ] [ ]
[ ] [ 1] [ 2] | [ 3] [ 4] [ ]
[ ] [ 5] [ 6] | [ 7] [ 8] [ ]
---------------+---------------
[ ] [ 9] [10] | [11] [12] [ ]
[ ] [13] [14] | [15] [16] [ ]
[ ] [ ] [ ] | [ ] [ ] [ ]

Share this post


Link to post
Share on other sites
The simplest way is to group the four matrices into a single large matrix, then to clip that matrix to the specified "top left, bottom right" rectangle, and to iterate within the clipped matrix.

In order to keep performance, do the regrouping and clipping operations lazily (that is, you only do them when the user accesses an element). This should be fairly easy to do by writing two adapter classes.

Share this post


Link to post
Share on other sites
I just knocked this together quickly. It's not particularly refined, but it does what you want, as far as I can tell.


#include <algorithm>
#include <cstddef>
#include <cassert>
#include <iostream>

template<bool> struct ct_assert;
template<> struct ct_assert<true> { };
template<typename T, typename U> struct same_type { static const bool value = false; };
template<typename T> struct same_type<T, T> { static const bool value = true; };

template<typename T, std::size_t H, std::size_t W>
struct matrix_defs
{
typedef T element_type;
static const std::size_t height = H;
static const std::size_t width = W;
};

template<typename T, std::size_t H, std::size_t W>
class matrix : public matrix_defs<T, H, W>
{
private:
typedef matrix_defs<T, H, W> base;

public:
typedef typename base::element_type element_type;

matrix() { std::fill(a_, a_ + sizeof(a_) / sizeof(*a_), T(0)); }

// ...

const element_type &operator() (std::size_t i, std::size_t j) const
{
assert(i < base::height);
assert(j < base::width);
return a_[i * base::width + j];
}

element_type &operator() (std::size_t i, std::size_t j)
{
assert(i < base::height);
assert(j < base::width);
return a_[i * base::width + j];
}

private:
T a_[H * W];
};

template<typename MatrixType1, typename MatrixType2>
class matrix_hjoin_ref :
public matrix_defs
<
typename MatrixType1::element_type,
MatrixType1::height,
MatrixType1::width + MatrixType2::width
>
{
private:
typedef matrix_defs
<
typename MatrixType1::element_type,
MatrixType1::height,
MatrixType1::width + MatrixType2::width
>
base;

public:
typedef typename base::element_type element_type;

matrix_hjoin_ref(MatrixType1 &left, MatrixType2 &right) :
left_(&left),
right_(&right)
{
ct_assert<MatrixType1::height == MatrixType2::height>();
ct_assert<same_type<typename MatrixType1::element_type, typename MatrixType2::element_type>::value>();
}

const element_type &operator() (std::size_t i, std::size_t j) const
{
assert(i < base::height);
assert(j < base::width);
return (j < MatrixType1::width) ?
(*left_)(i, j) :
(*right_)(i, j - MatrixType1::width);
}

element_type &operator() (std::size_t i, std::size_t j)
{
assert(i < base::height);
assert(j < base::width);
return (j < MatrixType1::width) ?
(*left_)(i, j) :
(*right_)(i, j - MatrixType1::width);
}

private:
MatrixType1 *left_;
MatrixType2 *right_;
};

template<typename MatrixType1, typename MatrixType2>
class matrix_vjoin_ref :
public matrix_defs
<
typename MatrixType1::element_type,
MatrixType1::height + MatrixType2::height,
MatrixType1::width
>
{
private:
typedef matrix_defs
<
typename MatrixType1::element_type,
MatrixType1::height + MatrixType2::height,
MatrixType1::width
>
base;

public:
typedef typename base::element_type element_type;

matrix_vjoin_ref(MatrixType1 &top, MatrixType2 &bottom) :
top_(&top),
bottom_(&bottom)
{
ct_assert<MatrixType1::height == MatrixType2::height>();
ct_assert<same_type<typename MatrixType1::element_type, typename MatrixType2::element_type>::value>();
}

const element_type &operator() (std::size_t i, std::size_t j) const
{
assert(i < base::height);
assert(j < base::width);
return (i < MatrixType1::height) ?
(*top_)(i, j) :
(*bottom_)(i - MatrixType1::height, j);
}

element_type &operator() (std::size_t i, std::size_t j)
{
assert(i < base::height);
assert(j < base::width);
return (i < MatrixType1::height) ?
(*top_)(i, j) :
(*bottom_)(i - MatrixType1::height, j);
}

private:
MatrixType1 *top_;
MatrixType2 *bottom_;
};

template<typename MatrixType, std::size_t H, std::size_t W>
class matrix_window_ref : public matrix_defs<typename MatrixType::element_type, H, W>
{
private:
typedef matrix_defs<typename MatrixType::element_type, H, W> base;

public:
typedef typename MatrixType::element_type element_type;

matrix_window_ref(MatrixType &matrix, std::size_t i_offset, std::size_t j_offset) :
matrix_(&matrix),
i_offset_(i_offset),
j_offset_(j_offset)
{
}

const element_type &operator() (std::size_t i, std::size_t j) const
{
assert(i < base::height);
assert(j < base::width);
return (*matrix_)(i + i_offset_, j + j_offset_);
}

element_type &operator() (std::size_t i, std::size_t j)
{
assert(i < base::height);
assert(j < base::width);
return (*matrix_)(i + i_offset_, j + j_offset_);
}

private:
MatrixType *matrix_;
std::size_t i_offset_;
std::size_t j_offset_;
};

template<typename T, std::size_t H, std::size_t W>
std::ostream &operator<< (std::ostream &out, const matrix<T, H, W> &m)
{
for (std::size_t i = 0; i != H; ++i)
for (std::size_t j = 0; j != W; ++j)
out << m(i, j) << (j == W - 1 ? '\n' : '\t');

return out;
}

int main()
{
typedef matrix<double, 4, 4> mat4x4;
typedef matrix_hjoin_ref<mat4x4, mat4x4> row_type;
typedef matrix_vjoin_ref<row_type, row_type> row_stack;
typedef matrix_window_ref<row_stack, 6, 6> window6x6;

mat4x4 tl, tr, bl, br;

row_type top_row(tl, tr); // join tl and tr to make a 4x8
row_type bottom_row(bl, br); // join bl and br to make a 4x8
row_stack both_rows(top_row, bottom_row); // an 8x8
window6x6 middle6x6(both_rows, 1, 1); // central 6x6 sub-matrix

double count = 0;

for (std::size_t i = 0; i != window6x6::height; ++i)
for (std::size_t j = 0; j != window6x6::width; ++j)
middle6x6(i, j) = count++;

std::cout << tl << '\n';
std::cout << tr << '\n';
std::cout << bl << '\n';
std::cout << br << '\n';

return 0;
}




It doesn't implement ToohrVyk's laziness idea, but if you're only iterating over the elements once, it may not be worth it, anyway.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
The simplest way is to group the four matrices into a single large matrix, then to clip that matrix to the specified "top left, bottom right" rectangle, and to iterate within the clipped matrix.

In order to keep performance, do the regrouping and clipping operations lazily (that is, you only do them when the user accesses an element). This should be fairly easy to do by writing two adapter classes.


Quote:
Original post by Montblanty
The most obvious solution, make a mega-matrix and draw them all into the correct positions in the big one, then read through that, isn't an acceptable solution. The reading from top left to bottom right needs to be O(n).


The matrices will be accessed several times a second so I can't do the easy inefficient memory-wastey solution.

The way I see this working is a custom set of iterative variables that ignore the actual array positions, then write some functionality to compensate for that

Share this post


Link to post
Share on other sites
Quote:
Original post by Montblanty
Quote:
Original post by ToohrVyk
The simplest way is to group the four matrices into a single large matrix, then to clip that matrix to the specified "top left, bottom right" rectangle, and to iterate within the clipped matrix.

In order to keep performance, do the regrouping and clipping operations lazily (that is, you only do them when the user accesses an element). This should be fairly easy to do by writing two adapter classes.


Quote:
Original post by Montblanty
The most obvious solution, make a mega-matrix and draw them all into the correct positions in the big one, then read through that, isn't an acceptable solution. The reading from top left to bottom right needs to be O(n).


The matrices will be accessed several times a second so I can't do the easy inefficient memory-wastey solution.


Um, doing it by "wasting" memory is exactly the approach you should be taking if speed is a concern. "Creating a custom set of iterative variables" (I assume you mean, a custom iterator class) would be what you do if you *don't* have lots of memory, and speed is not a concern.

Keep in mind that once you've built the larger array, you could *keep* it somewhere.

Share this post


Link to post
Share on other sites

This topic is 3790 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this