就局部性而言，数组与链表

Question

假设我们有一个未排序的数组和链表。
为两种数据结构搜索元素时最坏的情况是 O(n)，但我的问题是:

由于在缓存中使用空间局部性，数组是否仍然会更快，或者缓存是否会利用分支局部性允许链表与任何数组一样快？

我对数组的理解是，如果访问了一个元素，那么该内存块和许多周围的 block 就会被带入缓存，从而可以更快地访问内存。

我对链表的理解是，由于遍历链表的路径是可预测的，因此缓存将利用它并仍然存储适当的内存块，即使链表的节点在堆内可能相距很远.

Answer 1

您对数组案例的理解大多是正确的。如果一个数组被顺序访问，许多处理器不仅会获取包含该元素的 block ，还会预取后续 block ，以最大程度地减少等待缓存未命中所花费的周期。如果您使用的是 Intel x86 处理器，您可以在 Intel x86 优化 manual 中找到有关此的详细信息。 .此外，如果数组元素足够小，加载包含元素的 block 意味着下一个元素可能在同一个 block 中。

不幸的是，对于链表，从处理器的角度来看，加载模式是不可预测的。它不知道在地址 X 加载元素时，下一个地址是 (X + 8) 的内容。

作为一个具体的例子，顺序数组访问的加载地址序列很好且可预测。
例如，1000、1016、1032、1064 等。

对于链表，它看起来像:
1000、3048、5040、7888 等。很难预测下一个地址。