有效地迭代陣列和行主要順序

C 中的陣列可以看作是一塊連續的記憶體。更準確地說，陣列的最後一個維度是連續的部分。我們稱之為行主要訂單。瞭解這一點以及快取故障在訪問未快取資料時將完整快取行載入到快取中以防止後續快取故障的事實，我們可以看到為什麼使用 array[0][0] 訪問維度 10000x10000 的陣列可能會在快取中載入 array[0][1]，但是訪問 array[1][0] 是正確的之後會產生第二個快取故障，因為它距離 array[0][0] 只有 4 個位元組，因此肯定不會在同一個快取線上。這就是為什麼像這樣迭代是低效的：

#define ARRLEN 10000
int array[ARRLEN][ARRLEN];

size_t i, j;
for (i = 0; i < ARRLEN; ++i)
{
    for(j = 0; j < ARRLEN; ++j)
    {
        array[j][i] = 0;
    }
}

像這樣迭代更有效：

#define ARRLEN 10000
int array[ARRLEN][ARRLEN];

size_t i, j;
for (i = 0; i < ARRLEN; ++i)
{
    for(j = 0; j < ARRLEN; ++j)
    {
        array[i][j] = 0;
    }
}

同樣，這就是為什麼在處理具有一維和多個索引的陣列時（為了簡單起見，使用索引 i 和 j，這裡說 2 維）重要的是迭代遍歷陣列，如下所示：

#define DIM_X 10
#define DIM_Y 20

int array[DIM_X*DIM_Y];

size_t i, j;
for (i = 0; i < DIM_X; ++i)
{
    for(j = 0; j < DIM_Y; ++j)
    {
        array[i*DIM_Y+j] = 0;
    }
}

或者使用 3 維和索引 i，j 和 k：

#define DIM_X 10
#define DIM_Y 20
#define DIM_Z 30

int array[DIM_X*DIM_Y*DIM_Z];

size_t i, j, k;
for (i = 0; i < DIM_X; ++i)
{
    for(j = 0; j < DIM_Y; ++j)
    {
        for (k = 0; k < DIM_Z; ++k)
        {
            array[i*DIM_Y*DIM_Z+j*DIM_Z+k] = 0;
        }
    }
}

或者以更通用的方式，當我們有一個 N1 x N2 x … x Nd 元素的陣列時， d 維度和索引標記為 n1，n2，…，nd 偏移量計算如下

圖片/公式取自： https ： //en.wikipedia.org/wiki/Row-major_order