程式語言入門/陣列成本模型

我們說，如果資料結構儲存的任何元素的讀取（或更新）成本相同，無論其位置如何，那麼該資料結構就是隨機訪問的。函式式列表顯然不是隨機訪問的：讀取第 n 個元素是 O(n)。另一方面，C 或 Java 中的陣列是隨機訪問的。還有其他資料結構也是隨機訪問的，至少平均而言，例如雜湊表。從現在開始，我們將重點關注 C 樣式的陣列。隨機訪問的關鍵在於陣列在記憶體中是連續儲存的。因此，像a[i]這樣的訪問，在一個型別為 T 的陣列中，可以轉換為表示式*(a + i)。同樣的原理也適用於多維陣列。舉個例子，a[i][j]在一個有 M 行 N 列的二維陣列中，在 C 中，轉換為*(a + i*N + j)。然而，即使我們將自己限制在陣列中，也很難始終確保相同的訪問成本。罪魁禍首是所謂的區域性性。為了解釋什麼是區域性性，讓我們考慮兩個迴圈

#include <stdio.h>
int main(int argc, char** argv) {
  const int M = 5000;
  const int N = 1000;
  char m[M][N];
  int i, j;

  if (argc % 2) {
    // initializes the array, row major:
    for (i = 0; i < M; i++) {
      for (j = 0; j < N; j++) {
        m[i][j] = 1;
      }
    }
  } else {
    // initializes the array, column major:
    for (j = 0; j < N; j++) {
      for (i = 0; i < M; i++) {
        m[i][j] = 1;
      }
    }
  }

  return 0;
}

這個程式執行速度不同，這取決於哪個迴圈執行（在一臺 1.4GHz 的英特爾酷睿 i5 上）

$> clang -O0 trixSpeed.c -o trixSpeed

$>  time ./trixSpeed a

real	0m0.073s
user	0m0.068s
sys	0m0.003s

$> time ./trixSpeed 

real	0m0.025s
user	0m0.019s
sys	0m0.003s

那麼，這個例子發生了什麼呢？無論哪個迴圈執行，執行的操作次數都是相同的。但是，第一個迴圈快了 3.5 倍。如前所述，影響這些結果的關鍵因素是區域性性。現代通用計算機架構使用快取。快取被劃分為行。資料不是單獨從主記憶體帶入快取的。而是，一次帶入整行。如果程式可以訪問同一行上的多個數據，那麼就可以避免記憶體訪問。另一方面，如果跨不同行訪問資料，則必須執行多次訪問主記憶體的操作。這些訪問操作代價高昂，並且是此示例執行成本的主要來源。

如何實現一個程式，以便它能更多地從區域性性中獲益？答案是：這取決於程式語言。C 以行優先的方式組織資料。這意味著在二維陣列中，同一行上的資料在記憶體中彼此相鄰。但是，同一列中的資料可能相距很遠。同一列但相鄰行中的單元格將相隔 N 個元素，其中 N 是二維陣列中的行大小。另一方面，有些程式語言以列優先的方式組織資料。例如 Fortran。在這種情況下，在遍歷二維陣列時，固定列並改變行效率更高。