假設程式要讀取數量事先未知的數值,之後又要能按位置直接取出某個值。陣列提供了對位置 的直接存取,但固定大小的陣列無法保證容納未知的後續輸入。一開始就配置極大的陣列會浪費記憶體,而且仍然有上限。動態陣列保留直接存取的表示方式,在需要時更換底層儲存空間。
更換空間可能很昂貴,因為要複製原有的值。因此,真正值得問的是一連串操作的總成本:能否安排昂貴的更換時機,令多次尾端加入的總成本只呈線性增長?答案取決於容量增長規則。如果刪除還要回收空間,縮容門檻也同樣重要。
把序列與儲存空間分開
定義 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,因此儲存空間維持在 。調整期間,舊配置和新配置會短暫共存,但兩者的總容量仍不超過 的某個常數倍。
用便宜的更新支付昂貴的重新配置
在三種儲存策略下重播同一串加入與移除操作。分清有效元素與備用容量,以及實際工作量與攤銷費用。
切換策略會從空陣列重播完全相同的操作紀錄,不會改變抽象序列。
目前底層儲存空間: 有效大小 n=4; 容量 C=8.
[0] 1
有效元素
最後一次更新中複製
[1] 2
有效元素
最後一次更新中複製
[2] 3
有效元素
最後一次更新中複製
[3] 4
有效元素
最後一次更新中複製
[4] ·
備用位置
[5] ·
備用位置
[6] ·
備用位置
[7] ·
備用位置
索引探針 i=3: 有效序列索引; A[3]=4.
各次更新的工作量
圓點實線表示實際成本;方點虛線表示攤銷費用。下表列出全部數值,包括負的攤銷費用。
| 更新次序 | 操作 | 值 | 大小/容量:之前 → 之後 | 容量調整 | 複製元素數 | 實際成本 | 勢能:之前 → 之後 | 攤銷費用 | 累計成本 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 末端加入 | 1 | (0,1) → (1,1) | 不調整容量 | 0 | 1 | 0.5 → 1 | 1.5 | 1 |
| 2 | 末端加入 | 2 | (1,1) → (2,2) | 擴大 | 1 | 2 | 1 → 2 | 3 | 3 |
| 3 | 末端加入 | 3 | (2,2) → (3,4) | 擴大 | 2 | 3 | 2 → 2 | 3 | 6 |
| 4 | 末端加入 | 4 | (3,4) → (4,4) | 不調整容量 | 0 | 1 | 2 → 4 | 3 | 7 |
| 5 | 末端加入 | 5 | (4,4) → (5,8) | 擴大 | 4 | 5 | 4 → 2 | 3 | 12 |
| 6 | 末端加入 | 6 | (5,8) → (6,8) | 不調整容量 | 0 | 1 | 2 → 4 | 3 | 13 |
| 7 | 末端加入 | 7 | (6,8) → (7,8) | 不調整容量 | 0 | 1 | 4 → 6 | 3 | 14 |
| 8 | 末端加入 | 8 | (7,8) → (8,8) | 不調整容量 | 0 | 1 | 6 → 8 | 3 | 15 |
| 9 | 末端加入 | 9 | (8,8) → (9,16) | 擴大 | 8 | 9 | 8 → 2 | 3 | 24 |
| 10 | 末端移除 | 9 | (9,16) → (8,16) | 不調整容量 | 0 | 1 | 2 → 0 | −1 | 25 |
| 11 | 末端移除 | 8 | (8,16) → (7,16) | 不調整容量 | 0 | 1 | 0 → 1 | 2 | 26 |
| 12 | 末端移除 | 7 | (7,16) → (6,16) | 不調整容量 | 0 | 1 | 1 → 2 | 2 | 27 |
| 13 | 末端移除 | 6 | (6,16) → (5,16) | 不調整容量 | 0 | 1 | 2 → 3 | 2 | 28 |
| 14 | 末端移除 | 5 | (5,16) → (4,8) | 縮小 | 4 | 5 | 3 → 0 | 2 | 33 |
精確帳目恆等式: 33 = 32.5 + 0.5 − 0.
檢查界限:加入 ≤ 3;移除 ≤ 2。 有限操作紀錄中的檢查,並非對所有可能紀錄的證明。這裏的一般界限只適用於四分之一縮小策略。
- 最後一次實際成本
- 5
- 總複製元素數
- 19
- 總實際成本
- 33
- 每次更新的實際平均成本
- 33/14
- 目前勢能
- 0
- 攤銷費用總和
- 32.5
- 已記錄費用符合界限
- 是
- 策略具有一般界限證明
- 是
加倍/四分之一時縮小. n=4, C=8; 總實際成本: 33; 索引探針 i=3: 有效序列索引, 4. 策略具有一般界限證明: 是.
為何這套帳目成立
序列恰好佔用容量 C 中索引 0 至 n−1。備用位置雖已配置儲存空間,卻不是序列元素。每次更新的成本是一個單位,加上每個被複製的有效元素各一單位。移除先刪去最後元素,再複製餘下元素;加入則先複製舊元素,再寫入新元素。
容量加倍時,九次加入共複製 1+2+4+8=15 個元素,總成本是 9+15=24。第九次加入本身便要 9 個單位。界限限制整段操作的總成本,不是每次操作的實際成本,也不是對隨機輸入取平均。
當 2n≥C 時取 Φ(n,C)=2n−C,否則取 Φ(n,C)=C/2−n。初始 Φ(0,1)=1/2。定義 ĉ=c+Φ之後−Φ之前,勢能差便在相加時抵消:總實際成本 = Σĉ+1/2−Φ最後。四分之一縮小規則保證每次加入 ĉ≤3、每次移除 ĉ≤2。負的費用是合法帳目,不表示實際工作量為負。
在加入九個、再移除五個的例子中,最後一次移除把 (n,C)=(5,16) 改為 (4,8)。它複製四個餘下元素,所以 c=5;勢能則由 3 降至 0,因此攤銷費用是 2。擴大與縮小門檻之間的空隙,讓下一次容量調整前有很多便宜的更新。
若在二分之一時縮小,這個空隙便消失。加入八個元素後反覆加入及移除,會在同一容量邊界兩邊來回。這段 24 次更新在二分之一策略下成本為 159,在四分之一策略下則為 39。容量每次只加一也沒有常數攤銷界限:六次加入複製 1+2+3+4+5 個元素,成本 21;加倍策略只需 13。
n=5、C=8 時,可以讀取索引 6 嗎?
不可以。容量表示儲存空間存在,序列索引卻必須滿足 0≤i<n。索引 6 是備用位置,沒有序列值。選取備用容量例子後,把探針移至索引 4,便可讀取最後一個有效值 5。
這個精確的單位成本模型計算被搬移的有效元素,不量度記憶體配置時間或備用位置初始化。本圖處理末端加入、末端移除及索引,不模擬中間插入。三種策略都顯示同一勢能恆等式,但每次更新的常數界限只對四分之一策略有證明。
顯示上限為 64 次更新及 32 個有效元素。這是本圖的限制,不是資料結構的限制。
以小型實作明確表達策略
以下 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,複製 個元素,這時留下較多備用空間。若在開頭插入,每次還要移動全部既有元素;十次共有 次移動, 次則有 次移動。幾何擴容不會消除這些移動。