第4章 List Ranking：链表排名

把任意磁盘布局的链表排名转化为批量 Sort/Scan，理解指针跳跃的并行模拟，并用大独立集分治达到近扫描级 I/O。

学习目标

能解释“4 List Ranking”如何把链式随机访问改写为指针跳跃、排序扫描与分治收缩
能逐项核对The Pointer-Jumping Technique、Parallel Algorithm Simulation in a Two-Level Memory、A Divide-and-Conquer Approach，不把平台页数或相邻章节主题冒充原版目录
能固定输入和参数，按“rounds = ceil(log2(n))”手算一个最小样例，并找到输出或成本的首个分叉
能注入“同一轮原地更新 successor 与 rank，混用新旧状态破坏并行轮次语义”，保存基线、故障、恢复和同输入重放证据

来源、版次与独立重写边界

“4 List Ranking”对应 Paolo Ferragina 的 Pearls of Algorithm Engineering（Cambridge University Press，2023）。出版社书籍页确认作者、版次、ISBN、318页与算法工程定位；官方目录页和官方前置信息 PDF共同给出16章、61个编号节与索引的正式顺序。

对“4 List Ranking”而言，当前公开可核验材料是出版社目录、前言与书籍说明，并非获授权完整正文。因此，下方中文讲解、公式推导、代码和实验是按公开目录坐标进行的独立教学重写，不声称逐段翻译原书；涉及“把链式随机访问改写为指针跳跃、排序扫描与分治收缩”的结论必须由本页的最小输入、预言机与成本记录重新证明。

官方目录坐标：4 List Ranking

4.1 The Pointer-Jumping Technique：在本页正文中以“把链式随机访问改写为指针跳跃、排序扫描与分治收缩”的对象、状态、复杂度或工程边界核对。
4.2 Parallel Algorithm Simulation in a Two-Level Memory：在本页正文中以“把链式随机访问改写为指针跳跃、排序扫描与分治收缩”的对象、状态、复杂度或工程边界核对。
4.3 A Divide-and-Conquer Approach：在本页正文中以“把链式随机访问改写为指针跳跃、排序扫描与分治收缩”的对象、状态、复杂度或工程边界核对。

从“链上走一遍”在磁盘上为何很贵开始

给定 n 个带唯一 id 的单向链表节点，Succ[i] 保存节点 i 的后继 id；尾节点 t 用 Succ[t]=t 的自环表示。要求输出每个节点到尾部的距离 Rank[i]。

图中的逻辑链是 2→5→1→4→3，但 Succ 与 Rank 数组按 id 的数值顺序存放。RAM 模型允许通过 Succ 指针常数时间跳到任意数组位置，所以可从头向后两遍赋值、构造前驱后从尾向前赋值，或递归计算后继 Rank，均为 O(n) 时间。

先预测同一算法放到磁盘后的行为：逻辑相邻节点的 id 可以相距很远，每次追踪 Succ 都可能换页。虽然只访问 n 个节点，却可能产生 Theta(n) 次随机 I/O，而信息量下界只要求读写 Theta(n/B) 页。

本章的目标不是让指针跳得更快，而是把大量随机取数重新排列为少量批量排序与顺序扫描。这也揭示一个重要联系：低深度并行算法的共享内存访问，常能转成高效的外存批处理。

指针跳跃让已知距离每轮翻倍

pointer-jumping technique为每个节点配置一个处理器。初始时尾节点 Rank 为0，其余节点 Rank 为1。每一轮从旧快照同步执行：

\begin{aligned} \operatorname{Rank}'[i] &= \operatorname{Rank}[i] +\operatorname{Rank}[\operatorname{Succ}[i]],\\ \operatorname{Succ}'[i] &= \operatorname{Succ}[\operatorname{Succ}[i]] \end{aligned}

不变式是：当前 Rank[i] 等于原链上从 i 到当前 Succ[i] 的边数。累加后，两段首尾相接；后继再跨过同一个中间点，因此不变式保持。

第 r 轮后，一个尚未到尾的节点最多知道原链上 2 的 r 次方步之外的位置，所以最长距离 n-1 在 O(log n) 轮内覆盖。用 n 个处理器时并行时间为 O(log n)，但总操作量是 O(n log n)，高于最优顺序 RAM 算法的 O(n)。

