量化交易中文教材

第 17 章 摊还分析

本章对应原书第 17 章。前面各章分析的大多是"单个操作最坏要多久"。可有些数据结构偶尔会做一次很贵的操作（例如数组满了要整体搬家），平时却很便宜。只看单次最坏会把整体代价估得过高。摊还分析回答的是另一个问题：一整串操作最坏总共要多久，平均到每个操作上是多少。它是理解动态数组、并查集（第 21 章）、斐波那契堆（第 18 章）的必备工具，也直接关系到交易系统中"平均很快但偶尔卡顿"的设计取舍。

学习目标

读完本章，你应当能够：

  1. 说清摊还分析与平均情况分析的区别：前者不涉及概率，给出的是最坏情况下一串操作的平均代价。
  2. 用聚合分析、核算法、势能法三种方法分别分析带 MULTIPOP 的栈和二进制计数器，并说出三种方法各自的适用场合。
  3. 用势函数 \(\Phi=2\cdot num-size\) 证明"满则加倍"的动态表插入摊还代价为 3，并解释为什么"低于一半就减半"会抖动，而"低于 1/4 才减半"不会。
  4. 区分"摊还 \(O(1)\)"和"最坏 \(O(1)\)"，知道在低延迟系统里何时必须用预分配的环形缓冲区代替可扩容数组。
  5. 认识竞争分析（move-to-front）与"多层有序数组"（LSM 思想）这两个思考题背后的工程含义。

读前导读

这一章在解决什么问题。 有些操作平时很便宜，偶尔很贵。如果每次都按"最贵的那次"去估成本，结论会严重偏悲观。摊还分析的做法和会计里的摊销与预提几乎一模一样：一台设备一次性花 120 万元，你不会说"这个月成本 120 万、其余月份为 0"，而是每月摊 10 万；反过来，每三年一次的大修，你每月先预提一笔"大修准备"，到时候用准备金支付，当月利润就不会突然塌掉。本章的三种方法分别对应：

  • 聚合分析：把 \(n\) 个操作的总成本算出来，再平均。像"把一年的总费用除以 12"。
  • 核算法：便宜的操作多收一点钱，存成"信用"（预提的准备金），留给将来贵的操作花。要求是准备金余额永远不能为负。
  • 势能法：不再追踪每笔准备金挂在谁身上，而是用一个函数 \(\Phi\) 衡量"整个数据结构里现在存着多少准备金"，类似只看资产负债表上的"准备金余额"这一行。

和会计摊销不同的一点：摊还分析要求对最坏的操作序列也成立，不涉及概率，所以它是一个保证，不是一个期望。

本章还有一个对交易系统很重要的工程结论：摊还 \(O(1)\) 不等于每次都快。可扩容数组平均很便宜，但扩容那一下要整体搬家，形成延迟尖峰；低延迟系统要用预分配或环形缓冲区把它消除。

需要先想起来的数学。

  • 求和记号与几何级数。 \(\sum_{i=0}^{k-1}a_i\) 表示 \(a_0+a_1+\cdots+a_{k-1}\)。几何级数：\(1+\tfrac12+\tfrac14+\cdots=2\)；\(1+2+4+\cdots+2^m=2^{m+1}-1<2\cdot2^m\)。后者的意思是"翻倍序列的总和不超过最后一项的两倍"，这是本章所有 \(O(n)\) 结论的来源。见 第 00 册第 04 章 级数与收敛。
  • 取整符号。 \(\lfloor x\rfloor\) 是向下取整（\(\lfloor 3.7\rfloor=3\)），\(\lceil x\rceil\) 是向上取整（\(\lceil 3.2\rceil=4\)）。\(\lfloor\lg n\rfloor\) 是"不超过 \(n\) 的最大的 2 的幂的指数"，例如 \(\lfloor\lg 20\rfloor=4\)，因为 \(2^4=16\le20<32\)。
  • 望远镜求和（逐项相消）。 \((b_1-b_0)+(b_2-b_1)+(b_3-b_2)=b_3-b_0\)，中间项两两抵消，只剩首尾。这就是"各期净利润之和 = 期末留存收益 − 期初留存收益"。势能法的核心公式 (17.3) 就靠这一步。
  • 渐近记号 \(O\)、\(\Theta\)、\(\Omega\)。 \(O\) 是上界，\(\Omega\) 是下界，\(\Theta\) 是上下界同阶。见 第 00 册第 07 章 概率中的分析工具。

怎么读这一章。 17.1 必读，它说清楚摊还分析要回答什么。17.2 的二进制计数器和 17.4.1 的势能法定义是全章的核心，建议拿纸笔把计数器从 0 加到 8 走一遍。17.3 核算法篇幅短、直观，可以快速读过。17.5 动态表是与工程关系最紧的一节：17.5.2 必读；17.5.3 的逐情形核对第一次可以只看"错误策略为什么抖动"和最后的设计原则，代数核对留到第二遍。17.6 思考题可略读，但 LSM-tree 那一段对理解行情数据库很有帮助。17.7 建议直接读"逐条解读"。

17.1 为什么需要摊还分析

先看一个让人困惑的例子。一个栈除了 PUSH、POP 外再支持 MULTIPOP(S, k)：一次弹出栈顶 \(k\) 个对象，不够 \(k\) 个就全弹完。

def MULTIPOP(S, k):
    while not S.empty() and k > 0:
        S.pop()
        k -= 1

栈里有 \(s\) 个对象时，MULTIPOP 的实际代价是 \(\min(s,k)\)。原书图 17.1：栈自顶向下为 23, 17, 6, 39, 10, 47，MULTIPOP(S, 4) 后剩 10, 47，再 MULTIPOP(S, 7) 就清空了。

