逐行访问矩阵元素与列方式

给出矩阵A[i][j] 。 如果我们想添加矩阵的元素，哪种方法更好，为什么？

1. 列明智
2. 划明

从我的角度来看，行方式更好，因为在数组表示元素存储在连续的内存位置，因此访问它们花费的时间更少。但是因为在RAM中获取每个位置需要相同的时间，这是否重要？

Answer 1

利用空间局部性

在C中，矩阵以r ow-major顺序存储。 因此，如果访问元素a[i][j] ，则对元素a[i][j+1]的访问可能会到达缓存。 不会访问主存储器。 缓存比主内存快，因此访问模式很重要。

当然，必须考虑更多因素，例如写访问/读访问，写策略（直写，回写/写分配，无写分配），多级缓存等。 但这似乎对这个问题有点过分。

使用分析工具（如cachegrind）获得一些乐趣，并亲自查看。

例如，考虑一个访问4MB矩阵的虚拟程序。 查看每种访问模式的未命中率之间的差异。

列访问

 $ cat col_major.c #include  int main(){ size_t i,j; const size_t dim = 1024 ; int matrix [dim][dim]; for (i=0;i< dim; i++){ for (j=0;j  

行访问

 $ cat row_major.c #include  int main(){ size_t i,j; const size_t dim = 1024 ; int matrix [dim][dim]; for (i=0;i< dim; i++) for (j=0;j  

Answer 2

如果arrays很小，那就不重要了。 如果它们很大，那么读取时间可能会受到影响。 最大的问题是缓存。 如果您不能指望将完整矩阵一次加载到缓存中，那么您希望最大限度地减少遇到的缓存未命中数，因为处理缓存未命中相对耗时。

如果arrays真的很大，那么你可以通过引起更多页面交换来获得更大的性能命中率。

Answer 3

对于C，处理多维数组的最佳方法是：

 int a[MAX_I][MAX_J]; for (i = 0; i < MAX_I; ++i) { for (j = 0; j < MAX_J; ++j) { /* process a[i][j] */ } } 

原因是C语言将数组作为具有偏移量的指针处理，请参阅： C编程语言 。