指针跳跃与链表排名

List ranking 接口 ​

给一条以 next[v] 表示的无环单链表公理库链表Linked list节点通过指针连接并支持局部插入删除的线性数据结构。，尾节点满足 next[tail]=null。本文把 rank 定义为节点到尾的原始边数，因此尾 rank 为 0，前驱为 1；若应用要从表头开始的下标，可由总长度和尾距离换算，不能混用两个方向。

初始化

$$dist[v]=\{\begin{array}{ll}1,& next[v]\ne null,\\ 0,& next[v]=null.\end{array}$$

每个节点记录一条当前跳指针和这条跳边代表的原链距离。

同步 pointer jumping ​

每一轮所有活跃节点并行读取上一轮快照。若 $next[v]=u\ne null$，执行

$$dis{t}^{\prime }[v]=dist[v]+dist[u],nex{t}^{\prime }[v]=next[u].$$

尾节点和已跳到 null 的节点保持不变。所有新值写到另一缓冲或在轮末统一发布；若原地边读边写，不同处理器会混合两个轮次，倍增不变量失效。

第 $t$ 轮后，不变量是 next[v] 指向原链上至多 $2^t$ 条边后的节点，dist[v] 等于从 $v$ 到该指针目标的原始边数；若指针已为 null，dist[v] 就是到尾的完整距离。链长至多 $n$，故 $\lceil {\log }_{2}n\rceil$ 轮后全部完成。

四节点状态轨迹 ​

原链为 a→b→c→d→null。初态距离是 (1,1,1,0)。

第一轮使用旧快照：a 跳到 c、距离 2；b 跳到 d、距离 2；c 跳到 null、距离 1；d 保持 0。第二轮 a 读取 c 的旧状态，得到 null 与距离 $2+1=3$；b 读取 d，距离仍为 2。

最终 (3,2,1,0) 正是到尾排名。若第一轮更新 c 后立刻让 a 读新 c，a 会提前跨越不同倍数，其他节点又仍在旧层；算法可能在简单链上碰巧得到距离，却不再有统一轮次证明。

Work、depth 与处理器 ​

朴素方案每轮让所有 $n$ 个节点做常数工作，共 $O(\log n)$ 轮，因此

$$W=O(n\log n),D=O(\log n).$$

低 depth 并不等于 work-optimal：串行遍历只需 $O(n)$ 工作。经典 work-optimal list ranking 会随机或确定性选独立节点集合、把它们从链中 splice out，递归排名缩短后的链，再反向恢复被删节点，分析与单纯 pointer jumping 不同。

在 $P<n$ 时，直接按 Brent 调度给 $O(n\log n/P+\log n)$，仍保留额外对数工作。若只写“对数时间”，就隐藏了使用 $n$ 处理器和超线性 work 的条件。

PRAM 冲突规则 ​

每个节点只写自己的新记录，所以写是 exclusive。读取时，处理器 $v$ 读自身与后继 $u$ 的记录，而处理器 $u$ 也会读自身；自然实现因此允许 concurrent read，属于 CREW 风格。双缓冲解决轮次一致性，却不自动消除同地址并发读。

对一般 functional graph，多节点还可能共享同一后继，使并发读更明显。EREW 实现要复制目标记录或安排更复杂的读调度，并计入额外成本；不能只因为写目标不同就声称 EREW。

与 binary lifting 的区别 ​

倍增表公理库二进制倍增Binary lifting · Doubling technique预计算函数的 $2^k$ 次迭代，用输入步数的二进制展开快速跳转。预处理 up[v][j]，保留所有 $2^j$ 祖先以回答许多查询，空间 $O(n\log n)$。Pointer jumping 在每轮覆盖当前指针，用并行破坏式压缩换取一次全体排名，通常只保留 $O(n)$ 状态。

两者都用 doubling 不变量，但接口不同：前者是静态查询索引，后者是并行收缩过程。需要恢复原链时，必须另存初始 next，不能指望最终全部为 null 的数组仍含结构。

失败边界 ​

输入若含环，就没有尾距离，pointer jumping 会在环上周期跳转而不终止为 null。应先验证链结构、指定一个断点，或把问题改成 functional graph 的环检测与距离分解。

边带权时把初始 dist[v] 设为边权，更新仍用加法；负权不影响有限链求和，但可能溢出。多个不相交链可同时排名，尾节点各自为 0；共享尾的树形结构则不再是一条链，排名语义要重新定义。

参考资料

• James Wyllie, The Complexity of Parallel Computations, PhD thesis, Cornell University, 1979.
• Joseph JáJá, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
• Richard Karp, Vijaya Ramachandran, Parallel Algorithms for Shared-Memory Machines, 1990.