大型数组按行遍历与按列遍历的区别
对于一个很大的数组（如`70000×70000`），按行遍历速度快还是按列遍历快，为什么？
今天这学期开学第一天，上了《计算机操作系统原理》，老师提出个问题
对于一个很大的数组（如
70000×70000），按行遍历速度快还是按列遍历快，为什么？
乍一看，程序时间复杂度一样，理论上不是应该一样快吗？难道老师在钓鱼？
实践出真知，我们就写个程序跑一跑。
程序
70000×70000我电脑在默认情况下开不下，我这里用20000×20000测试
按行遍历
/**
* M1
*/
public class M1 {
public static void main(String[] args) {
final int N=20000;
int[][] a = new int[N][N];
Long start=System.currentTimeMillis();
for(int i=0;i<N;i++){
for (int j = 0; j < N; j++) {
a[i][j]=1;
}
}
Long stop=System.currentTimeMillis();
System.out.println(stop-start);
}
}
按列遍历
/**
* M2
*/
public class M2 {
public static void main(String[] args) {
final int N=20000;
int[][] a = new int[N][N];
Long start=System.currentTimeMillis();
for(int i=0;i<N;i++){
for (int j = 0; j < N; j++) {
a[j][i]=1;
}
}
Long stop=System.currentTimeMillis();
System.out.println(stop-start);
}
}
运行结果
分析
好吧，看上去的确是不一样。看这结果是不是感觉有点玄学，为啥差这么多？
回想计算机组成原理学过的知识，计算机组成原理笔记，存储器的层次化结构，高速缓存……
没错，就是这货！
存储器的层次化结构
典型存取时间 存储器 典型容量 1ns 寄存器 <1KB 2ns 高速缓存（cache） 4MB 10ns 主存储器（RAM和ROM） 500MB~4GB 10ms 辅助存储器（硬盘） 40~500G 10s 海量后备存储器（磁带库、光盘等） 10~100TB 在很多主流编程语言中，数组在内存中存放的方式是“一行行”存放的，按行遍历，访问的内存地址分别为
x+1,x+2,x+3,……,x+n,x+n+1……
而按列遍历访问的顺序是
x+1,x+n+1,x+2n+1,……,x+n(n-1)+1,x+2,x+n+2,……
cache的命中率基本为0，结合几种存储器的速度，不难分析出原因了。
所以，针对这个问题，在回答时要说明前提，即数组在内存中的实际的编址方式是怎样的。
在我机器java这例子，就是按行遍历快了。
2019年09月16日，我把实验过程给老师看了，老师补充这个速度除了与高速缓存的命中有关，还与编译器的内存管理有关。
最后修改于 2019-09-16