I'm looking for an algorithm idea on how to traverse a matrix using a linear index while avoiding row/column based traversals to get a more diverse distribution of values.
To understand this better, think of an image that's split in blocks, with
N rows &
M columns. I need to process each image block sequentially (from
NxM) but I don't know in advance what the processing time will be for each block ( blocks that are close together tend to have a similar processing time, with small variations).
During processing, I need to be able to estimate as best as possible the remaining processing time based on the number of blocks that have already been processed & their associated processing time. For this reason, traversing the blocks by columns or by rows will not give an accurate estimation so I need to find another way of traversing the matrix that would pick values from different zones of the image.
It's also important to be able to determine the blocks processing order based on a linear index (from 1 to NxM), without calculating them in advance. The algorithm that returns the
column corresponding to the linear index should be as fast as possible.
Shorter version of the question
For a liner index named
idx, I need to get a corresponding
column pair from a matrix with
N rows &
M columns while avoiding a row/column based traversal.
NxM, the algorithm would return a
[row, column] pair so that all the rows & columns combinations are returned exactly once.
(the values in the matrix represent the linear index's value that's associated with that row&column position)
1 17 13 9 5 6 2 18 14 10 11 7 3 19 15 16 12 8 4 20
The above example is for a diagonal traversal that would produce a better distribution of values that a row/column based traversal.
Another possible solution would be to split the matrix into smaller blocks & traverse those blocks in rows/columns. For example a
4x5 matrix could be virtually split into
2x2 blocks and those smaller blocks could be traversed by rows or columns (e.g.
idx(1) = block1[1, 1],
idx(2) = block2[1, 1], etc.). The traversal would look something like this:
1 13 | 3 15 | 5 7 17 | 9 18 | 11 ------+-------+--- 2 14 | 4 16 | 6 8 19 | 10 20 | 12
Any other traversal ideas are welcomed.
Ideally, this algorithm would translate to a math formula to calculate the row & column based on the linear index, possibly with a few conditions (
IF statements) to compensate for missing values, etc.