16

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

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

我对数组的理解是,如果访问了一个元素,那么该内存块和许多周围的块将被带入缓存,从而实现更快的内存访问。

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

4

1 回答 1

15

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

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

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

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

于 2013-09-28T07:42:09.367 回答