如果只看单个操作：栈里最多 \(n\) 个对象，一次 MULTIPOP 最坏 \(O(n)\)，于是 \(n\) 个操作最坏 \(O(n^2)\)。这个界是对的，但不紧。直觉告诉我们：一个对象只能被压入一次、弹出一次，"大量弹出"必须先有"大量压入"来垫付。

摊还分析（amortized analysis）就是把这种直觉变成严格的界：对任意长度为 \(n\) 的操作序列，求最坏总代价 \(T(n)\)，再看每个操作平均分到多少。它与平均情况分析（average-case analysis）不同——后者要假设输入服从某个分布，算的是期望；摊还分析不涉及概率，保证对最坏的那串操作也成立。

原书介绍三种方法，用同两个例子贯穿：

  • 聚合分析（aggregate analysis）：直接求 \(n\) 个操作的总代价上界 \(T(n)\)，每个操作的摊还代价都记为 \(T(n)/n\)。
  • 核算法（accounting method）：给不同类型的操作定不同的"收费"，多收的部分作为信用（credit）存在数据结构的某些对象上，留给以后的贵操作用。
  • 势能法（potential method）：和核算法类似，但把信用看作整个数据结构的"势能"（potential），用一个函数统一描述。

有一点需要提前说明：摊还分析里的收费、信用、势能只存在于分析中，代码里不需要（也不应该）维护什么 x.credit 字段。

17.2 聚合分析

聚合分析的做法最朴素：证明对所有 \(n\)，任意 \(n\) 个操作的最坏总时间是 \(T(n)\)，那么每个操作的摊还代价就是 \(T(n)/n\)，所有操作类型共用这个值。

17.2.1 带 MULTIPOP 的栈

每个对象被压入后最多被弹出一次。因此在任何操作序列中，POP 的调用次数（包括 MULTIPOP 内部调用的 POP）不超过 PUSH 的次数，而 PUSH 次数不超过 \(n\)。所以任意 \(n\) 个 PUSH、POP、MULTIPOP 的总代价是 \(O(n)\)，每个操作的摊还代价是 \(O(1)\)。

这里没有用到任何概率推理，\(O(n)\) 是最坏情况下的总界。

17.2.2 二进制计数器

用 \(k\) 位数组 \(A[0..k-1]\) 表示计数器，\(A[0]\) 是最低位，值为 \(x=\sum_{i=0}^{k-1}A[i]\cdot 2^i\)。初值为 0，INCREMENT 对 \(2^k\) 取模加 1：

def INCREMENT(A):
    i = 0
    while i < len(A) and A[i] == 1:   # 把末尾连续的 1 翻成 0（进位）
        A[i] = 0
        i += 1
    if i < len(A):
        A[i] = 1

代价记为翻转的位数。粗看：全 1 时一次要翻 \(k\) 位，\(n\) 次是 \(O(nk)\)。

细看：\(A[0]\) 每次都翻；\(A[1]\) 每两次翻一次，共 \(\lfloor n/2\rfloor\) 次；一般地 \(A[i]\) 共翻 \(\lfloor n/2^i\rfloor\) 次。总翻转次数

\[\sum_{i=0}^{k-1}\left\lfloor\frac{n}{2^i}\right\rfloor<n\sum_{i=0}^{\infty}\frac{1}{2^i}=2n.\]

所以 \(n\) 次 INCREMENT 最坏 \(O(n)\)，摊还 \(O(1)\)。原书图 17.2 列出了计数从 0 加到 16 时的累计代价：1, 3, 4, 7, 8, 10, 11, 15, 16, 18, 19, 22, 23, 25, 26, 31，始终小于操作次数的两倍。

推导拆解：以 \(n=8\) 次 INCREMENT 为例逐位数。\(A[0]\) 翻了 8 次，\(A[1]\) 翻了 \(\lfloor8/2\rfloor=4\) 次，\(A[2]\) 翻了 \(\lfloor8/4\rfloor=2\) 次，\(A[3]\) 翻了 1 次，合计 15，与原书累计代价表第 8 项一致，小于 \(2\times8=16\)。 不等式的两步：第一步去掉取整，\(\lfloor n/2^i\rfloor\le n/2^i\)；第二步把有限项的和 \(\sum_{i=0}^{k-1}\) 放大成无穷项的和 \(\sum_{i=0}^{\infty}\)（多加的都是正数），而 \(1+\tfrac12+\tfrac14+\cdots=2\)。"\(<\)"而不是"\(\le\)"是因为放大时确实多加了正数。 换个角度读：越高的位越"贵"（进位时它要跟着翻），但也越"少见"，频率按一半一半递减，所以总量收敛。

一个小练习式的例子（原书 17.1-3）：第 \(i\) 个操作在 \(i\) 是 2 的幂时代价为 \(i\)，否则为 1。前 \(n\) 个操作的总代价不超过 \(n+\sum_{j=0}^{\lfloor\lg n\rfloor}2^j<n+2n=3n\)，摊还 \(O(1)\)。后面的动态表正好就是这个代价模式。

推导拆解：把每个操作的代价拆成"基本的 1"加上"额外部分"。所有操作的基本部分合计 \(n\)。额外部分只在 \(i=1,2,4,8,\dots\) 时出现，最大的那个 2 的幂不超过 \(n\)，即 \(2^{\lfloor\lg n\rfloor}\le n\)。这些 2 的幂的和 \(1+2+4+\cdots+2^{\lfloor\lg n\rfloor}=2^{\lfloor\lg n\rfloor+1}-1<2n\)。例如 \(n=20\)：\(1+2+4+8+16=31<40\)。两部分相加小于 \(3n\)。（这里为了简便，把 2 的幂处的代价按 \(i\) 全部算作额外部分，略有高估，不影响上界。）

