假設程式要讀取數量事先未知的數值,之後又要能按位置直接取出某個值。陣列提供了對位置 的直接存取,但固定大小的陣列無法保證容納未知的後續輸入。一開始就配置極大的陣列會浪費記憶體,而且仍然有上限。動態陣列保留直接存取的表示方式,在需要時更換底層儲存空間。
更換空間可能很昂貴,因為要複製原有的值。因此,真正值得問的是一連串操作的總成本:能否安排昂貴的更換時機,令多次尾端加入的總成本只呈線性增長?答案取決於容量增長規則。如果刪除還要回收空間,縮容門檻也同樣重要。
把序列與儲存空間分開
定義 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,複製 個元素,這時留下較多備用空間。若在開頭插入,每次還要移動全部既有元素;十次共有 次移動, 次則有 次移動。幾何擴容不會消除這些移動。