假设程序要读取数量事先未知的数值,之后还要能够按位置直接取出某个值。数组提供了对位置 的直接访问,但固定大小的数组无法保证容纳未知的后续输入。一开始就分配极大的数组会浪费内存,而且仍然存在上限。动态数组保留直接访问的表示方式,在必要时更换底层存储空间。
更换空间可能很昂贵,因为要复制原有的值。因此,真正值得问的是一连串操作的总成本:能否安排昂贵的更换时机,使多次尾部追加的总成本只呈线性增长?答案取决于容量增长规则。如果删除还要回收空间,缩容阈值也同样重要。
将序列与存储空间分开
定义 11.1.1
(长度、容量与所表示的序列)
动态数组存储底层数组 、长度 和容量 ,满足
它的抽象序列恰好由 组成。其余 个位置是备用空间,不是额外的序列元素。索引有效的充要条件是 。
append(x) 在尾部追加 。pop() 删除并返回最后一项,前提是序列非空。按索引读取或替换已有项,不改变长度和容量。
最初序列为空,容量为 1。如果追加时 ,将新值写入 ,再把 加一。如果 ,先分配容量 ,依次复制 个有效元素,换成新空间,然后才追加新值。容量倍增是实现规则,不改变调用者所见的序列操作。
复制必须保持顺序。复制后,原本索引为 的元素仍在索引 ,所以所有已有的索引查询都有相同答案。新值成为第 项,新长度为 。搬移空间改变表示方式,而追加按照约定改变抽象序列。
先选择成本模型,再开始计数
下面的分析为每次 append 或 pop 的普通常数工作收取一个单位,每复制一个有效元素再收取一个单位。因此
这是明确的算法成本模型,不是逐条机器指令的精确计数。比较和元数据更新需要常数时间。模型不计算新分配中尚未使用位置的初始化成本。如果分配会用线性时间初始化全部 个位置,下文的渐近界仍然成立:除了常数大小的边界情况,每次调整后的容量都不超过本次所复制有效元素数目的某个常数倍。表格中的精确常数则只适用于上述模型。
例题 11.1.2
(第九次追加很昂贵,前九次总成本却是线性级)
从长度 0、容量 1 开始,依次在尾部追加 1 至 9。
| 追加的值 | 之后的长度 | 之后的容量 | 复制元素数 | 操作成本 |
|---|---|---|---|---|
总共九单位普通工作,加上 次元素复制,成本为 24。仅第九次追加就花费 9。因此,尾部追加具有常数摊还时间,并不表示每次调用的最坏成本都是常数。
将整串追加操作的成本相加
命题 11.1.3
(倍增策略的线性总成本)
从容量为 的空动态数组出发,采用倍增规则,且没有删除操作。在上述成本模型下,每一串 次追加的总成本都小于 。
证明
(几何级数的复制量有线性总和)
考虑从初始空数组开始的 次追加。如果发生扩容,所复制的元素数依次为
其中 :复制 个元素发生在插入第 项时。总复制成本为
加上 单位普通工作,总成本小于 。如果完全没有扩容,这个界也直接成立。这是对每一串长度为 的追加操作都成立的确定性界,与存储的数值无关。
摊还界通过为每次操作分配有界的平均收费,限制整串操作的总成本。昂贵操作的成本可以由前后多次比较便宜的操作共同承担。
概念视角算法
把代币放在元素上
每次收费 3 单位:一单位支付写入,两单位留在元素上。容量 的数组满时,后写入的 个元素共带 单位,正好付清复制 个元素; 时该元素带 2 单位。余额从不为负,故 次追加至多 。
常见错误
(摊还成本不是平均情形成本)
把摊还常数理解为对随机输入取平均后的常数,是错误的。界 对每一串长度为 的追加序列都成立,不涉及概率;被平均的是同一串固定序列中各个操作的成本。反过来,这个界也不表示每次调用都便宜:上表中的第九次追加成本为 9。
容量倍增也限制了备用空间。如果只有追加而且 ,就有 :刚扩容后,新容量为旧长度的两倍,新长度则比旧长度多一。两次扩容之间,容量固定而长度增加。
反例模式
每次只增加一格,就失去线性总成本界
假设数组满时,容量从 增加到 。从容量 1 开始,第 2 至第 次追加分别复制 个元素,总和为
因此总追加成本为 ,摊还成本为 。每个状态仍满足 ,每个索引查询也正确。功能不变量保持了,但容量策略没有达到性能目标。每次增加固定数量的位置,也有相同的渐近问题。
如果使用固定整数增长因子 ,复制总和则为 。因子越大,刚扩容后的备用空间通常越多。这是空间与复制量之间的取舍,并不意味着应该无限制地分配。
缩容需要与扩容阈值保持距离
如果数组从不缩小,删除几乎所有值后,可能仍用极大的分配空间存放极少元素。一个自然的初步想法是:长度降到容量一半时,立刻将容量减半。但如果同时采用满时倍增,两条规则可能反复撤销对方刚完成的工作。
反例模式
半满就缩容,可能立即又要扩容
从长度和容量均为 的满数组开始。追加一次:复制 个元素,长度变为 ,容量为 。再删除一次:长度回到 ,恰好为容量的一半。上述缩容规则又复制 个元素,回到容量 。
现在可以重复同一对追加、删除操作。每一对都复制 个元素,长度却没有任何持久变化。这并不是只选择了一个不公平的昂贵起点:先用 次追加建立满数组,再将该操作对重复 次,总共 次更新就至少造成 次复制。总成本相对于操作串长度呈二次增长。
更好的方法是保留扩容规则,只在一次 pop 之后,新长度满足 且容量大于 1 时才缩容。将容量减半,但不低于 1。因为容量是二的幂,代码使用 n <= C // 4。通常缩容后,使用率回到一半;之后继续追加或继续删除,都要经过一段变化才会触发下一次调整。
这种将满容量与四分之一满阈值分开的做法,常称为滞回(hysteresis)。它的数学作用是迫使两次昂贵调整之间累积足够多的操作。说它“通常有帮助”,弱于对每一串混合操作证明成本界;下一个论证才给出这项保证。
用势能同时核算扩容与缩容
为每个状态指定非负势能
半满时势能为零。接近满或接近空时,势能都会上升,为相应的未来容量调整积累额度。初始状态 的势能为 。
命题 11.1.4
(四分之一满缩容规则的常数摊还成本)
从容量为 的空动态数组出发。追加遇到已满的数组时,容量加倍。每次删除之后,当且仅当容量大于 并且新长度至多为 时,容量减半。则每一串共 次的有效追加与删除操作,总实际成本至多为 。
证明
(同时核算追加与删除的势能)
对于从 变为 的一次操作,定义摊还收费
对于至少为 4 的容量,下表包含所有调整情况及普通操作。在半满位置,势能为零,跨过中点的操作也满足表中的界。
| 操作 | 实际成本 | 势能变化 | 摊还收费 |
|---|---|---|---|
| 不扩容的追加,位于上半区 | |||
| 不扩容的追加,位于下半区 | |||
| 容量 已满时追加 | |||
| 不缩容的删除,仍在上半区 | |||
| 不缩容的删除,进入或位于下半区 | |||
| 删除并从容量 缩容 |
扩容前的势能为 。新长度为 、新容量为 ,新势能为 2,释放的额度足够支付旧元素的复制。
对于 的缩容,删除后第一次达到阈值的长度恰为 。删除前的长度为 :之前每次操作完成后,都仍高于缩容阈值。旧势能为 。缩容后容量为 ,使用率为一半,势能为零。操作复制 个有效元素,因此摊还收费为 2。
容量 1 和 2 只有常数个边界状态,直接代入也能得到追加收费最多 3、删除最多 2。特别地,从容量 2 删除最后一项,缩到容量 1,摊还收费为 。
对于 次更新,势能差连续相消:
因为 。所以,在这项策略下,每一串有效的追加、删除混合操作都有常数摊还更新成本。
证明透视
为什么两个阈值之间的距离能够支付缩容
这个势能有两种斜率。在上半区,每次追加使势能上升 ,所以从半满到全满的 次追加,恰好存下复制 个元素所需的 单位。在下半区,每次删除使势能上升 ,所以从半满到缩容阈值的 次删除,存下复制这 个元素所需的 单位。
证明依赖策略的一条性质:每次操作完成后,长度都大于 ( 除外)。因此触发缩容的那次删除必定从长度 开始,此时存储的势能为 。再加上收费 ,就足以支付实际成本 ;缩容后数组恰好半满、势能为零,下一次调整无论朝哪个方向都相距很远。
如果没有这个距离,论证就不成立。假如在半满时缩容,上一个反例中的删除会从 (势能 )变为 (势能 ),实际成本为 ,摊还收费就是 ,任何常数都无法界住它。
摊还收费可以为负,例如表中的 ,表示释放先前积累的势能。实际操作仍然具有正成本。势能只是分析工具;实现不需要真的存储或花费一笔代币余额。
例题 11.1.5
(实际成本为五的删除,摊还收费可以是二)
按照前面的追加序列到达长度 9、容量 16,再连续删除四次,过程中没有缩容,最后到达长度 5。状态 的势能为 。
再删除一次,新长度为 4,触发缩容到容量 8。复制四个有效元素,实际成本为 5。新状态 的势能为零,所以摊还收费为 。
四个被复制的元素保持原有索引与顺序。已经删除的第五项不会被复制。缩容改变备用空间,不改变保留下来的抽象序列。
例题 11.1.6
(经过最小容量的混合操作序列)
从 出发,。依次追加 、、,再删除三次,全程采用四分之一满规则。
| 操作 | 之后的状态 | 实际成本 | 势能 | 摊还收费 |
|---|---|---|---|---|
| 追加 | ||||
| 追加 (已满:复制 1 个) | ||||
| 追加 (已满:复制 2 个) | ||||
| 删除(,不缩容) | ||||
| 删除(:缩容,复制 1 个) | ||||
| 删除(:缩容,复制 0 个) |
实际成本合计 。摊还收费合计 ,两者相等,因为序列结束时回到起始状态,,相消恒等式因而给出相等。最后一次删除是边界情形:它使序列变空,并把容量 2 缩为容量 1,而不需要复制任何元素。如果再对这个空数组删除,会抛出 IndexError,长度和容量都不变。
每次操作完成后,如果 ,这项策略也保证 ,否则早已触发缩容。通常的非空缩容后有 。空状态的容量为 1,因此存储空间保持为 。调整期间,旧空间和新空间会短暂共存,但两者的总容量仍不超过 的某个常数倍。
用小型实现明确表达策略
下面的 Python 类用固定长度的列表作为底层空间,自行处理容量调整。copied 计算有效元素的搬移次数,work 计算上述模型的成本。这些计数器用于解释算法,不是测量分配器或解释器的运行时间。索引检查依据长度,而不是容量。私有的调整方法只会接收足够容纳全部有效元素的容量。
class DynamicArray:
def __init__(self):
self.data = [None]
self.size = 0
self.copied = 0
self.work = 0
@property
def capacity(self):
return len(self.data)
def _resize(self, capacity):
replacement = [None] * capacity
for i in range(self.size):
replacement[i] = self.data[i]
self.copied += self.size
self.work += self.size
self.data = replacement
def append(self, value):
if self.size == self.capacity:
self._resize(2 * self.capacity)
self.data[self.size] = value
self.size += 1
self.work += 1
def pop(self):
if self.size == 0:
raise IndexError("pop from empty dynamic array")
self.size -= 1
value = self.data[self.size]
self.data[self.size] = None
self.work += 1
if self.capacity > 1 and self.size <= self.capacity // 4:
self._resize(self.capacity // 2)
return value
def __getitem__(self, index):
if not 0 <= index < self.size:
raise IndexError("index outside sequence")
return self.data[index]
def __setitem__(self, index, value):
if not 0 <= index < self.size:
raise IndexError("index outside sequence")
self.data[index] = value
在这个模型中,按索引读取和替换的最坏时间为 。尾部追加和删除的摊还时间为 ,但触发调整的一次调用可以花费 。如果在数组开头插入,仍然要移动后面的全部元素;容量调整的证明不会使这个操作变为常数时间。比较数据结构时,必须同时说明操作、成本模型以及成本界的种类。
常见错误
(容量不是长度)
在 Python 类中,len(self.data) 是容量。长度为 5、容量为 8 时,它返回 8,而三个备用位置存放的 None 并不是序列元素。用它检查索引会接受索引 6,并读取到备用位置。有效性必须由 size 字段决定。
练习与详解
快速检查
(1. 比较整串操作与单次成本)
从初始状态开始,八次和九次尾部追加的总成本分别是多少?为什么这些数字支持摊还界,却不能证明每次追加的最坏成本都是常数?
解答 · 解答 1
八次成本为 ;九次成本为 。仅第九次就花费 。两个总成本都小于调用次数的三倍,但最后一次的成本随着之前的满容量增长。
快速检查
(2. 精确比较两种增长规则)
从容量 1 开始追加六个值。分别在容量每次加一和每次倍增的规则下,计算复制元素数和总成本。
解答 · 解答 2
每次加一会复制 个元素,成本为 。倍增会复制 个元素,成本为 。这是指定模型下的计数,不是某种编程语言的实测时间。
快速检查
(3. 备用空间不是序列的一部分)
数组长度为 5、容量为 8。索引 6 有效吗?替换第 2 项是否改变长度或容量?请根据抽象不变量解释。
解答 · 解答 3
索引 6 无效,因为有效索引是 0 至 4。备用位置虽然实际存在,却没有表示序列项。替换第 2 项只改变一个已有值,长度仍为 5,容量仍为 8。有效性取决于长度,而不是已分配位置的数目。
快速检查
(4. 计算缩容操作的势能收费)
在长度 5、容量 16 时,按照四分之一满规则删除一次。给出新长度、容量、复制数、实际成本、前后势能和摊还收费。
解答 · 解答 4
新长度为 4,触发容量缩到 8。复制四个保留的值,实际成本为 5。势能从 变为 ,所以摊还收费为 。
快速检查
(5. 诊断半满缩容策略)
从长度和容量均为 8 的满状态开始,如果采用倍增和半满缩容,一对追加、删除操作会发生什么?为什么将准备操作也计入,仍不能保证常数摊还成本?
解答 · 解答 5
追加将八个值复制到容量 16;删除回到长度 8,再将八个值复制回容量 8。这对操作成本为 ,而长度和容量回到原状。一般构造中,先用 次追加建立满容量,再执行 对操作,总共只有 次更新,却有 次复制。计入准备工作也无法恢复线性总成本界。
快速检查
(6. 改变增长因子,区分成本取舍)
从容量 1 开始追加十个值,不进行删除。比较倍增和增至三倍的最终容量及复制数。如果每次改在开头插入,还会有什么额外成本?
解答 · 解答 6
倍增最终容量为 16,复制 个元素。增至三倍最终容量为 27,复制 个元素,此时保留了更多备用空间。如果在开头插入,每次还要移动全部已有元素;十次共有 次移动, 次则有 次移动。几何扩容不会消除这些移动。