去摊还化 | Codeboy's Blog

形式陈述

摊还分析保证一段操作序列的总成本，仍允许某次操作付出线性工作。去摊还化重新调度这些工作，让每次公开操作都只承担固定预算，同时保持中间状态可查询。它通常需要三份证明：迁移期间的访问仍正确，每次工作量有界，以及本轮迁移在下一轮启动之前结束。

一个完整模型：顺序动态数组

以下构造支持串行执行的 $\operatorname{append}(v)$ 、合法下标的 $\operatorname{read}(i)$ 与 $\operatorname{write}(i,v)$ 。每个值占常数机器字，槽的读写与复制成本为 $O(1)$ 。不包含删除、收缩或并发操作；直接返回底层连续存储指针也不属于接口。

稳态维护动态数组 $A$ 、长度 $n$ 和容量 $C\ge1$ ，初始为空且容量为 $1$ 。当 $n<C$ 时，追加直接写 $A[n]$ 后令 $n\leftarrow n+1$ 。当满载追加时，在写新元素之前启动迁移：

N=C=n,\qquad O=A,\qquad B=\text{容量为 }2N\text{ 的未初始化新区},\qquad k=0.

$N$ 是本轮固定的旧规模， $n$ 是继续变化的逻辑长度； $k$ 是已经迁移的旧槽数。新追加值写入 $B[n]$ ，再增加 $n$ 。迁移期间，已有下标的唯一权威位置为

\operatorname{slot}(i)= \begin{cases} B[i],&0\le i<k,\\ O[i],&k\le i<N,\\ B[i],&N\le i<n. \end{cases}

读操作从权威槽返回值，写操作只改权威槽；追加总写 $B[n]$ 。不需要同时更新旧副本与新区，也没有日志。新区中的尚未初始化槽不会被读到。

每个合法公开操作先完成用户动作，再执行恰好 $\min\{2,N-k\}$ 个微步。每个微步为

B[k]\leftarrow O[k],\qquad k\leftarrow k+1.

达到 $k=N$ 时提交 $A=B,C=2N$ ，回收旧区并结束迁移。触发扩容的追加本身也领取这次迁移预算。“至多搬两项”只限制成本；要证明进度，还须规定只要有剩余任务，就做满两项。

越界读写在改变状态之前报告错误；新区分配失败也须在改变原逻辑序列前报告失败。下面的序列定理针对内存申请成功的合法操作。

正确性：权威槽归纳

不变量是：每个逻辑下标 $0\le i<n$ 的最新值位于 $\operatorname{slot}(i)$ ，已复制前缀不会再次从旧区读取。

稳态显然满足。启动时 $k=0$ ，旧 $N$ 个值仍以 $O$ 为准，新增值直接写入 $B[N]$ ，因此不变量仍成立。一次读不改变逻辑序列；一次写改动的正是该下标的权威槽；追加只新增一个新区下标，均保持表示正确。

微步复制的下标恰为 $k$ ，其权威值仍在 $O[k]$ 。先把当前值写入 $B[k]$ ，再推进前沿，新权威位置因而拥有同一个最新值。若此前曾写过这个尚未迁移的下标，写入已更新 $O[k]$ ，复制自然带走新值。前沿之前的旧副本即使陈旧，也不会再被访问或复制。

当 $k=N$ 时，所有旧下标与新增下标的权威值都在 $B$ ，提交可恢复稳态。因此归纳覆盖了任意合法的读、写、追加混合序列，而不只是一串插入。

截止期：下次扩容前一定完成

从触发追加开始计数，设已经完成 $t$ 次公开操作，其中有 $a_t$ 次追加。在本轮尚未提交时，

k_t=\min\{N,2t\},\qquad n_t=N+a_t\le N+t.

本轮迁移最多需要 $\lceil N/2\rceil$ 次操作。新区共有 $N$ 个额外空位，至少需要 $N$ 次追加才再次装满，第 $N+1$ 次追加才会触发下一次扩容。因此

\lceil N/2\rceil\le N<N+1

保证两轮不重叠。读写不消耗容量，却继续推进迁移，只会让完成时间提前。迁移任务始终是最初的 $N$ 个槽，新增下标没有加入待复制集合。

每次只搬一项其实也足够：第 $N$ 次公开操作末已经复制完毕，而下一次触发扩容的追加尚未开始。两项预算提供更早完成的余量；不能声称本翻倍数组必须每次搬两项才追得上。

直觉

摊还分析说“一整段操作付得起搬家费用”，去摊还化进一步安排“每次搬多少，以及搬家时到哪里找当前值”。前沿 $k$ 就是地址路由规则：它左边去新区，它右边尚属旧范围的槽去旧区，新增尾部始终去新区。

两份物理副本并不要求双写。这里的串行次序保证复制总能读到未迁移位置的最新值，前沿推进后旧副本永久退出权威位置。困难在于规定清楚切换时刻，而不是让两块存储在每时每刻都完全相同。

