2

I have a grid represented with a flat vector, that is:

-------------
| 6 | 7 | 8 |
-------------
| 3 | 4 | 5 |
-------------
| 0 | 1 | 2 |
-------------

I access the elements with the indices from 0 to grid.size()-1. I want to implement the Fast Sweeping Method. The main purpose of that method is that it does sweeps, that is, grid traversals in specific directions. For the 2D case:

Sweep 1: Right-top

for [row = 0 : nrows-1]
    for [col = 0 : ncols-1] --> Result: 0 1 2 3 4 5 6 7 8

Sweep 2: Left-top

for [row = 0 : nrows-1]
    for [col = ncols-1 : 0] --> Result: 2 1 0 5 4 3 8 7 6

Sweep 3: Right-bottom

for [row = nrows-1 : 0]
    for [col = 0 : ncols-1] --> Result: 6 7 8 3 4 5 0 1 2

Sweep 4: Left-bottom

for [row = nrows-1 : 0]
    for [col = ncols-1 : 0] --> Result: 8 7 6 5 4 3 2 1 0

And then computing idx = row*ncols + col.

This implementation is straightforward and its generalization to n dimensions as well, when just nesting for loops. However, I am working on a n-dimensional implementation and I am trying to generalize it in just 2 loops: 

while (keepSweeping)
    ++sweep;
    for (idx = init, idx == end, idx += inc)
         // Traverse the grid

Computing init, end and inc is being really challenging. Also inc depends on ncols and changes dynamically. For instance, for sweep 2 inc = -1, but every ncols times inc = -1 + 2*ncols, so I achieve to go from 0 to 5.

Any help on how to do it? I am focusing firstly on the 2D case.

EDIT: I saw these threads http://www.cplusplus.com/forum/beginner/68434/ variable nested for loops that suggest to implement the loops recursively. Since I am looking for maximum performance, do you think that is a good idea?

Thank you!

Community
  • 1
  • 1
Javi
  • 3,440
  • 5
  • 29
  • 43
  • _Since I am looking for maximum performance, do you think that is a good idea?_ Depends on the language and the way you write your recursion. But worrying about this only makes sense once you've established with tests that this is going to be a bottleneck. – biziclop Mar 05 '15 at 15:04
  • I am coding in C++, and assume a recursion as those posts (I cannot think on other way). I agree with looking for the bottleneck and do not worry about that... but I am going to do benchmarks against other similar methods that are already generalized (they do not have those sweeps) and thus I would be introduced a cost in the algorithm which is not because design but because implementation. – Javi Mar 05 '15 at 15:07
  • If I understand correctly, you're trying to find a generic algorithm to deal with the various sweeps you described? What I don't understand is why you say you will compute `idx = nrows*ncols + col`. Is `col` acting like an iterator here? (In your example, nrows=3, ncols=3, so we have `idx=9+col` and I guess `col` is the only variable) – Grégoire C Mar 05 '15 at 15:13
  • I want to find a generic algorithm that gives me the indices in the order described for each sweep. And yes, for the example `col` is acting like an inner loop iterator (and `row` is the iterator of the outter loop). Regarding the index computation, there is an error, it is `idx = row*ncols + col`. I editted it, thanks for catching that. – Javi Mar 05 '15 at 15:25
  • Why do you consider that you can sweep *n-dimensional* grids with just *2* loops? I think that you need *n* loops for a *n* dimensional grid, that is, you will have one loop per dimension of the grid and inside each loop, a test for the direction to choose. – Grégoire C Mar 05 '15 at 16:04
  • I guess it is possible, but I'm not sure. A used a flat array because I want to avoid nested loops so that the exact same code works for 2 or 6 dimensions. – Javi Mar 05 '15 at 16:11
  • I don't know if this helps but in reality you've only got two sweeps, the others are just the same two reversed. But as you increase the number of dimensions, the number of different sweeps will rise too. – biziclop Mar 06 '15 at 16:40
  • The number or `sweeps` is `2^n` where `n` is the number of dimensions. – Javi Mar 06 '15 at 19:15

1 Answers1

1

Ok here is my try to answer your problem in the 2D case, using only one loop. Hopefully this is not too far from what you are looking for:

// ****** INITIALIZATION ******
int ncols = 4; // number of columns
int nrows = 3; // number of rows
boolean right = true; // direction of sweep on horizontal axis
boolean top = true; // direction of sweep on vertical axis
int counter = 0; // number of positions explored
if (right) {
    colIterator = 0;
}
else {
    colIterator = ncols - 1;
}
if (top) {
    rowIterator = 0;
}
else {
    rowIterator = nrows - 1;
}

// ****** CONTINUATION CONDITION ******
while (counter != nrows*ncols) {

    // ****** DO SOMETHING ******
    System.out.println(rowIterator*ncols + colIterator);

    // ****** PROGRESSION PHASE ******
    counter++;
    // Have we completed a row?
    if ((counter % ncols) == 0) {
        if (top) {
            // We have to move up
            rowIterator++;
        }
        else {
            // we have to move down
            rowIterator--;
        }
        if (right) {
            colIterator = 0;
        }
        else {
            colIterator = ncols - 1;
        }
    }
    else {
        // We have not yet completed a row
        if (right) {
            // We have to move right
            colIterator++;
        }
        else {
            // or left
            colIterator--;
        }
    }
}

Note: this code has been tested with Groovy.

A bit of upper-level explanation: it works with one loop because in 2D, we can find a global metric of the advancement of the work we want to do (here this metric is the counter variable) and can use the metric to determine, at each iteration of the loop, if we have completed a row (or not) by using the modulus operation.

I don't think it is mathematically possible to generalize this algorithm to upper dimensions (i.e. above 2) with only one loop, because there will be no mathematical operator that will tell us if we have finished part of the work on one given dimension and should start working on the outter dimensions (here, the modulus tells us that we have to modify the rowIterator because we have reached a border of the grid, but in dimension 3 or above 3, what would be the mathematical operator to use?).

Good luck and please post what you find, it's an interesting challenge.

Grégoire C
  • 1,361
  • 1
  • 13
  • 32
  • Thank you for your reply. It seems nice but the management of `top` and `right` is missing, which is not obvious either. So far I have solved it by nesting loops and limiting the maximum number of dimensions. It is not a nice solution but it seems that this problem is more complex than I though. – Javi Mar 09 '15 at 07:13
  • What do you mean by "management of `top` and `right`"? Do you want to make all sweeps automatically, without changing the booleans "by hand"? – Grégoire C Mar 09 '15 at 08:30
  • Exactly. In my case I have to keep sweeping until a termination condition is achieved. In any case, I already solved that mandgement to n-dimensions, but no the indexing without using nested loops. – Javi Mar 09 '15 at 09:50