¿Cuál es la mejor manera de recorrer una sub-matriz 2D de una matriz 2D? - C, matriz multidimensional

Si tengo una matriz 2D, es trivial recorrer toda la matriz, una fila o una columna usando bucles. Sin embargo, ocasionalmente, necesito atravesar una sub-matriz 2D arbitraria.

Un gran ejemplo sería sudoku en el que podría almacenar una cuadrícula completa en una matriz 2D, pero luego necesitaré analizar cada bloque individual de 9 cuadrados. Actualmente, haría algo como lo siguiente:

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.
}
}

¿Hay una mejor manera de iterar sobre subarreglas arbitrarias, especialmente cuando ocurren en un patrón regular como el anterior?

Respuestas

El rendimiento en esta estructura de bucle será horrible. Considere el bucle más interno:

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

C está ordenado por "fila mayor", lo que significa que el acceso block causará una falta de caché en cada iteración! Eso es porque la memoria no se accede de forma contigua.

Hay un problema similar para grid. Su orden de bucle anidado es arreglar i antes de variar j, pero estas accediendo grid en j como la fila. De nuevo, esto no es contiguo y se almacenará en caché en cada iteración.

Por lo tanto, una regla de oro para tratar con bucles anidados y matrices multidimensionales es colocar los índices de bucle y los índices de matriz en el mismo orden. Para tu código, que "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
}
}

Bueno, en el caso del sudoku no podrías simplementeAlmacena 9 matrices 3x3. Entonces no tiene que preocuparse por los arreglos de sub arrays ... Si comienza a mover grillas mucho más grandes que el sudoku, también mejoraría el rendimiento del caché de esta manera.

Ignorando eso, tu código de arriba funciona bien.

Imagina que tienes una matriz 2D a[n][m]. Para hacer un bucle en un subarray q x r cuya esquina superior derecha está en la posición x,y utilizar:

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

Para su ejemplo de sudoku, podría hacer esto

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]