图中的 $k=2$ 状态已经复制 $a,b$ ， $c,d$ 仍以旧区为准，刚追加的 $e$ 在新区。复制预算限制单次搬迁工作；此前的证明还说明何时必须做满预算以及什么时候提交。

例子与边界

一条含迁移期间读写的实际轨迹

初态容量与长度均为 $8$ ，数组为 $[a,b,c,d,e,f,g,h]$ 。下表在迁移期间先执行用户动作，再搬两项； $k$ 表示本行结束时的前沿。

操作	用户动作的位置与结果	随后复制的旧下标	结束状态
$\operatorname{append}(i)$	启动迁移，写 $B[8]=i$	$0,1$	$n=9,k=2$
$\operatorname{read}(0)$	$0<k$ ，从 $B[0]$ 返回 $a$	$2,3$	$n=9,k=4$
$\operatorname{write}(7,h')$	$k\le7<N$ ，只改 $O[7]$	$4,5$	$n=9,k=6$
$\operatorname{read}(7)$	从 $O[7]$ 返回 $h'$	$6,7$	$k=8$ ，提交容量 $16$
$\operatorname{append}(j)$	在稳态写 $A[9]=j$	无	$n=10$

第三行更新尚未复制的槽，第五行最终数组为

[a,b,c,d,e,f,g,h',i,j].

若写操作错误地只更新未初始化的 $B[7]$ ，第四行稍后的复制就会用旧 $h$ 覆盖它。权威位置规则防止了这个具体错误。

图中的容量 $4$ 是同一规则的更小状态：第一次追加后 $k=2$ ，第二次操作末就完成迁移。因此不能在一条容量 $4$ 的轨迹中再安排多次“尚在迁移期间”的读写。 $N=1$ 时，触发追加写入 $B[1]$ 后只复制一个剩余旧槽，当次即完成。

分配、空间与真实时间

每次公开操作包含一个用户动作、至多两次槽复制，以及常数个元数据更新。若抽象模型把未初始化区块的保留与释放也计为 $O(1)$ ，则上述三种操作具有确定性的最坏 $O(1)$ 时间。 在迁移期旧区与新区共占 $N+2N=3N$ 个槽，且此时 $n\ge N+1$ ，所以空间为 $O(n)$ ；从容量 $1$ 开始的稳态空间为 $O(n+1)$ 。

实际分配器可能初始化整块内存，元素复制可能触发复杂对象操作，释放可能调用析构或垃圾回收。此时应把这些成本另计，不能只凭“复制两槽”就声称真实执行时间有最坏常数界。惰性页映射也可能把成本推迟为页错误，不能自动提供硬实时保证。

迁移期间逻辑序列分布在两块区间，仍有最坏常数下标访问，但不再由单个连续存储区承载。需要持续暴露连续缓冲区地址的接口不能直接采用此构造。

哪些变化需要重新证明

删除、收缩、并发读写和后台迁移都超出上面的操作模型。它们可能改变重建期限、增加正在复制位置的竞争、或要求独立的内存回收协议。一个“加锁或加版本号”的建议本身既不构成完整正确性证明，也不提供等待时间上界。

更一般的数据结构还可能不断产生新的迁移任务。如果每步新增工作超过固定处理预算，积压会增长；这时必须重新比较任务到达率与处理率。本数组每轮任务数固定为 $N$ ，不能拿这种持续到达的反例否定每步一项已经足够的结论。

推论与应用

全局重建规定何时从活动元素恢复结构；一次性执行仍可能造成线性停顿。把它去摊还化，需要额外给出可增量执行的微步、过渡期访问规则和完成期限。本页的前沿是其中一种特定实现，其他结构可能需要双查、双写或更新日志，不能机械照搬。

确定性工作预算加确定性截止期才能给本页的逐操作最坏界。若重建规模只以高概率受控，则相应保证也只是高概率；若依赖后台线程，则还须加入调度假设。去摊还化改变的是算法的工作安排，不会凭空消除资源申请、竞争和回收成本。

参考资料

Michael T. Goodrich, Daniel S. Hirschberg, Michael Mitzenmacher and Justin Thaler, Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability, MedAlg 2012，作者稿 §4.1、p.11 的 crossover index 与每次访问复制两项。原文采用半满启动和访问前复制；本页对满载启动、操作后复制的顺序数组给出独立证明，不沿用其外围字典的概率保证。
Mark H. Overmars, The Design of Dynamic Data Structures, Lecture Notes in Computer Science 156, Springer, 1983，动态重建与去摊还化的系统背景。

形式陈述 ​

一个完整模型：顺序动态数组 ​

正确性：权威槽归纳 ​

截止期：下次扩容前一定完成 ​

一条含迁移期间读写的实际轨迹 ​

分配、空间与真实时间 ​

哪些变化需要重新证明 ​

反向链接