下载掌阅APP，畅读海量书库
立即打开
一个常见的编程问题：遍历同样大小的数组和链表，哪个比较快？如果按照某些教科书上的分析方法，两者一样快，因为时间复杂度都是 O ( n )，但其实遍历数组比遍历链表要快很多。
首先介绍一个概念：存储器层次（memory hierarchy）。计算机中存在多种不同的存储器，各存储器的平均存取速度相差很大，如表1.1所示。
表1.1
各存储器的平均存取速度差异非常大，CPU寄存器的平均存取速度是内存的平均存取速度的大约100倍！这就是为什么CPU生产厂家发明了CPU缓存，而CPU缓存就是数组和链表的关键区别所在。
CPU缓存会把一个连续的内存空间读入，因为数组结构是连续的内存地址，所以数组的全部或者部分元素被连续保存在CPU缓存中，平均读取每个元素只要3个CPU时钟周期。而链表的节点是分散在堆空间里面的，读取的时候CPU缓存帮不上忙，只能去读取内存，平均读取时间为100个CPU时钟周期。这样算下来，遍历数组的速度比遍历链表的速度快大约33倍！（以上皆为理论数字，具体的数字因CPU型号及环境不同而略有差异）。
因此，程序中尽量使用连续的数据结构，这样可以充分发挥CPU缓存的优势。对缓存友好的算法称为 Cache- oblivious algorithm，有兴趣的读者可以参考相关资料。再举一个简单的例子，程序如下。
两个程序的执行结果一样，算法复杂度也一样，但是程序2的执行速度要快很多，因为C++的数组是按行存储的。