聚合分析也有边界：如果给栈加上 MULTIPUSH（一次压 \(k\) 个），\(O(1)\) 摊还界就不成立了，因为每次 MULTIPUSH 自身就要 \(k\)；如果给计数器加上 DECREMENT，在 \(2^{k-1}\) 附近来回加减，每次都翻 \(k\) 位，\(n\) 次就是 \(\Theta(nk)\)（原书 17.1-1、17.1-2）。摊还界依赖于"贵操作必须由便宜操作预先垫付"的结构，破坏了这个结构，界就失效。

17.3 核算法

17.3.1 思想

核算法给第 \(i\) 个操作定一个摊还代价 \(\hat c_i\)（即收费）。收费高于实际代价 \(c_i\) 时，差额作为信用存在数据结构的某个对象上；以后某个操作的收费低于实际代价时，就用存下的信用支付。要让摊还总代价成为实际总代价的上界，必须对所有长度为 \(n\) 的操作序列都有

\[\sum_{i=1}^n\hat c_i\ \ge\ \sum_{i=1}^n c_i. \tag{17.1}\]

等价地说：任何时刻数据结构中的总信用 \(\sum\hat c_i-\sum c_i\) 都必须非负。如果允许信用暂时为负（先欠账后还），那一刻的摊还总和就不再是实际总和的上界。

核算法的特点是不同操作可以收不同的费，甚至收费可以渐近地不同。

金融直觉：\(\hat c_i\)（读作"c hat"，帽子表示"估计/分摊后的"）相当于每期计入损益的费用，\(c_i\) 是每期实际付出的现金。核算法要求的"总信用非负"就是"预提准备金账户余额永远不为负"：你只能花已经提好的钱，不能透支。一旦允许透支，"累计计提费用 \(\ge\) 累计实际支出"就可能在某个时点不成立，摊还代价也就不再是实际代价的上界。

17.3.2 栈：盘子上的一美元

实际代价：PUSH 1，POP 1，MULTIPOP \(\min(k,s)\)。设收费：PUSH 2，POP 0，MULTIPOP 0。

原书的类比是自助餐厅的一摞盘子，用 1 美元代表单位代价。每压入一个盘子付 2 美元：1 美元付压栈本身，另 1 美元放在这个盘子上。于是任何时刻栈里每个盘子上都放着 1 美元。POP 或 MULTIPOP 弹出盘子时，用盘子上的那 1 美元付账，自己不收费。栈里盘子数非负，所以信用非负；\(n\) 个操作的摊还总代价是 \(O(n)\)，实际总代价也就是 \(O(n)\)。

17.3.3 计数器：每个 1 上存一美元

把一位从 0 置为 1 收费 2 美元：1 美元付置位，1 美元留在这一位上，供以后把它复位为 0 时使用。于是复位不收费。每次 INCREMENT 至多置位一次（while 循环后那一行），摊还代价不超过 2。计数器中 1 的个数非负，所以信用非负，\(n\) 次 INCREMENT 总代价 \(O(n)\)。

17.4 势能法

17.4.1 定义

势能法把预付的"工作"表示为整个数据结构的势能，而不是挂在某个对象上。设初始数据结构为 \(D_0\)，第 \(i\) 个操作的实际代价为 \(c_i\)，操作后得到 \(D_i\)。势函数（potential function）\(\Phi\) 把每个 \(D_i\) 映到实数 \(\Phi(D_i)\)。第 \(i\) 个操作的摊还代价定义为

\[\hat c_i=c_i+\Phi(D_i)-\Phi(D_{i-1}). \tag{17.2}\]

即"实际代价加上势能的增量"。求和时中间项望远镜相消：

\[\sum_{i=1}^n\hat c_i=\sum_{i=1}^n c_i+\Phi(D_n)-\Phi(D_0). \tag{17.3}\]

