假设我们有一个未排序的数组和链表。为两种数据结构搜索元素时最坏的情况是 O(n)，但我的问题是：
由于在缓存中使用空间局部性，数组是否仍然会更快，或者缓存是否会利用分支局部性允许链表与任何数组一样快？
我对数组的理解是，如果访问了一个元素，那么该内存块和许多周围的块将被带入缓存，从而实现更快的内存访问。
我对链表的理解是，由于遍历链表的路径是可预测的，因此缓存将利用它并仍然存储适当的内存块，即使链表的节点在堆内可能相距很远.
问问题
9108 次
1 回答
15
您对数组案例的理解大多是正确的。如果一个数组被顺序访问，许多处理器不仅会获取包含该元素的块，还会预取后续块以最小化等待缓存未命中所花费的周期。如果您使用的是 Intel x86 处理器，您可以在 Intel x86 优化手册中找到有关此内容的详细信息。此外，如果数组元素足够小，加载包含元素的块意味着下一个元素可能在同一个块中。
不幸的是，对于链表，从处理器的角度来看，加载模式是不可预测的。它不知道在地址 X 加载元素时，下一个地址是 (X + 8) 的内容。
作为一个具体的例子，顺序数组访问的加载地址序列很好且可预测。例如，1000、1016、1032、1064 等。
对于链表，它看起来像：1000、3048、5040、7888 等。很难预测下一个地址。
于 2013-09-28T07:42:09.367 回答