编程语言入门/数组成本模型

我们说，如果数据结构存储的任何元素的读取（或更新）成本相同，无论其位置如何，那么该数据结构就是随机访问的。函数式列表显然不是随机访问的：读取第 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。在这种情况下，在遍历二维数组时，固定列并改变行效率更高。