void pointer_jump_round(
    const std::vector<int>& old_succ,
    const std::vector<int>& old_rank,
    std::vector<int>& new_succ,
    std::vector<int>& new_rank) {
    for (std::size_t i = 0;
         i != old_succ.size();
         ++i) {
        const std::size_t next =
            static_cast<std::size_t>(old_succ[i]);
        new_rank[i] =
            old_rank[i] + old_rank[next];
        new_succ[i] = old_succ[next];
    }
}

用两次排序和三次扫描模拟随机访存

parallel algorithm simulation in a two-level memory（两级存储中的并行算法模拟）面对一般形式 A[a_i] op A[b_i]：第 i 个处理器读取源 A[b_i]，用 op 更新目标 A[a_i]。直接按 i 执行会随机读取 b_i。

使用三元组 (a_i,b_i,0)：

Scan 输入，生成全部三元组；
按 b_i Sort，让记录与源数组位置对齐；
协同 Scan 数组 A，把 A[b_i] 填入记录；
按 a_i Sort，让记录与目标位置对齐；
协同 Scan A，执行目标更新。

两次 Sort 与三次 Scan 都作用于 Theta(n) 条定长记录。若用软 O 记号隐藏外存排序中很小的对数因子，一次并行步骤需要：

\widetilde O\left(\frac{n}{B}\right) \quad\text{I/Os}

指针跳跃的 Rank 更新与 Succ 更新具有相同源 i、目标 Succ[i]，可把两种值装进四元组，在一次批处理中完成。O(log n) 轮总计：

\widetilde O\left(\frac{n}{B}\log n\right) \quad\text{I/Os}

相比直接追链的 Theta(n) I/O，只要 B 明显大于 log n 就有优势。更一般地，n 个处理器、T 轮的 PRAM 算法可用 O(n) 空间和约 (\widetilde O((n/B)T)) I/O 模拟；T 远小于 B 时得到次线性 I/O。

这种通用转换的代价是工作量可能不最优。指针跳跃仍让所有活动节点参与多轮，下一节用分治只对被删节点周围做必要更新。

分治方法：每层删除一个大独立集

divide-and-conquer approach先给尾节点 Rank=0、其他节点 Rank=1，然后选一个节点集合 I，满足：

I 是；
I 至少有 n/c 个节点，其中常数 c 大于2；
因为相邻不能同时选，I 至多有 n/2 个节点。

Divide 找到 I。Conquer 从链中删除 I：仅对每个指向被删节点 y 的前驱 x 执行 Rank[x]+=Rank[y] 与 Succ[x]=Succ[y]，得到 L*。递归求 L* 的排名。

Recombine 再为每个 y 属于 I 计算 Rank[y]+=Rank[Succ[y]]。独立集性质保证 Succ[y] 没被同层删除，递归答案已经可用；Rank[y] 保存 y 到当前后继的原链距离，两者相加就是 y 到尾部的完整距离。

ListRankDC(L):
  I = large_independent_set(L)
  for each predecessor x of y in I:
      Rank[x] = Rank[x] + Rank[y]
      Succ[x] = Succ[y]
  ListRankDC(L without I)
  for each y in I:
      Rank[y] = Rank[y] + Rank[Succ[y]]

若每层独立集选择成本是 I(n)，其余删除与回填可由 Sort/Scan 完成，则递归为：

T(n) = I(n) +\widetilde O\left(\frac{n}{B}\right) +T\left(\left(1-\frac{1}{c}\right)n\right)

规模每层按常数比例缩小，所以只要 I(n) 是近扫描成本，各层几何级数之和仍为 (\widetilde O(n/B))。真正困难变成：不沿逻辑链扫描，怎样只用局部信息构造大独立集。

随机方案：选择 H 后接 T 的节点

为每个节点独立抛公平硬币。若节点 i 为 H 且 Succ[i] 为 T，就把 i 放进 I。相邻两个节点不可能同时满足条件：若 i 被选，其后继硬币为 T，不可能同时以 H 开头被选。因此 I 一定是独立集。

每个非尾节点被选的概率为：

\Pr(i\in I) = \Pr(H,T) = \frac14

期望选中约 n/4 个节点；Chernoff 集中界说明集合大小高度集中在期望附近。若小于 n/c，其中 c 取大于4的常数，就重新抛币，期望只需常数轮。

bool selected(
    std::size_t i,
    const std::vector<bool>& heads,
    const std::vector<int>& succ) {
    const auto next =
        static_cast<std::size_t>(succ[i]);
    return heads[i] && !heads[next];
}

检查 i 与 Succ[i] 的硬币值仍是批量随机访存，可用前述 Sort-Scan模拟。于是 I(n) 为期望近扫描成本，递归解为平均 (\widetilde O(n/B)) I/O。

