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

Question

我理解缓存不经意的表达是什么意思。但是我想知道是否有任何简单的解释可以解释如何设计可以优化使用缓存的数据结构，而不知道缓存的大小。

您能否提供这样的解释，最好是一个（简单的）示例？

Answer 1

即使是像快速排序这样熟悉的算法，也有点忘记缓存（但不是最优的）。回想一下，它的工作原理是对数组进行分区，然后在分区的每一侧递归。最终，它在一个适合缓存的子阵列上运行，因此在完成该子阵列并移动到另一个之前，不会有更多的缓存未命中。这就是我们正在寻找的财产。

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

不过，快速排序距离最优还有一段距离。每个单独的分区阶段不会划分和递归 - 它会在内存中进行长时间的连续运行，从而搅动缓存。在子数组大小足够小到我们开始获胜之前，这可能会发生几次，因此我们没有最小化缓存未命中的数量。

Answer 2

主要的直觉是，如果您递归拆分您使用的数据集，在某个时候（通常很快）您将达到 1）适合缓存的大小，并且 2）填充至少一半的缓存（假设每个拆分数据集的（至少大约）一半）。