What is the best way to loop through a 2D sub-array of a 2D array?

If I have a 2D array, it is trivial to loop through the entire array, a row or a column by using for loops. However, occasionally, I need to traverse an arbitrary 2D sub-array.

A great example would be sudoku in which I might store an entire grid in a 2D array but then need to analyse each individual block of 9 squares. Currently, I would do something like the following:

for(i = 0; i < 9; i += 3) {
    for(j = 0; j < 9; j += 3) {
        for(k = 0; k < 3; k++) {
            for(m = 0; m < 3; m++) {
                block[m][k] == grid[j + m][i + k];
            }
开发者_运维知识库        }

        //At this point in each iteration of i/j we will have a 2D array in block 
        //which we can then iterate over using more for loops.
    }
}

Is there a better way to iterate over arbitrary sub-arrays especially when they occur in a regular pattern such as above?

---

The performance on this loop structure will be horrendous. Consider the inner most loop:

        for(m = 0; m < 3; m++) {
            block[m][k] == grid[j + m][i + k];
        }

C is "row-major" ordered, which means that accessing block will cause a cache miss on each iteration! That's because the memory is not accessed contiguously.

There's a similar issue for grid. Your nested loop order is to fix i before varying j, yet you are accessing grid on j as the row. This again is not contiguous and will cache miss on every iteration.

So a rule of thumb for when dealing with nested loops and multidimensional arrays is to place the loop indices and array indices in the same order. For your code, that's

for(j = 0; j < 9; j += 3) {
    for(m = 0; m < 3; m++) {
        for(i = 0; i < 9; i += 3) {
            for(k = 0; k < 3; k++) {
                block[m][k] == grid[j + m][i + k];
            }
        }
        // make sure you access everything so that order doesn't change
        // your program's semantics
    }
}

---

Well in the case of sudoku couldn't you just store 9 3x3 arrays. Then you don't need to bother with sub arrays... If you start moving to much larger grids than sudoku you would improve cache performance this way as well.

Ignoring that, your code above works fine.

---

Imagine you have a 2D array a[n][m]. In order to loop a subarray q x r whose upper right corner is at position x,y use:

for(int i = x; i < n && i < x + q; ++i)
   for(int j = y; j < m && j < y + r; ++j)
   {
      ///
   }

For your sudoku example, you could do this

for(int i = 0; i<3; ++i)
    for(int j = 0; j < 3; ++j)
       for(int locali = 0; locali < 3; ++locali)
           for(int localj = 0; localkj <3; ++localj)
               //the locali,localj element of the bigger i,j 3X3 square is 
               a[3*i + locali][3*j+localj]