language-agnostic - 缓存遗忘数据结构背后的直觉是什么？

Question

我明白什么表达cache oblivious方法。但是我想知道是否有任何简单的解释来说明如何设计可以最佳地使用缓存的数据结构，而无需知道缓存的大小。

你能否提供这样的解释，最好是一个(简单的)例子？

Answer 1

即使是像快速排序这样熟悉的算法也有些缓存无意识(但不是最佳的)。回想一下，它的工作原理是对数组进行分区，然后在分区的每一侧递归。最终，它在一个适合缓存的子阵列上运行，因此在完成该子阵列并移动到另一个子阵列之前，不会有更多的缓存未命中。这就是我们要找的属性(property)。

将此与插入排序进行对比，插入排序(使用技术术语)一直在整个地方跳跃。因此，除了插入排序需要移动 O(n^2) 项之外，在大型数组上使用时，它也会错过很多缓存。

不过，快速排序离最佳排序还有一段距离。每个单独的分区阶段都不会划分和递归 - 它会通过内存搅动缓存进行长时间的顺序运行。在子阵列大小足够小以至于我们开始获胜之前，这可能会发生多次，因此我们不会最小化缓存未命中的数量。