选择 HH 或 TT 不行：一段连续相同硬币会让相邻节点同时入选，破坏独立集。选择 TH 也可以，只是把头尾角色互换。

确定性抛硬币：从唯一 id 压到三色

不用随机数。初始 coin(i)=i-1，所有节点颜色唯一，以 b=ceil(log n) 位表示。

对每个 i，找到 coin(i) 与 coin(Succ[i]) 第一个不同的位位置 pi(i)，记 i 在该位的值为 z(i)，并设置：

\operatorname{coin}'(i) = 2\pi(i)+z(i)

新颜色范围不超过 2b，表示位数从 b 缩到约 log b。若相邻节点得到相同新颜色，它们的 pi 与 z 都相同，但 pi 正是两者首个不同位，z 不可能也相同，形成矛盾。因此相邻颜色始终不同。

反复 O(log* n) 轮后颜色降到0至5，再用局部重着色降到0、1、2，最后选择颜色严格小于前驱与后继的局部极小节点。

局部极小节点不相邻，因此构成独立集；三色且相邻不同限制了两个局部极小值之间的最大间隔，可保证至少常数比例，本页给出 n/4 下界。每轮只比较节点与邻居，可用 Sort/Scan；log* n 增长极慢，被软 O 隐藏后，得到最坏情形确定性的 (\widetilde O(n/B)) I/O。

这里的不是把因子变没。工程报告仍应列出排序轮次、记录宽度、临时空间和实际传输量；在真实参数中它们通常小，但会影响实现。

如何验证链表排名实现

测试不能只生成按 id 顺序连接的链，那会把所有 I/O 难点隐藏掉。应先生成逻辑排列，再随机打乱 id，构造 Succ 数组；用 RAM 线性预言机求 Rank，与指针跳跃和分治结果逐节点比较。

边界至少覆盖单尾节点、两节点、长链、随机排列、独立集恰好很小的抛币结果，以及递归多层后 Rank[y] 大于1的回填。每轮指针跳跃要检查不变式：沿原链走 Rank[i] 步恰到当前 Succ[i]。

外存基准除总时间外，还应记录 Sort 与 Scan 次数、读写字节、随机 I/O、峰值临时空间和每层剩余节点数。只有 Rank 正确且数据移动符合推导，才能说明并行算法模拟真正转成了 I/O 效率。

先预测，再操作三个章专属实验

分步1 / 3

1. 成本模型与工作集

在“4 List Ranking”中先预测层级和访问模式如何改变“rounds = ceil(log2(n))”，再切换工作集与局部性；最终结果相同不代表代价相同。

Cost-model laboratory

4 List Ranking

把链式随机访问改写为指针跳跃、排序扫描与分治收缩

工作集所在层级

规模8192

传输256

相对成本8×

rounds = ceil(log2(n))

不变量：每个节点的最终 rank 等于到链尾的真实距离且节点集合不丢失

可重放工程合同

“4 List Ranking”的实验必须保留：节点 id、successor、每轮 rank、收缩集合、排序/扫描次数与串行预言机。本章性能数据至少预热一次、重复多次并报告分布；正确性必须与独立预言机比较，不能只比较两个共享同一错误的优化实现。

练习与答案

练习

问题 1：正式目录。 “4 List Ranking”的公开目录边界是什么，平台如何证明没有把其他章主题混入？

问题 2：最小反例。 怎样验证“rounds = ceil(log2(n))”不是只写在页面上的公式？

问题 3：恢复证据。 怎样证明“同一轮原地更新 successor 与 rank，混用新旧状态破坏并行轮次语义”已经修复？

本章回顾

链表排名输出每个节点到自环尾节点的距离。
RAM 中顺序追链是 O(n)，任意磁盘布局却可能产生 Theta(n) 随机 I/O。
指针跳跃同步更新 Rank 与 Succ，O(log n) 轮、O(n log n) 总工作。
两次按源和目标排序、三次扫描可批量模拟 A[a_i] op A[b_i]。
PRAM 的 T 轮可转成约 (\widetilde O((n/B)T)) 的两级存储模拟。
分治删除常数比例独立集，递归剩余链，再回填被删节点累计距离。
随机 HT 规则以1/4概率选节点且保证相邻节点不能同时入选。
确定性抛硬币把唯一 id 压到三色，再由局部极小构造大独立集。
随机方案给出平均近扫描 I/O，确定性方案给出最坏情形近扫描 I/O。