我正在讀「編程珠璣」，我的解決方案的一個解釋真的很困惑 - 在第1列恆定時間通過使用更多的空間編程珍珠初始化 - 列1
的問題是問題9 ：當使用位圖數據來表示一組整數時，第一階段將該組初始化爲空。但初始化空間本身可能需要很長時間。 演示如何通過設計一種技術在第一次訪問矢量時初始化矢量條目以避免此問題。
的答案是： 數據 [0 ... N-1]，可以與包含在兩個附加n元素向量的簽名 實現，從和初始化向量的效果，整數top。如果元素 數據 [I]被初始化，然後從 [I] < 頂部和到 [* *從[I]] = 1。因此從是一個簡單的 簽名，到和頂部一起確保從不會意外地被記憶的隨機內容簽署。
我已經讀了幾次這個答案。我不明白。
有人可以解釋它嗎？
感謝，
此頁幫了我：http://comments.gmane.org/gmane.comp.programming.algogeeks/30667
但是，讓我看看，如果我能解釋它。
基本上問題是：如果矢量足夠大，初始化一個矢量爲所有0都需要花費不少數量的時間。那麼，我們如何通過使用更多空間來避免初始化爲0？即我們如何區分這個向量中的隨機數據與我們故意放在那裏的數據？
本特利的解決方案是使用與數據矢量和「top」相同大小的「from」（一張圖）和「to」（一個簽名[實際上只是對from of index的反向映射）這是迄今爲止數據數組中元素的數量。如下所述，重要的是from[i] < top。
使用從溶液中例如： 我們聲明的數據陣列和設置元件的數量是零：
top = 0
data = int array of integers of size 1,000,000
(all random values since we did not initialize it)
在索引1（I = 1在這種情況下）插入的元件。但是現在我們怎麼知道這不是一個隨機值？我們使用地圖和簽名。 「from」的索引等於數據的索引。
from[i] = top
to[top] = i
data[i] = 0 (I don't think it matters whether you set it to 0 or your intended value of 3)
top++ (top is now 1)
所以你可能會說什麼，如果to[from[i]] == i偶然。那麼既然我們說from[i] < top，這是不可能的。
檢查以下兩種情況：
A）有沒有尚未插入到數據陣列（即元素頂部= 0） 這意味着from[i] < 0這不是有效的數組索引。所以這是不可能的。
B）插入了一個元素（即top> 0，假設它是1） 由於from[i] < top =>from[i] = 0。但是，我們在數據數組中插入了一個元素，所以我們明確地設置了to[from[i]] = i。
休止符遵循頂部= 2，...，N
HTH
我發現下面的鏈接帖子是在瞭解一定時間初始化伎倆背後的想法非常有幫助。
鏈接：http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/
希望helps-