Каков наилучший способ перебрать 2D-подмассив 2D-массива?

Question

Если у меня есть двумерный массив, то обходить весь массив, строку или столбец тривиально, используя циклы for.Однако иногда мне нужно пройти произвольный 2D-массив.

Отличным примером может служить судоку, в котором я могу сохранить всю сетку в 2D-массиве, но затем мне нужно проанализировать каждый отдельный блок из 9 квадратов.,В настоящее время я хотел бы сделать что-то вроде следующего:

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

Есть ли лучший способ перебора произвольных подмассивов, особенно когда они встречаются в регулярном порядке, таком как выше?

Answer 1

Производительность этой структуры цикла будет ужасной. Рассмотрим самый внутренний цикл:

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

C упорядочен по "строке-мажору", что означает, что доступ к block вызовет пропадание кэша на каждой итерации! Это потому, что к памяти не осуществляется непрерывный доступ.

Есть похожая проблема для grid. Ваш порядок вложенных циклов должен исправить i до изменения j, но вы получаете доступ к grid на j в качестве строки. Это снова не является непрерывным и будет кэшировать промах на каждой итерации.

Таким образом, практическое правило при работе с вложенными циклами и многомерными массивами заключается в размещении индексов цикла и индексов массива в одном и том же порядке. Для вашего кода это

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

Answer 2

Представьте, что у вас есть двумерный массив a[n][m].Чтобы зациклить подрешетку q x r, верхний правый угол которой находится в позиции x,y, используйте:

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

Для примера с судоку вы можете сделать это

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]

Answer 3

Ну, в случае с судоку вы не можете просто хранить 9 массивов 3х3.Тогда вам не нужно беспокоиться о вложенных массивах ... Если вы начнете переходить на гораздо более крупные сетки, чем в sudoku, вы также улучшите производительность кеша.

Игнорируя это, ваш код работает нормально.