只要 \(\Phi(D_n)\ge\Phi(D_0)\)，摊还总代价就是实际总代价的上界。由于事先不知道会执行多少个操作，通常要求对所有 \(i\) 都有 \(\Phi(D_i)\ge\Phi(D_0)\)。惯例是令 \(\Phi(D_0)=0\)，再证明 \(\Phi(D_i)\ge 0\)。若 \(\Phi(D_0)\neq0\)，换成 \(\Phi'=\Phi-\Phi(D_0)\) 即可（原书 17.3-1）。

推导拆解：(17.3) 是怎么来的？把 (17.2) 对 \(i=1,2,3\) 写开再相加： \(\hat c_1+\hat c_2+\hat c_3=(c_1+c_2+c_3)+\big[\Phi(D_1)-\Phi(D_0)\big]+\big[\Phi(D_2)-\Phi(D_1)\big]+\big[\Phi(D_3)-\Phi(D_2)\big]\)。 方括号里 \(\Phi(D_1)\) 一正一负抵消，\(\Phi(D_2)\) 也抵消，只剩 \(\Phi(D_3)-\Phi(D_0)\)。\(n\) 项同理。 于是"摊还总代价 − 实际总代价 = 期末势能 − 期初势能"。只要期末势能不低于期初，摊还总代价就不低于实际总代价，可以当作上界用。 金融直觉：\(\Phi\) 就是资产负债表上的"准备金余额"，(17.2) 是"本期计提费用 = 本期实际支出 + 准备金余额的变动"，(17.3) 是把各期加总后的勾稽关系。

直观理解：势能增加，说明这个操作被多收了费，多收的部分存进了势能；势能减少，说明势能在替这个操作付账。摊还代价依赖于势函数的选择，不同的势函数给出不同但都有效的上界。

设计势函数的原则：昂贵操作即将发生时，势能刚好积累到足以支付它；昂贵操作做完后，势能回到 0。这句话贯穿本章后半和第 18、21 章。

17.4.2 栈

令 \(\Phi\) 为栈中对象数。空栈 \(\Phi(D_0)=0\)，且 \(\Phi(D_i)\ge0\)。

  • PUSH：势能增 1，\(\hat c=1+1=2\)。
  • MULTIPOP(S, k)：弹出 \(k'=\min(k,s)\) 个，实际代价 \(k'\)，势能降 \(k'\)，\(\hat c=k'-k'=0\)。POP 同理为 0。

三种操作摊还都是 \(O(1)\)，\(n\) 个操作最坏 \(O(n)\)。

17.4.3 计数器

令 \(\Phi\) 为计数器中 1 的个数 \(b_i\)。设第 \(i\) 次 INCREMENT 把 \(t_i\) 位复位为 0，实际代价不超过 \(t_i+1\)（复位 \(t_i\) 位，最多再置位一位）。若 \(b_i=0\)，说明 \(k\) 位全部复位，\(b_{i-1}=t_i=k\)；若 \(b_i>0\)，则 \(b_i=b_{i-1}-t_i+1\)。总之 \(b_i\le b_{i-1}-t_i+1\)，于是

\[\Phi(D_i)-\Phi(D_{i-1})\le1-t_i,\qquad\hat c_i\le(t_i+1)+(1-t_i)=2.\]

白话解释：举一次具体的 INCREMENT：计数器从 0111（十进制 7）变成 1000（十进制 8）。末尾三个 1 被复位，\(t_i=3\)；再把第四位置 1。实际代价 \(3+1=4\)。操作前有 3 个 1，操作后有 1 个 1，势能下降 2。摊还代价 \(=4+(-2)=2\)。 贵操作（翻很多位）恰好是把很多个 1 变成 0 的操作，它消耗的势能正好抵掉了多出来的实际代价。这就是"势能在替贵操作付账"。

计数器不从 0 开始时，势能法显出灵活性。设开始时有 \(b_0\) 个 1、结束时有 \(b_n\) 个 1，由 (17.3)：

\[\sum_{i=1}^n c_i=\sum_{i=1}^n\hat c_i-\Phi(D_n)+\Phi(D_0)\le 2n-b_n+b_0. \tag{17.4}\]

因为 \(b_0\le k\)，只要执行的次数 \(n=\Omega(k)\)，总代价仍是 \(O(n)\)，与初值无关。

17.4.4 三种方法的比较

方法 记账对象 优点 适用
聚合分析 整串操作的总代价 最简单，不需要设计任何东西 所有操作摊还代价相同、总代价容易数清楚时
核算法 挂在具体对象上的信用 直观，能给不同操作不同收费 能清楚指出"谁替谁付钱"时
势能法 整个结构的一个函数 \(\Phi\) 最通用，可处理复杂的结构变化与非零初态 动态表、斐波那契堆、并查集等复杂结构

17.5 动态表：可扩容数组的数学

这是本章与工程联系最紧的一节。Python 的 list、C++ 的 std::vector、Java 的 ArrayList，以及行情接收程序里的逐笔缓冲区，都是这里的动态表（dynamic table）。

17.5.1 问题与记号

事先不知道要存多少对象。表满了就分配一个更大的新表，把旧表的全部对象复制过去；删掉很多对象后，又可能想把表缩小以免浪费内存。我们希望：

  1. 插入和删除的摊还代价是 \(O(1)\)；
  2. 未用空间不超过总空间的常数比例。

记表中项数为 \(T.num\)，槽数为 \(T.size\)，装载因子（load factor）\(\alpha(T)=T.num/T.size\)（空表约定 \(size=0\)、\(\alpha=1\)）。只要 \(\alpha\) 有正的常数下界，浪费的空间就不超过常数比例。

17.5.2 只插入：满则加倍

def TABLE_INSERT(T, x):
    if T.size == 0:
        T.table = allocate(1); T.size = 1
    if T.num == T.size:                       # 表满：扩张
        new_table = allocate(2 * T.size)
        copy all items of T.table into new_table   # T.num 次基本插入
        free(T.table)
        T.table = new_table
        T.size = 2 * T.size
    insert x into T.table                     # 1 次基本插入
    T.num += 1

以"基本插入"为单位计代价（分配和释放的开销被复制开销支配）。第 \(i\) 个操作在表有空位时 \(c_i=1\)；触发扩张时 \(c_i=i\)（插入自己 1 次，再搬 \(i-1\) 项）。粗看单次最坏 \(O(n)\)，\(n\) 次 \(O(n^2)\)，但这个界不紧。

聚合分析。 只有当 \(i-1\) 恰好是 2 的幂时才扩张：

\[c_i=\begin{cases}i,&i-1\text{ 是 2 的幂},\\1,&\text{否则},\end{cases}\qquad \sum_{i=1}^n c_i\le n+\sum_{j=0}^{\lfloor\lg n\rfloor}2^j<n+2n=3n.\]

摊还代价至多 3。

核算法直观。 每插入一项收 3 美元：1 美元插入自己；1 美元存在自己身上，供下次扩张时搬自己；1 美元存在表中某个已经被搬过一次、身上没钱的老项上，供它下次搬家。设刚扩张完表大小为 \(m\)，里面有 \(m/2\) 项且都没有信用；再插 \(m/2\) 项把表填满时，每项身上恰好各有 1 美元，正好付清下一次扩张。

势能法。 我们希望势能在扩张刚完成时为 0，到表满时涨到等于项数（恰好够付搬家费）。取

\[\Phi(T)=2\cdot T.num-T.size. \tag{17.5}\]

扩张后 \(num=size/2\)，\(\Phi=0\)；扩张前 \(num=size\)，\(\Phi=num\)。表始终至少半满，故 \(\Phi\ge0\)。

  • 不扩张：\(size_i=size_{i-1}\)，\(\hat c_i=1+(2num_i-size_i)-(2(num_i-1)-size_i)=3\)。
  • 扩张：\(size_i=2size_{i-1}\)，\(size_{i-1}=num_{i-1}=num_i-1\)，于是
\[\hat c_i=num_i+\big(2num_i-2(num_i-1)\big)-\big(2(num_i-1)-(num_i-1)\big)=num_i+2-(num_i-1)=3.\]

原书图 17.3 画出了这个过程：势能在每次扩张前积累到等于项数，扩张时清零，随即因为新插入的那一项升到 2。

推导拆解：扩张那一行逐项对应如下。 实际代价 \(c_i=num_i\)：插入新项 1 次 + 搬旧项 \(num_{i-1}=num_i-1\) 次，合计 \(num_i\)。 新势能 \(\Phi_i=2num_i-size_i\)，其中 \(size_i=2size_{i-1}=2(num_i-1)\)，所以 \(\Phi_i=2num_i-2(num_i-1)=2\)。 旧势能 \(\Phi_{i-1}=2num_{i-1}-size_{i-1}\)，扩张前表是满的，\(size_{i-1}=num_{i-1}=num_i-1\)，所以 \(\Phi_{i-1}=num_i-1\)。 合起来 \(\hat c_i=num_i+2-(num_i-1)=3\)。 数值例：表大小 8、已满 8 项，插入第 9 项。实际代价 \(1+8=9\)；旧势能 \(2\times8-8=8\)；新表大小 16，新势能 \(2\times9-16=2\)；摊还代价 \(9+2-8=3\)。可以看到，贵操作的 9 单位实际代价里，有 8 单位来自之前存下的势能。

17.5.3 既插入又删除：为什么阈值是 1/4

现在还要支持 TABLE-DELETE，并在表太空时收缩。目标是同时保持装载因子有正下界、每个操作摊还代价有常数上界。

错误策略：满时加倍，低于半满就减半。 装载因子确实始终不低于 1/2，但摊还代价可以很大。设 \(n\) 是 2 的幂，先插入 \(n/2\) 项（此时 \(num=size=n/2\)），然后执行"插、删、删、插、插、删、删、插……"。第一次插入扩张到 \(n\)；两次删除又让表低于半满，收缩回 \(n/2\)；再两次插入又扩张……每次扩张或收缩代价 \(\Theta(n)\)，一共 \(\Theta(n)\) 次，总代价 \(\Theta(n^2)\)，摊还 \(\Theta(n)\)。原因是扩张后紧接着的删除太少，付不起收缩；收缩后紧接着的插入太少，付不起扩张。这种现象叫抖动（thrashing）。

正确策略：满时加倍，删除后低于 1/4 才减半。 装载因子下界变为 1/4。直观上，装载因子为 1/2 时最"健康"，势能为 0；偏离 1/2 时势能增长，到装载因子为 1 或 1/4 时势能恰好等于 \(num\)，足以支付复制；扩张或收缩之后装载因子回到 1/2，势能清零。势函数取分段形式：

\[\Phi(T)=\begin{cases}2\cdot T.num-T.size,&\alpha(T)\ge 1/2,\\[2pt] T.size/2-T.num,&\alpha(T)<1/2.\end{cases}\tag{17.6}\]

空表势能为 0，势能永远非负。\(\alpha=1\) 时 \(\Phi=num\)，可付扩张；\(\alpha=1/4\) 时 \(size=4num\)，\(\Phi=2num-num=num\)，可付收缩。

白话解释：把装载因子 \(\alpha\) 想成一个仪表，1/2 是正中间。分段势函数的形状像一个"V"：在 1/2 处为 0，往两边走都上升，走到两端（1 或 1/4）时恰好等于当前项数，够付一次整体搬家。用 \(size=16\) 检验：\(num=8\)（\(\alpha=1/2\)）时两段公式都给出 \(\Phi=0\)；\(num=16\)（满）时 \(\Phi=32-16=16\)；\(num=4\)（\(\alpha=1/4\)）时 \(\Phi=8-4=4\)。 为什么 1/2 收缩会出问题？在 V 字型的语言里，扩张后表回到 1/2，此时势能为 0；若收缩阈值也在 1/2，只删一两项就触发收缩，而这时势能几乎为 0，没有存款可付搬家费。拉开到 1/4，就保证了"每次大搬家之前，至少已经有约 \(size/4\) 次便宜操作在攒钱"。

逐情形核对（初值 \(num_0=size_0=0\)，\(\Phi_0=0\)）：

  • 插入，\(\alpha_{i-1}\ge1/2\)：与 17.5.2 完全相同，\(\hat c_i\le 3\)。
  • 插入，\(\alpha_{i-1}<1/2\)（此时不可能扩张）：若插入后仍 \(\alpha_i<1/2\)，\(\hat c_i=1+(size_i/2-num_i)-(size_i/2-(num_i-1))=0\)；若插入后 \(\alpha_i\ge1/2\)，
\[\hat c_i=1+\big(2(num_{i-1}+1)-size_{i-1}\big)-\big(size_{i-1}/2-num_{i-1}\big)=3\alpha_{i-1}size_{i-1}-\tfrac32 size_{i-1}+3<3.\]
  • 删除，\(\alpha_{i-1}<1/2\)（\(num_i=num_{i-1}-1\)）：不收缩时 \(\hat c_i=1+(size_i/2-num_i)-(size_i/2-(num_i+1))=2\)；收缩时实际代价 \(c_i=num_i+1\)（删 1 项、搬 \(num_i\) 项），且 \(size_i/2=size_{i-1}/4=num_{i-1}=num_i+1\)，
\[\hat c_i=(num_i+1)+\big((num_i+1)-num_i\big)-\big((2num_i+2)-(num_i+1)\big)=1.\]
  • 删除，\(\alpha_{i-1}\ge1/2\)：摊还代价同样有常数上界，留作练习（原书 17.4-2）。

结论：任意 \(n\) 个插入删除的实际总时间 \(O(n)\)，空间利用率不低于 1/4。

从中学到的设计原则：扩张阈值和收缩阈值之间必须留一段"缓冲带"（滞后区间，hysteresis）。阈值重合（都在 1/2 附近）就会在边界上来回翻转。这条原则远不止用于数组。

17.6 思考题选讲

原书第 17 章末有五道思考题，其中两道对量化系统尤其有启发。

17-2 让二分查找动态化。 有序数组二分查找是 \(O(\lg n)\)，但插入要挪动 \(\Theta(n)\) 个元素。改用 \(k=\lceil\lg(n+1)\rceil\) 个有序数组 \(A_0,\dots,A_{k-1}\)，\(|A_i|=2^i\)，第 \(i\) 个数组满或空由 \(n\) 的二进制第 \(i\) 位决定。查找时对每个非空数组二分，最坏 \(O(\lg^2 n)\)；插入就像二进制计数器加 1——新元素与 \(A_0,A_1,\dots\) 中连续的满数组逐级归并，直到遇到空数组。单次最坏 \(\Theta(n)\)，但摊还 \(O(\lg n)\)（每个元素每被归并一次就进入更大一级，至多 \(\lg n\) 级）。这正是日志结构合并树（LSM-tree）的原型：写入先进小的有序块，后台逐级合并成大块。RocksDB、LevelDB，以及很多时序数据库的写路径都基于这个思想。它解释了为什么这类行情库写入很快、点查略慢、后台合并（compaction）时会占用 I/O。

17-5 自组织表的竞争分析。 链表中访问第 \(k\) 个元素代价为 \(k\)。move-to-front（MTF）启发式在每次访问后把元素移到表头，代价 \(c_i=2\,\mathrm{rank}(x)-1\)（找到它花 \(\mathrm{rank}\)，往前交换 \(\mathrm{rank}-1\) 次）。以两张表之间的逆序对数 \(q_i\) 定义势能 \(\Phi=2q_i\)，可以证明 MTF 的摊还代价至多是任何启发式（哪怕预先知道全部访问序列）实际代价的 4 倍。这类"和事后最优比"的分析叫竞争分析（competitive analysis），是在线算法的标准框架。在线组合选择、执行算法中"相对于事后最优成交价的竞争比"，都是同一类思路。

其余三题：17-1 位反转计数器（FFT 的位反转置换，可做到整体 \(O(n)\)）；17-3 摊还的权重平衡树（失衡时重建最高的失衡子树，用 \(\Delta(x)=|x.left.size-x.right.size|\) 构造势能，插入删除摊还 \(O(\lg n)\)）；17-4 红黑树重构代价（只插入时每次 RB-INSERT 摊还 \(O(1)\) 次结构修改）。

17.7 量化实战：扩容、抖动与环形缓冲区

17.7.1 摊还 \(O(1)\) 不等于每次都快

动态表的分析给了一个好消息和一个坏消息。好消息是加倍扩容让 \(n\) 次插入总共只花 \(O(n)\)；坏消息是那一次扩张本身是 \(\Theta(n)\)。在研究环境里这无所谓，在交易系统的热路径上却意味着：平时每条行情处理只要几百纳秒，偶尔某一条要等整个缓冲区搬家，形成延迟尖峰（latency spike）。如果这一刻恰好是行情剧烈波动、订单最密集的时候，后果很直接——报单晚了。

所以低延迟系统通常这样处理：

  • 预分配：按历史峰值的若干倍一次性分配容量，交易时段内不再扩容（C++ 的 reserve、NumPy 的预分配数组）。
  • 环形缓冲区（ring buffer）：固定容量，满了就覆盖最老的数据。滚动窗口类指标（滚动均值、波动率、VWAP）天然只需要最近 \(W\) 个值，用环形缓冲区可以把"摊还 \(O(1)\)"变成"最坏 \(O(1)\)"。环形缓冲区的基本实现见本册第 10 章。
  • 对象池：订单、成交回报等对象预先分配好，用自由表（第 10 章）回收复用，避免运行中的内存分配。

另一个容易被忽略的点是收缩阈值。如果某个缓存或队列在阈值附近反复扩缩容，就会出现 17.5.3 的抖动。设计时让扩张阈值和收缩阈值分开（例如满了扩、低于 1/4 才缩），和交易信号里"进场阈值与出场阈值分开以避免频繁换仓"是同一个道理。

17.7.2 代码：四个实验

下面的代码做四件事：(1) 比较加倍、1.5 倍、固定增量三种扩容策略的总代价和单次最坏代价；(2) 用势函数 \(\Phi=2num-size\) 逐步核对摊还代价恒为 3；(3) 重现 1/2 收缩阈值的抖动；(4) 实现一个最坏 \(O(1)\) 的环形缓冲区滚动波动率，并与 pandas 结果对照。

import numpy as np, pandas as pd, sys

# ---------- 1. 动态表：不同扩容策略的总代价（以"基本插入"计） ----------
def simulate_insert(n, grow):
    size = num = 0
    total = worst = 0
    for _ in range(n):
        c = 1
        if num == size:                 # 表满：扩张，搬移 num 项
            c += num
            size = grow(size)
        num += 1
        total += c
        worst = max(worst, c)
    return total, worst

n = 1_000_000
for name, g in [("加倍 x2", lambda s: max(1, 2*s)),
                ("x1.5", lambda s: max(1, int(np.ceil(1.5*s)))),
                ("固定 +1024", lambda s: s + 1024)]:
    tot, worst = simulate_insert(n, g)
    print(f"{name:10s} 总代价/n = {tot/n:8.3f}   单次最坏 = {worst}")

# ---------- 2. 势能法核对：Phi = 2*num - size，摊还代价恒为 3 ----------
size = num = 0; phi_prev = 0; amort = []
for i in range(1, 70):
    c = 1
    if num == size:
        c += num; size = max(1, 2*size)
    num += 1
    phi = 2*num - size
    amort.append(c + phi - phi_prev); phi_prev = phi
print("前 12 次插入的摊还代价:", amort[:12], " 最大值:", max(amort[1:]))

# ---------- 3. 抖动：收缩阈值 1/2 与 1/4 ----------
def thrash(n, shrink_at):
    size = num = 0; total = 0
    def insert():
        nonlocal size, num, total
        c = 1
        if num == size: c += num; size = max(1, 2*size)
        num += 1; total += c
    def delete():
        nonlocal size, num, total
        num -= 1; c = 1
        if num == 0: size = 0
        elif num < shrink_at*size: c += num; size //= 2
        total += c
    for _ in range(n//2): insert()
    ops = 0
    pattern = [insert, delete, delete, insert]
    while ops < n//2:
        pattern[ops % 4](); ops += 1
    return total / n
n = 2**16
print(f"低于 1/2 就减半: 每操作平均代价 {thrash(n, 0.5):.1f}")
print(f"低于 1/4 才减半: 每操作平均代价 {thrash(n, 0.25):.2f}")

# ---------- 4. CPython list 的真实扩容次数 ----------
lst, last, reallocs = [], sys.getsizeof([]), 0
for i in range(1_000_000):
    lst.append(i)
    s = sys.getsizeof(lst)
    if s != last: reallocs += 1; last = s
print("CPython list 追加 100 万次，容量变化次数:", reallocs)

# ---------- 5. 预分配环形缓冲区：最坏 O(1) 的滚动均值/方差 ----------
class RollingRing:
    """容量固定的环形缓冲区，维护窗口内的和与平方和；每次更新恰好 O(1)。"""
    def __init__(self, window):
        self.buf = np.zeros(window); self.w = window
        self.head = 0; self.count = 0; self.s = 0.0; self.ss = 0.0
    def push(self, x):
        if self.count == self.w:                 # 满：覆盖最老的值
            old = self.buf[self.head]; self.s -= old; self.ss -= old*old
        else:
            self.count += 1
        self.buf[self.head] = x; self.s += x; self.ss += x*x
        self.head = (self.head + 1) % self.w
    def mean(self): return self.s / self.count
    def var(self):                               # 样本方差
        m = self.mean(); return (self.ss - self.count*m*m) / (self.count - 1)

rng = np.random.default_rng(17)
ret = rng.standard_t(df=4, size=5000) * 0.01      # 模拟厚尾分钟收益
rr = RollingRing(240); vols = []
for x in ret:
    rr.push(x)
    vols.append(np.sqrt(rr.var()) if rr.count == 240 else np.nan)
ref = pd.Series(ret).rolling(240).std().to_numpy()
print("与 pandas rolling std 的最大绝对误差:", np.nanmax(np.abs(np.array(vols) - ref)))

运行输出：

加倍 x2      总代价/n =    2.049   单次最坏 = 524289
x1.5       总代价/n =    3.100   单次最坏 = 699913
固定 +1024   总代价/n =  489.219   单次最坏 = 999425
前 12 次插入的摊还代价: [2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]  最大值: 3
低于 1/2 就减半: 每操作平均代价 8193.4
低于 1/4 才减半: 每操作平均代价 2.00
CPython list 追加 100 万次，容量变化次数: 86
与 pandas rolling std 的最大绝对误差: 8.326672684688674e-17

逐条解读：

  • 按比例扩容（2 倍或 1.5 倍）的平均代价都是常数。一般地，扩容倍数为 \(g>1\) 时，搬移总量约为 \(n\cdot\frac{1}{g-1}\)，摊还代价约 \(1+\frac{1}{g-1}\) 再加上尾部余量，所以 1.5 倍比 2 倍略贵、但更省内存。（推导：最后一次扩张时搬了约 \(n/g\) 项，之前各次依次约为 \(n/g^2,n/g^3,\dots\)，等比数列求和 \(\frac{n/g}{1-1/g}=\frac{n}{g-1}\)。\(g=2\) 时约 \(n\)，\(g=1.5\) 时约 \(2n\)，与输出中 2.05 和 3.10 的差异方向一致。）固定增量扩容的平均代价随 \(n\) 线性增长（这里约 489），本质上是 \(\Theta(n^2/1024)\) 的总代价。这就是"为什么不要在循环里 np.append"——它每次都重新分配并复制整个数组，比固定增量还糟。
  • 势能核对：第一次插入摊还代价是 2（空表时没有可搬的项），之后每次都恰好是 3，与推导一致。
  • 抖动实验：阈值取 1/2 时，后半段每次操作平均要搬几千项；取 1/4 后回到常数 2。
  • CPython 的 list 追加 100 万次只换了 86 次容量。它用的是约 1.125 倍的过量分配，仍是按比例扩容，所以 append 摊还 \(O(1)\)。具体倍数随 Python 版本可能不同。
  • 单次最坏代价一栏是工程上真正要关心的：2 倍扩容时最大的一次要搬 52 万项。环形缓冲区则每次更新恰好做常数次运算，没有这个尖峰。

关于环形缓冲区的数值问题：用"和与平方和"递推方差，长时间运行会累积舍入误差，并在均值远大于标准差时（例如直接对价格而非收益算方差）出现灾难性相消。生产中常用两个办法：定期（比如每 \(W\) 次更新）从缓冲区重新求和一次，平摊下来仍是 \(O(1)\)——这本身又是一个摊还论证；或者改用 Welford 递推。

本章小结

摊还分析研究一串操作的最坏总代价，平均到每个操作上；它不用概率，因此是一种最坏情况保证。聚合分析直接数总量；核算法给操作定价并把余款存在对象上；势能法用一个势函数 \(\Phi\) 记录整个结构里存下的"预付工作"，摊还代价等于实际代价加势能增量。经典结论是：带 MULTIPOP 的栈、二进制计数器、满则加倍的动态表都是摊还 \(O(1)\)；收缩阈值必须与扩张阈值拉开（1/4 对 1），否则会抖动。工程上要记住摊还界不限制单次延迟，低延迟场景要用预分配或环形缓冲区把它变成最坏界。

概念 / 结论 公式或要点
摊还代价（势能法） \(\hat c_i=c_i+\Phi(D_i)-\Phi(D_{i-1})\)
望远镜求和 \(\sum\hat c_i=\sum c_i+\Phi(D_n)-\Phi(D_0)\)，要求 \(\Phi(D_i)\ge\Phi(D_0)\)
核算法约束 任何时刻总信用 \(\sum\hat c_i-\sum c_i\ge 0\)
栈 + MULTIPOP \(\Phi=\) 栈中对象数，PUSH 摊还 2，POP/MULTIPOP 摊还 0
二进制计数器 总翻转 \(<2n\)；\(\Phi=\) 1 的个数，摊还 \(\le 2\)；非零初值总代价 \(\le 2n-b_n+b_0\)
动态表（只插入） \(\Phi=2num-size\)，插入摊还 3，\(\alpha\ge1/2\)
动态表（插入 + 删除） 满则加倍、\(<1/4\) 才减半，分段势函数 (17.6)，\(\alpha\ge1/4\)
抖动 扩缩阈值重合导致 \(\Theta(n)\) 摊还；设计上要留滞后区间
工程含义 摊还 \(O(1)\ne\) 最坏 \(O(1)\)；热路径用预分配/环形缓冲区

练习

基础

  1. 用聚合分析、核算法、势能法三种方法分别证明：第 \(i\) 个操作在 \(i\) 为 2 的幂时代价为 \(i\)、否则为 1，则摊还代价为 \(O(1)\)。（原书 17.1-3、17.2-2、17.3-2。提示：核算法每次收 3；势能法取 \(\Phi_0=0\)、\(\Phi_i=2i-2^{\lfloor\lg i\rfloor+1}\)（\(i\ge1\)），它在 \(i\) 为 2 的幂时归零、其间每步涨 2，可验证摊还代价不超过 3。）
  2. 说明为什么给栈加上 MULTIPUSH 后 \(O(1)\) 摊还界不再成立；为什么给计数器加上 DECREMENT 后 \(n\) 次操作可达 \(\Theta(nk)\)。（原书 17.1-1、17.1-2。）
  3. 栈的大小永不超过 \(k\)，每执行 \(k\) 个操作就把整个栈拷贝一次作备份。证明含拷贝在内 \(n\) 个操作总代价 \(O(n)\)。（原书 17.2-1。提示：每个操作多收 1 美元存起来。）
  4. 用两个栈实现队列，使 ENQUEUE、DEQUEUE 摊还 \(O(1)\)。用势能法证明。（原书 17.3-6。提示：\(\Phi=2\times\) 入栈中的元素数。）
  5. 在 17.7.2 的实验 1 中，若扩容倍数为 \(g\)，推导 \(n\) 次插入的总搬移量的上界。（提示：最后一次扩张前容量约 \(n/g\)，前面构成等比数列，总量 \(<\frac{n}{g-1}\)。）

进阶

  1. 补全 \(\alpha_{i-1}\ge1/2\) 时 TABLE-DELETE 的摊还分析，证明摊还代价有常数上界。（原书 17.4-2。提示：此时删除不会触发收缩，分 \(\alpha_i\ge1/2\) 与 \(\alpha_i<1/2\) 两种情况。）
  2. 把收缩规则改为"装载因子低于 1/3 时把大小乘以 2/3"，用 \(\Phi=|2\cdot T.num-T.size|\) 证明删除摊还代价有常数界。（原书 17.4-3。）
  3. 设计一个数据结构，支持 INSERT 与 DELETE-LARGER-HALF（删除当前最大的 \(\lceil|S|/2\rceil\) 个元素），使任意 \(m\) 个操作总时间 \(O(m)\)。（原书 17.3-7。提示：无序数组 + 线性时间选择中位数，势能取元素个数的常数倍。）
  4. 思考题 17-2：实现"多层有序数组"的 INSERT 并证明摊还 \(O(\lg n)\)；讨论为什么 DELETE 难做，以及 LSM-tree 用"墓碑标记 + 合并时清理"如何回避它。
  5. 环形缓冲区滚动方差每 \(W\) 次更新就从头重新求和一次。证明每次更新的摊还代价仍是 \(O(1)\)，并说明它的单次最坏代价是多少。若要求单次最坏也是 \(O(1)\)，可以怎样把重算工作分摊到每次更新中做一点？（提示：增量地维护第二套累加器。）

原书推荐习题：17.1-3 / 17.2-2 / 17.3-2（同一问题三种方法对照），17.3-6，17.4-2，17.4-3，思考题 17-2、17-5。

原书对照

本章小节 原书章节 PDF 页码
17.1 为什么需要摊还分析 第 17 章导言 p.472–473
17.2 聚合分析 17.1 Aggregate analysis p.473–477
17.3 核算法 17.2 The accounting method p.477–480
17.4 势能法 17.3 The potential method p.480–484
17.5 动态表 17.4 Dynamic tables（17.4.1 扩张，17.4.2 扩张与收缩） p.484–492
17.6 思考题选讲 Problems 17-1 ～ 17-5 p.493–498
本章注记 Chapter notes p.499