ReZero's Utopia.

(译)缓存参数无关算法

Word count: 1.2kReading time: 4 min
2020/07/05 Share

缓存参数无关算法 笔记

参考链接:

Cache Oblivious Introduce blog

Cache Oblivious paper

假设 硬盘 存在 M bits,以 B bits 作为分页大小,缓存按页加载,介绍相关的缓存参数无关的命中算法,这里的参数指 B

转化问题: N 个整数, 按 B 个 一页,求最快找到 N 所在页的算法

算法低效但是参数无关: 二分查找

假设 N 个整数本身是有序的,采用方法: 总长 O(N) 所以计算查找次数为 O(logN -logB),因为二分范围降到 B 时直接取出该页

参数无关是因为该算法并不知晓 B 的值,它只是按照标准的二分查找去搜(调用方是缓存,它load B 页时会去查到真正的所需值来停止二分,这对二分算法本身不可见)

非低效,但是参数相关: B-Tree

假设一开始知晓 B 的值,那么就可以达到 O(log[B]N) (中括号代表底数),具体如下

首先把 list 转成 B 树:也就是说每个节点有 B 个元素,统一节点的元素是有序的,不同节点之间是整体有序的,每个节点上 B 个元素会产生 B+1 个分支,这样生成树之后,每下降一层间隔就会减少 B 倍(也就是砍掉了其他分支,相当于树的第二层取了节点作为新树), 那时间复杂度就是 O(logN/logB) = O(log[B]N)

非低效且参数无关算法: van Emde Boas layout

传统的二分搜索树的特性决定了每次搜索都是 O(logN - logB),这显然不合期望,van Emde Boas layout 算法使用了一种很好的递归方式来排序,从而使得每次分页的查询都包含接下来可能要查的几个节点,从而提高命中率。

简洁概念

假设存在树高 H = 2^K.

概念展开

假设现在有一棵完全二叉树 H = 2^K,以 x 作为 root 节点,而我们的目的是计算出二叉树顶点的一种排列: L(x, k)

  1. 横切 2^(k-1) 和 2^(k-1) + 1 两层之间的枝,然后我们将得到这样的结果

    • n=2^(h/2)2^(K-1) 高 的小完全二叉树这些二叉树是从上面的节点断开后生成的,分别以 l1..ln 作为根节点。
    • 以及以 root 作为根节点的 2^(K-1) 高的根树。
  1. x 根节点和 k 值得到的这 n+1 个 BST的调用函数 我们称为 L(x, k)

  2. 将它们排列好后返回(顺序不重要)

Sierpinski triangles, atoms and time

为了更好的解释接下来如何实现这种构造,首先给出一个直观的演示,它很像 Sierpinski 三角,如下:

同过 Sierpinski 三角 我们大致能得到一种限制深度的递归,这使得这个递归更加偏像 BFS 而不是 DFS。

具体一点来说,我们引入 t 变量作为限制的递归深度,并引入概念 atom 代表递归深度为 t 时的子树单元。举例来说,递归深度 t 为 0 的时候,atom 是整个树。

接下来,当 t = 1 我们得到上面提到过的 2^(K-1) 高的子树,这时的 atoms 指的就是这些子树。

继续提高 t 递归深度,得到一批 2^(K-2) 的 atoms。

随着递归深度的提高最终 atoms 会变成最小的子树单元也就是一个个独立的节点。这一过程表明我们通过限制 t 即递归的深度可以得到不同程度精细的 atoms,综上可以获取如下推论

In the final layout, we can choose any resolution to look at the layout. All vertices in any atom at this resolution will be in a contiguous segment.

Algorithm

假设页面大小是 B。 每步进一次,原子的高度减半。这样 B 和原子的关系就构建出来了,无论 B 是多大,只要每次我们使得得到的 原子群 高度为 O(logB) 即可,这样他就可以塞进一页(2^(logB) = B)当中去。

现在来算下搜索复杂度:它会首先遍历第一个 atom 子树,直到遍历完该子树的所有节点,然后继续使用相同的遍历去遍历下一个 atom 子树,每次这样的遍历花费 O(logB) 次步进,然后未划分子树前我们知道整棵大树需要 O(logN) 次遍历,所以我们可以算出来一共有 O(logN / logB) = O(log[B]N)atom,这个数量也同时就是我们需要 access page 的次数。

CATALOG
  1. 1. 缓存参数无关算法 笔记
    1. 1.1. 算法低效但是参数无关: 二分查找
    2. 1.2. 非低效,但是参数相关: B-Tree
    3. 1.3. 非低效且参数无关算法: van Emde Boas layout
    4. 1.4. 简洁概念
    5. 1.5. 概念展开
    6. 1.6. Sierpinski triangles, atoms and time
    7. 1.7. Algorithm