Muh*_*uri 4 language-agnostic cache-oblivious
我理解表达式缓存无意义的含义.但我想知道是否有任何简单的解释,如何设计数据结构,可以最佳地使用缓存,而不知道缓存的大小.
您能否提供这样的解释,最好是(简单)示例？
即使是像quicksort一样熟悉的算法也有点缓存(但不是最优的).回想一下,它通过对数组进行分区,然后在分区的每一侧进行递归来工作.最终,它在一个适合缓存的子阵列上运行,因此在完成该子阵列并转移到另一个子阵列之前不会再有缓存未命中.这是我们正在寻找的财产.
将此与插入排序进行对比,插入排序(使用技术术语)始终遍布整个地方.因此,除了插入排序需要移动O(n ^ 2)个项目之外,在大型数组上使用时,它也会错过很多缓存.
不过,Quicksort距离最佳状态还有一段距离.每个单独的分区阶段都不会进行分割和递归 - 它会通过缓存缓存的内存进行长时间的顺序运行.在子阵列大小足够小以至于我们开始获胜之前,这可能会发生几次,因此我们不会最大限度地减少缓存未命中数.