演算法/隨機化
當人們試圖用確定性演算法解決難題時，它們會被推到極限，因此，一個有用的加速計算的技術是隨機化。在隨機演算法中，演算法可以訪問一個隨機源，可以想象成在計算過程中拋硬幣。根據拋硬幣的結果，演算法可能會分叉它的計算路徑。
隨機演算法主要有兩種型別：拉斯維加斯演算法和蒙特卡羅演算法。在拉斯維加斯演算法中，演算法可以使用隨機性來加速計算，但演算法必須始終返回輸入的正確答案。蒙特卡羅演算法沒有後者的限制，也就是說，它們可以返回錯誤的返回值。但是，返回錯誤返回值的機率必須很小，否則該蒙特卡羅演算法就沒有用。
許多近似演算法使用隨機化。
在介紹隨機技術之前，我們將從一個確定性問題開始，它會引導到一個使用隨機化的問題。假設你有一個無序的數值陣列，你想找到
- 最大值，
- 最小值，以及
- 中位數。
用我們以前一位計算機科學教授的話來說，“你怎麼做呢？”
首先，找到最大元素相對簡單
// find-max -- returns the maximum element
function find-max(array vals[1..n]): element
let result := vals[1]
for i from 2 to n:
result := max(result, vals[i])
repeat
return result
end
將result初始設定為也可以，但這對max函式來說是一個無用的呼叫，因為第一個比較的元素將被設定為result。透過將result初始化為這樣的值，函式只需要進行n-1次比較。（此外，在支援超程式設計的語言中，資料型別可能不是嚴格的數字，可能沒有好的方法來分配；使用vals[1]是型別安全的。）
可以透過呼叫min函式而不是max函式來執行類似的查詢最小元素的例程。
但是現在假設你想同時找到最小值和最大值；這裡有一個解決方案
// find-min-max -- returns the minimum and maximum element of the given array
function find-min-max(array vals): pair
return pair {find-min(vals), find-max(vals)}
end
因為find-max和find-min都對max或min函式進行了n-1次呼叫（當vals有n個元素時），find-min-max中進行的總比較次數為.
但是，有一些冗餘的比較。可以透過將min和max函式“編織”在一起來消除這些冗餘。
// find-min-max -- returns the minimum and maximum element of the given array function find-min-max(array vals[1..n]): pair let min := let max := if n is odd: min := max := vals[1] vals := vals[2,..,n] // we can now assume n is even n := n - 1 fi for i:=1 to n by 2: // consider pairs of values in vals if vals[i] < vals[i + 1]: let a := vals[i] let b := vals[i + 1] else: let a := vals[i + 1] let b := vals[i] // invariant: a <= b fi if a < min: min := a fi if b > max: max := b fi repeat return pair {min, max} end
這裡，我們只迴圈次，而不是n次，但每次迭代我們進行三次比較。因此，進行的比較次數為，比原始演算法快了。
只需要進行三次比較，而不是四次，因為根據構造，總是滿足 。 （在 "if" 的第一部分，我們實際上更確切地知道 ，但在 else 部分，我們只能得出結論 。）利用這個性質，我們可以注意到，a 不需要與當前最大值比較，因為 b 已經大於或等於 a，類似地，b 不需要與當前最小值比較，因為 a 已經小於或等於 b。
在軟體工程中，使用庫和編寫自定義演算法之間存在著矛盾。在本例中，為了獲得更快的 查詢最小值最大值 例程，沒有使用 min 和 max 函式。在實際程式中，這種操作可能不會成為瓶頸：但是，如果測試表明該例程應該更快，則應該採用這種方法。通常，重用庫的解決方案總體上優於編寫自定義解決方案。諸如開放式實現和麵向方面程式設計之類的技術可以幫助管理這種爭論，從而實現兩全其美，但無論如何，這是一個有用的區別，值得認識到。
查詢中位數
[edit | edit source]最後，我們需要考慮如何找到中位數值。一種方法是對陣列進行排序，然後從位置提取中位數vals[n/2]:
// find-median -- returns the median element of vals function find-median(array vals[1..n]): element assert (n > 0) sort(vals) return vals[n / 2] end
如果我們的值不是足夠接近的值（或者不能透過基數排序進行排序），上面的排序將需要 步。
但是，可以在 時間內提取第 n 個順序統計量。關鍵在於消除排序：我們實際上並不需要對整個陣列進行排序才能找到中位數，因此對整個陣列進行排序會造成一些浪費。我們將使用的一種技術是隨機性。
在介紹非排序 查詢中位數 函式之前，我們介紹一種稱為 分割槽 的分治式操作。我們想要的是一個例程，它在陣列中找到一個隨機元素，然後將陣列分成三個部分
- 小於或等於隨機元素的元素；
- 等於隨機元素的元素；以及
- 大於或等於隨機元素的元素。
這三個部分由兩個整數表示：j 和 i。分割槽是在陣列中“就地”執行的
// partition -- break the array three partitions based on a randomly picked element
function partition(array vals): pair{j, i}
請注意，當選取的隨機元素在陣列中實際出現三次或更多次時，所有三個分割槽中的條目都可能與隨機元素具有相同的值。雖然這種操作可能聽起來並不實用，但它具有一個可以利用的強大特性：當分割槽操作完成後，隨機選取的元素在陣列中的位置將與對陣列進行完全排序後相同！
這種特性可能聽起來並不那麼強大，但請回想一下 查詢最小值最大值 函式的最佳化：我們注意到，透過先將陣列中的元素成對選取並相互比較，我們可以減少所需的總比較次數（因為當前的最小值和最大值只需要與每個值比較一次，而不是兩次）。這裡也使用了類似的概念。
雖然 分割槽 的程式碼並不神奇，但它有一些棘手的邊界情況
// partition -- break the array into three ordered partitions from a random element
function partition(array vals): pair{j, i}
let m := 0
let n := vals.length - 2 // for an array vals, vals[vals.length-1] is the last element, which holds the partition,
// so the last sort element is vals[vals.length-2]
let irand := random(m, n) // returns any value from m to n
let x := vals[irand]
swap( irand,n+ 1 ) // n+1 = vals.length-1 , which is the right most element, and acts as store for partition element and sentinel for m
// values in vals[n..] are greater than x
// values in vals[0..m] are less than x
while (m <= n ) // see explanation in quick sort why should be m <= n instead of m < n in the 2 element case,
// vals.length -2 = 0 = n = m, but if the 2-element case is out-of-order vs. in-order, there must be a different action.
// by implication, the different action occurs within this loop, so must process the m = n case before exiting.
while vals[m] <= x // in the 2-element case, second element is partition, first element at m. If in-order, m will increment
m++
endwhile
while x < vals[n] && n > 0 // stops if vals[n] belongs in left partition or hits start of array
n—endwhile
if ( m >= n) break;
swap(m,n) // exchange vals[n] and vals[m]
m++ // don't rescan swapped elements
n—endwhile
// partition: [0..m-1] [] [n+1..] note that m=n+1
// if you need non empty sub-arrays:
swap(m,vals.length - 1) // put the partition element in the between left and right partitions
// in 2-element out-of-order case, m=0 (not incremented in loop), and the first and last(second) element will swap.
// partition: [0..n-1] [n..n] [n+1..]
end
我們可以使用 分割槽 作為一般 查詢 操作的子例程
// find -- moves elements in vals such that location k holds the value it would when sorted
function find(array vals, integer k)
assert (0 <= k < vals.length) // k it must be a valid index
if vals.length <= 1:
return
fi
let pair (j, i) := partition(vals)
if k <= i:
find(a[0,..,i], k)
else-if j <= k:
find(a[j,..,n], k - j)
fi
TODO: debug this!
end
這讓我們得到了關鍵點
// find-median -- returns the median element of vals function find-median(array vals): element assert (vals.length > 0) let median_index := vals.length / 2; find(vals, median_index) return vals[median_index] end
你可能會想到的一個問題是“隨機呼叫真的有必要嗎？”例如，我們可以始終選取中間元素，而不是隨機選取樞軸。鑑於我們的演算法適用於所有可能的陣列，我們可以得出結論，在所有可能的輸入上，所有可能輸入的平均執行時間與我們使用隨機函式的分析相同。這裡的推理是，在所有可能的陣列集合中，中間元素與其他任何元素一樣“隨機”。但這種推理存在一個陷阱：通常，程式中演算法的輸入並非隨機。例如，輸入比隨機情況下更有可能被排序。同樣，由於它是來自真實程式的真實資料，因此資料可能具有其他模式，這些模式會導致次優結果。
換句話說，對於隨機化中位數查詢演算法，它以極低的機率執行次優，與輸入無關；而對於只選取中間元素的確定性演算法，它在它將接收的某些最常見輸入型別上執行不良的可能性更大。這讓我們得出以下準則
| 隨機化準則 如果你的演算法依賴於隨機性，請確保你自己引入隨機性，而不是依賴資料是隨機的。 |
請注意，存在“反隨機化”技術，可以將平均情況快速演算法轉換為完全確定性演算法。有時反隨機化的開銷太大，需要非常大的資料集才能獲得任何收益。儘管如此，反隨機化本身在理論上具有價值。
隨機化 查詢 演算法是由 C. A. R. "Tony" Hoare 發明的。雖然 Hoare 是計算機科學界的重要人物，但他可能最廣為人知的是他在一般圈子裡快速排序演算法，我們將在下一節中討論。
快速排序
[edit | edit source]上一節中的中位數查詢分割槽演算法實際上非常接近完整排序演算法的實現。構建快速排序演算法留作練習，建議讀者在閱讀下一節之前先嚐試（與合併排序相比，快速排序是魔鬼般的，合併排序是一種沒有隨機化步驟改進的排序）。
快速排序的關鍵部分是選擇正確的中位數。但是為了快速執行，首先假設陣列是未排序的，並且每個陣列的最右邊的元素與任何其他元素一樣可能是中位數，並且我們完全樂觀地認為最右邊元素碰巧不是最大鍵，這意味著我們將在每一步只刪除一個元素（分割槽元素），並且沒有右陣列要排序，並且有一個 n-1 左陣列要排序。
這就是 隨機化 對於快速排序很重要的原因，即選擇更優的分割槽鍵，這對快速排序高效工作非常重要。
比較快速排序與插入排序所需的比較次數。
對於插入排序，在對隨機陣列進行升序排序時，查詢最小的第一個元素的平均比較次數為 n /2 。
第二個元素的平均比較次數為 (n-1)/2;
第三個元素為 (n- 2) / 2。
總比較次數為 [ n + (n - 1) + (n - 2) + (n - 3) .. + (n - [n-1]) ] 除以 2，即 [ n x n - (n-1)! ] /2 或約為 O(n 平方) 。
在快速排序中，如果選擇了真正的中位數，則每次劃分步驟中的比較次數都會減半，因為左半部分的劃分不需要與右半部分的劃分進行比較，但在每一步中，由先前劃分級別建立的所有劃分的元素數量仍然為n。
比較n個元素的級別數是將n除以2的步驟數，直到n = 1。或者反過來，2 ^ m ~ n，所以m = log2 n。
因此，比較總數為n（元素）x m（掃描級別）或n x log2n，
因此，比較次數為O(n x log 2(n) )，小於插入排序的O(n^2)或O( n x n )。
（比較O(n x log 2(n) )與O( n x n )，可以消除公因子n，比較為log2(n) vs n，隨著n變大，呈指數級差異。例如，比較n = 2^16，或16 vs 32768，或32 vs 4 gig）。
要在由先前遞迴呼叫確定的陣列的一部分上就地實現劃分，需要從該部分的兩端進行掃描，每當左掃描的當前位置的值大於劃分值且右掃描的當前位置的值小於劃分值時，就進行交換。因此，初始步驟是：-
Assign the partition value to the right most element, swapping if necessary.
因此，劃分步驟是：-
increment the left scan pointer while the current value is less than the partition value. decrement the right scan pointer while the current value is more than the partition value , or the location is equal to or more than the left most location. exit if the pointers have crossed ( l >= r), OTHERWISE perform a swap where the left and right pointers have stopped , on values where the left pointer's value is greater than the partition, and the right pointer's value is less than the partition.
最後，在由於左右指標交叉而退出迴圈後，將最右側的劃分值與左向前掃描指標的最後一個位置進行交換，因此它最終位於左右劃分之間。
確保此時，在最終交換後，正確處理了兩個元素有序陣列和兩個元素無序陣列的情況，這意味著所有情況都應得到正確處理。這是使快速排序正常工作的良好除錯步驟。
對於有序的兩個元素情況，左指標停留在劃分或第二個元素上，因為找到劃分值。右指標從劃分之前的第一個元素開始向後掃描，並在到達最左側位置時停止。
指標交叉，迴圈在進行迴圈交換之前退出。在迴圈之外，將左指標在最右側位置的內容和劃分值（也在最右側位置）進行交換，對有序的兩個元素情況沒有任何改變。
對於無序的兩個元素情況，左指標掃描並在第一個元素處停止，因為它大於劃分值（左掃描值停止交換大於劃分值的值）。
右指標從第一個元素開始並在第一個元素處停止，因為它已到達最左側元素。
迴圈退出是因為左指標和右指標在第一個位置相等，並且左指標在第一個位置的內容和劃分值在最右側（另一個）位置的內容被交換，將先前無序的元素排列成有序的。
另一個實現問題是如何在掃描過程中移動指標。在外部迴圈結束時移動它們似乎很合乎邏輯。
partition(a,l,r) {
v = a[r];
i = l;
j = r -1;
while ( i <= j ) { // need to also scan when i = j as well as i < j ,
// in the 2 in-order case,
// so that i is incremented to the partition
// and nothing happens in the final swap with the partition at r.
while ( a[i] < v) ++i;
while ( v <= a[j] && j > 0 ) --j;
if ( i >= j) break;
swap(a,i,j);
++i; --j;
}
swap(a, i, r);
return i;
使用預增/減一元運算子，可以在 while 迴圈的測試條件中進行測試之前進行掃描，但這意味著指標應分別在開頭偏移 -1 和 +1：因此，演算法看起來像：-
partition (a, l, r ) {
v=a[r]; // v is partition value, at a[r]
i=l-1;
j=r;
while(true) {
while( a[++i] < v );
while( v <= a[--j] && j > l );
if (i >= j) break;
swap ( a, i, j);
}
swap (a,i,r);
return i;
}
qsort 演算法是
qsort( a, l, r) {
if (l >= r) return ;
p = partition(a, l, r)
qsort(a , l, p-1)
qsort( a, p+1, r)
}
最後，劃分元素的隨機化。
random_partition (a,l,r) {
p = random_int( r-l) + l;
// median of a[l], a[p] , a[r]
if (a[p] < a[l]) p =l;
if ( a[r]< a[p]) p = r;
swap(a, p, r);
}
這可以在呼叫 qsort() 中的劃分之前呼叫。
洗牌陣列
[edit | edit source] This keeps data in during shuffle
temporaryArray = { }
This records if an item has been shuffled
usedItemArray = { }
Number of item in array
itemNum = 0
while ( itemNum != lengthOf( inputArray) ){
usedItemArray[ itemNum ] = false None of the items have been shuffled
itemNum = itemNum + 1
}
itemNum = 0 we'll use this again
itemPosition = randdomNumber( 0 --- (lengthOf(inputArray) - 1 ))
while( itemNum != lengthOf( inputArray ) ){
while( usedItemArray[ itemPosition ] != false ){
itemPosition = randdomNumber( 0 --- (lengthOf(inputArray) - 1 ))
}
temporaryArray[ itemPosition ] = inputArray[ itemNum ]
itemNum = itemNum + 1
}
inputArray = temporaryArray
相等的多元多項式
[edit | edit source][TODO：截至目前，沒有已知的確定性多項式時間解決方案，但存在隨機化多項式時間解決方案。最常用的例子是IsPrime，但已找到確定性多項式時間解決方案。]
雜湊表
[edit | edit source]雜湊依賴於雜湊碼函式，將鍵隨機地均勻分佈到可用的槽中。在 Java 中，這是透過將一箇中等大小的素數（31 * 17）新增到一個整型鍵，然後對雜湊表的大小取模來完成的。對於字串鍵，初始雜湊值是透過將每個字元的序數值乘以 31 的乘積相加得到的。
維基百科的資料結構/雜湊表章節很好地涵蓋了這個主題。
跳躍表
[edit | edit source][TODO：談論跳躍表。重點是說明隨機化有時可以使結構更容易理解，而不是平衡樹的複雜性。]
字典或對映是一個通用概念，其中值在某個鍵下插入，並透過鍵檢索。例如，在某些語言中，字典概念是內建的（Python），而在另一些語言中，它是核心庫的一部分（C++ S.T.L. 和 Java 標準集合庫）。提供庫的語言通常允許程式設計師在雜湊演算法或平衡二叉樹實現（紅黑樹）之間進行選擇。最近，跳躍表已經出現，因為它們提供了在多執行緒應用程式中高度併發的實現優勢。
雜湊是一種技術，它依賴於鍵透過雜湊函式時的隨機性，以找到一個雜湊值，該值對應於線性表中的索引。雜湊執行得和雜湊函式一樣快，但只有當插入的鍵在陣列中均勻分佈時才能很好地工作，因為任何雜湊到相同索引的鍵都必須作為雜湊衝突問題處理，例如透過為表中的每個槽保留一個連結串列，並在連結串列中迭代以比較每個鍵值對的完整鍵與搜尋鍵。
雜湊的缺點是無法使用這種資料結構進行有序遍歷。
二叉樹可以用來表示字典，並且可以透過訪問節點（訪問左子節點，訪問當前節點，訪問右子節點，遞迴地）對二叉樹進行有序遍歷。當二叉樹“不平衡”時，例如，插入的鍵值對的鍵以升序或降序插入時，可能會導致搜尋效率低下，因此它們實際上看起來像連結串列，沒有左子節點，並且所有右子節點都是自平衡的。二叉樹可以透過機率（使用隨機性）或確定性（使用子節點連結顏色為紅色或黑色）進行，透過區域性 3 節點樹旋轉操作。旋轉只是將父節點與子節點交換，但保留順序，例如，對於左子節點旋轉，左子節點的右子節點成為父節點的左子節點，父節點成為左子節點的右子節點。
紅黑樹更容易理解，如果檢查相應的2-3-4 樹。2-3-4 樹是一棵樹，節點可以有 2 個子節點、3 個子節點或 4 個子節點，其中 3 個子節點節點在 3 個子節點之間有兩個鍵，4 個子節點節點在 4 個子節點之間有 3 個鍵。4 節點被積極地拆分為 3 個單鍵 2 節點，中間 2 節點向上傳遞以與父節點合併，如果父節點是一個鍵的 2 節點，則成為一個鍵的 3 節點；或者如果是一個鍵的 3 節點，則成為一個鍵的 4 節點，它將在以後被拆分（向上）。拆分一個三鍵 4 節點的行為實際上是一個再平衡操作，它可以防止出現祖父母、父節點、子節點的三個節點字串，而不會發生平衡旋轉。2-3-4 樹是B 樹的有限例子，B 樹通常具有足夠多的節點以適合物理磁碟塊，以便促進無法容納在物理 RAM 中（現在這種情況不太常見）的非常大的索引的快取。
紅黑樹是 2-3-4 樹的二叉樹表示，其中 3 節點由一個父節點和一個紅色子節點建模，4 節點由一個父節點和兩個紅色子節點建模。4 節點的拆分由父節點和 2 個紅色子節點表示，將紅色子節點翻轉為黑色，並將父節點翻轉為紅色。父節點永遠不會是紅色的情況，因為還會發生平衡操作，如果有一個祖父母節點、一個紅色父節點和一個紅色子節點，則祖父母節點被旋轉為父節點的子節點，父節點變為黑色，祖父母節點變為紅色；這與之前的翻轉場景統一，該場景由 2 個紅色子節點表示一個 4 節點。實際上，可能是這種對 4 節點的標準化，以及對傾斜或鋸齒狀 4 節點的強制旋轉，導致了二叉樹的再平衡。
一個新的最佳化是將任何單個右紅色子節點左旋轉為單個左紅色子節點，以便只發生左傾斜內聯 4 節點（3 個紅色節點內聯）的右旋轉，從而簡化了再平衡程式碼。
跳躍表以單鏈表為模型，不同之處在於節點是多層的。高節點很少見，但插入操作確保節點在每個級別都連線起來。
跳躍表的實現需要建立隨機高度的多層節點，然後插入它們。
節點是透過隨機函式的迭代建立的，其中高層節點在迭代中出現得更晚，而且更罕見，因為迭代已經經歷了許多隨機閾值（例如 0.5，如果隨機數在 0 到 1 之間）。
插入需要一個臨時的前一個節點陣列，其高度與生成的插入節點相同。它用於儲存給定級別的最後一個指標，該指標的鍵小於插入鍵。
掃描從跳躍列表的頭部開始，在頭部節點的最高級別，並繼續橫向掃描，直到找到一個鍵高於插入鍵的節點，並將前一個指標儲存在臨時前一個節點陣列中。然後從該節點開始掃描下一個更低級別，依此類推，以鋸齒形向下走，直到到達最低級別。
然後在臨時前一個節點陣列的每個級別執行列表插入，以便前一個節點的下一個節點在每個級別上都成為插入節點的下一個節點，並且插入節點成為前一個節點的下一個節點。
搜尋涉及從頭部節點的最高級別迭代到最低級別，並沿每個級別的下一個指標掃描，直到找到大於搜尋鍵的節點，向下移動到下一個級別，並繼續掃描，直到找到最低級別上具有更高鍵的節點，或者找到搜尋鍵。
建立當更高時更不頻繁的隨機高度節點，以及在每個級別上鍊接所有節點的過程，正是跳躍列表具有優勢的整體結構的原因。
一種跳躍列表實現方法：實現前瞻單鏈表，然後測試，然後轉換為跳躍列表實現，然後進行相同的測試，最後進行效能比較
[edit | edit source]以下是跳躍列表在 Python 中的實現。首先實現一個單鏈表，將下一個節點始終視為當前節點，然後實現跳躍列表，儘量減少對前者的修改，比較有助於澄清實現。
#copyright SJT 2014, GNU
#start by implementing a one lookahead single-linked list :
#the head node has a next pointer to the start of the list, and the current node examined is the next node.
#This is much easier than having the head node one of the storage nodes.
class LN:
"a list node, so don't have to use dict objects as nodes"
def __init__(self):
self.k=None
self.v = None
self.next = None
class single_list2:
def __init__(self):
self.h = LN()
def insert(self, k, v):
prev = self.h
while not prev.next is None and k < prev.next.k :
prev = prev.next
n = LN()
n.k, n.v = k, v
n.next = prev.next
prev.next = n
def show(self):
prev = self.h
while not prev.next is None:
prev = prev.next
print prev.k, prev.v, ' '
def find (self,k):
prev = self.h
while not prev.next is None and k < prev.next.k:
prev = prev.next
if prev.next is None:
return None
return prev.next.k
#then after testing the single-linked list, model SkipList after it.
# The main conditions to remember when trying to transform single-linked code to skiplist code:
# * multi-level nodes are being inserted
# * the head node must be as tall as the node being inserted
# * walk backwards down levels from highest to lowest when inserting or searching,
# since this is the basis for algorithm efficiency, as taller nodes are less frequently and widely dispersed.
import random
class SkipList3:
def __init__(self):
self.h = LN()
self.h.next = [None]
def insert( self, k , v):
ht = 1
while random.randint(0,10) < 5:
ht +=1
if ht > len(self.h.next) :
self.h.next.extend( [None] * (ht - len(self.h.next) ) )
prev = self.h
prev_list = [self.h] * len(self.h.next)
# instead of just prev.next in the single linked list, each level i has a prev.next
for i in xrange( len(self.h.next)-1, -1, -1):
while not prev.next[i] is None and prev.next[i].k > k:
prev = prev.next[i]
#record the previous pointer for each level
prev_list[i] = prev
n = LN()
n.k,n.v = k,v
# create the next pointers to the height of the node for the current node.
n.next = [None] * ht
#print "prev list is ", prev_list
# instead of just linking in one node in the single-linked list , ie. n.next = prev.next, prev.next =n
# do it for each level of n.next using n.next[i] and prev_list[i].next[i]
# there may be a different prev node for each level, but the same level must be linked,
# therefore the [i] index occurs twice in prev_list[i].next[i].
for i in xrange(0, ht):
n.next[i] = prev_list[i].next[i]
prev_list[i].next[i] = n
#print "self.h ", self.h
def show(self):
#print self.h
prev = self.h
while not prev.next[0] is None:
print prev.next[0].k, prev.next[0].v
prev = prev.next[0]
def find(self, k):
prev = self.h
h = len(self.h.next)
#print "height ", h
for i in xrange( h-1, -1, -1):
while not prev.next[i] is None and prev.next[i].k > k:
prev = prev.next[i]
#if prev.next[i] <> None:
#print "i, k, prev.next[i].k and .v", i, k, prev.next[i].k, prev.next[i].v
if prev.next[i] <> None and prev.next[i].k == k:
return prev.next[i].v
if pref.next[i] is None:
return None
return prev.next[i].k
def clear(self):
self.h= LN()
self.h.next = [None]
#driver
if __name__ == "__main__":
#l = single_list2()
l = SkipList3()
test_dat = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
pairs = enumerate(test_dat)
m = [ (x,y) for x,y in pairs ]
while len(m) > 0:
i = random.randint(0,len(m)-1)
print "inserting ", m[i]
l.insert(m[i][0], m[i][1])
del m[i]
# l.insert( 3, 'C')
# l.insert(2, 'B')
# l.insert(4, 'D')
# l.insert(1, 'A')
l.show()
n = int(raw_input("How many elements to test?") )
if n <0: n = -n
l.clear()
import time
l2 = [ x for x in xrange(0, n)]
random.shuffle(l2)
for x in l2:
l.insert(x , x)
l.show()
print
print "finding.."
f = 0
t1 = time.time()
nf = []
for x in l2:
if l.find(x) == x:
f += 1
else:
nf.append(x)
t2 = time.time()
print "time", t2 - t1
td1 = t2 - t1
print "found ", f
print "didn't find", nf
dnf = []
for x in nf:
tu = (x,l.find(x))
dnf.append(tu)
print "find again ", dnf
sl = single_list2()
for x in l2:
sl.insert(x,x)
print "finding.."
f = 0
t1 = time.time()
for x in l2:
if sl.find(x) == x:
f += 1
t2 = time.time()
print "time", t2 - t1
print "found ", f
td2 = t2 - t1
print "factor difference time", td2/td1
隨機性的作用
[edit | edit source]使更高節點的幾何隨機頻率降低的想法意味著，比較的級別越高，需要比較的鍵就越少，並且由於這些鍵是隨機選擇的，因此這應該可以消除導致樹演算法需要進行樹平衡的退化輸入問題。由於更高級別的列表具有間隔更大的元素，但搜尋演算法在每次搜尋在某個級別終止後都會向下移動一個級別，因此更高級別有助於“跳過”在較低級別上搜索較早元素的需要。由於存在多個跳躍級別，因此不太可能在更高級別上跳躍過少而無法在較低級別上透過更好的跳躍來彌補，並且 Pugh 聲稱總體效能為 O(logN)。
從概念上來說，它比平衡樹更容易理解，因此更容易實現嗎？從二叉樹、平衡二叉樹、2-3 樹、紅黑樹和 B 樹發展而來的思想形成了一個更強大的概念網路，但發展是漸進的，因此可以說，一旦理解了紅黑樹，它們就具有更多有助於記憶或重新整理記憶的概念背景。
併發訪問應用程式
[edit | edit source]除了使用隨機化來增強連結串列的基本記憶體結構之外，跳躍列表還可以擴充套件為在多處理器應用程式中使用的全域性資料結構。請參閱本章末尾的補充主題。
練習的想法
[edit | edit source]將 Linux 完全公平排程程式的紅黑樹實現替換為跳躍列表，看看重新編譯後你的 Linux 版本執行情況如何。
樹堆
[edit | edit source]樹堆是一種雙鍵二叉樹，它使用第二個隨機生成的鍵和前面討論過的樹操作（父節點-子節點旋轉）來隨機旋轉樹，以便總體上生成一個平衡樹。回想一下，二叉樹的工作原理是將所有左子樹中的節點都小於給定節點，並將所有右子樹中的節點都大於給定節點。還要記住，節點旋轉不會破壞此順序（有些人稱之為不變式），但會改變父節點和子節點的關係，因此，如果父節點小於右子節點，則父節點會變成以前右子節點的左子節點。樹堆或樹堆的想法是，在父節點和子節點之間保持二叉堆關係，即父節點的優先順序高於其子節點，這與二叉樹中鍵的左右順序不同，因此，最近插入的二叉樹葉節點恰好具有很高的隨機優先順序，可以被旋轉，使其在樹中相對較高，沒有優先順序較低的父節點。
樹堆是紅黑樹和跳躍列表的替代方案，是一種自平衡排序儲存結構。
Java 樹堆實現示例
[edit | edit source]// Treap example: 2014 SJT, copyleft GNU .
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;
public class Treap1<K extends Comparable<K>, V> {
public Treap1(boolean test) {
this.test = test;
}
public Treap1() {}
boolean test = false;
static Random random = new Random(System.currentTimeMillis());
class TreapNode {
int priority = 0;
K k;
V val;
TreapNode left, right;
public TreapNode() {
if (!test) {
priority = random.nextInt();
}
}
}
TreapNode root = null;
void insert(K k, V val) {
root = insert(k, val, root);
}
TreapNode insert(K k, V val, TreapNode node) {
TreapNode node2 = new TreapNode();
node2.k = k;
node2.val = val;
if (node == null) {
node = node2;
} else if (k.compareTo(node.k) < 0) {
node.left = insert(k, val, node.left);
} else {
node.right = insert(k, val, node.right);
}
if (node.left != null && node.left.priority > node.priority) {
// right rotate (rotate left node up, current node becomes right child )
TreapNode tmp = node.left;
node.left = node.left.right;
tmp.right = node;
node = tmp;
} else if (node.right != null && node.right.priority > node.priority) {
// left rotate (rotate right node up , current node becomes left child)
TreapNode tmp = node.right;
node.right = node.right.left;
tmp.left = node;
node = tmp;
}
return node;
}
V find(K k) {
return findNode(k, root);
}
private V findNode(K k, Treap1<K, V>.TreapNode node) {
// TODO Auto-generated method stub
if (node == null)
return null;
if (k.compareTo(node.k) < 0) {
return findNode(k, node.left);
} else if (k.compareTo(node.k) > 0) {
return findNode(k, node.right);
} else {
return node.val;
}
}
public static void main(String[] args) {
LinkedList<Integer> dat = new LinkedList<Integer>();
for (int i = 0; i < 15000; ++i) {
dat.add(i);
}
testNumbers(dat, true); // no random priority balancing
testNumbers(dat, false);
}
private static void testNumbers(LinkedList<Integer> dat,
boolean test) {
Treap1<Integer, Integer> tree= new Treap1<>(test);
for (Integer integer : dat) {
tree.insert(integer, integer);
}
long t1 = System.currentTimeMillis();
Iterator<Integer> iter = dat.iterator();
int found = 0;
while (iter.hasNext()) {
Integer j = desc.next();
Integer i = tree.find(j);
if (j.equals(i)) {
++found;
}
}
long t2 = System.currentTimeMillis();
System.out.println("found = " + found + " in " + (t2 - t1));
}
}
樹堆與伸展樹的對比
[edit | edit source]伸展樹與樹堆類似，它們都使用旋轉將高優先順序節點帶到頂部，而不會改變主鍵順序，只是它們不使用隨機鍵來確定優先順序，而是將最後訪問的節點旋轉到樹的根部，以便更頻繁訪問的節點將位於頂部附近。這意味著在樹堆中，插入的節點只會旋轉到其隨機優先順序鍵所確定的優先順序，而在伸展樹中，插入的節點會被旋轉到根部，並且伸展樹中的每次搜尋都會導致重新平衡，但在樹堆中並非如此。
去隨機化
[edit | edit source][待辦事項：存在針對快速排序的確定性演算法，其效能與快速排序在平均情況下一樣好，並且保證在所有情況下至少達到這種效能。最棒的是，不需要隨機化。討論中還應該包含一些關於使用隨機化的觀點：一些隨機化演算法為您提供的置信機率比實際硬體本身還要高！（例如，太陽黑子會隨機翻轉硬體中的位，導致故障，這是我們經常承擔的風險）]
[主要思想：檢視所有包含 5 個元素的塊，並選擇中位數（O(1) 選擇），將所有中位數放入陣列中（O(n)），遞迴地選擇該陣列的中位數，重複此操作，直到陣列中少於 5 個元素。這種對每五個元素進行遞迴中位數構造需要時間 T(n)=T(n/5) + O(n)，根據主定理，這等於 O(n)。因此，可以在 O(n) 時間內找到正確的樞軸。需要證明此樞軸足夠好，以便無論輸入是什麼，我們仍然是 O(n log n)。這種快速排序版本不需要 rand，而且它永遠不會表現不佳。仍然需要證明選出的元素是足夠好的樞軸。]
練習
[edit | edit source]- 編寫一個find-min函式，並在幾個不同的輸入上執行它，以演示其正確性。
多處理器硬體提供 CAS（比較並設定）或 CMPEXCHG（比較並交換）（英特爾手冊 253666.pdf，第 3-188 頁）原子操作，其中將預期值載入到累加器暫存器中，與目標記憶體位置的內容進行比較，如果相同，則將源記憶體位置的內容載入到目標記憶體的內容中，並設定零標誌，否則，如果不同，則將目標記憶體的內容返回到累加器中，並取消設定零標誌，例如，表示鎖爭用。在英特爾架構中，在 CMPEXCHG 之前發出 LOCK 指令，如果記憶體位置正在被快取，則鎖定快取以防止併發訪問，否則，如果不在快取中，則鎖定共享記憶體位置，以用於下一條指令。
CMPEXCHG 可用於實現鎖定，其中自旋鎖（例如，直到設定零標誌為止一直重試）在設計上是最簡單的。
無鎖設計透過避免自旋等待鎖來提高效率。
Java 標準庫有一個非阻塞併發跳躍表的實現，基於一篇名為“非阻塞單鏈表的實用實現”的論文。
跳躍表實現是對無鎖單鏈表的擴充套件，下面對其進行描述：-
**插入** 操作為：X -> Y 插入 N，N -> Y，X -> N；預期結果為 X -> N -> Y。
如果 M 在 X 和 Y 之間插入，並且 M 先完成，然後 N 完成，那麼情況是 X -> N -> Y <- M，則存在競爭條件。
M 不在列表中。CAS 操作避免了這種情況，因為它在更新 X -> 之前檢查了 -> Y 的副本，與 X -> 的當前值進行比較。
如果 N 先更新 X ->，那麼當 M 嘗試更新 X -> 時，它在執行 M -> Y 之前獲得的 X -> Y 副本與 X -> N 不匹配，因此 CAS 返回非零標誌設定（回想一下，CAS 要求使用者將累加器載入為預期值、目標位置的當前值，然後如果目標位置仍然包含累加器的值，則原子地將目標位置更新為源位置）。嘗試插入 M 的程序然後可以在 X 之後重試插入，但現在 CAS 檢查 -> N 是 X 的下一個指標，所以重試後，X->M->N->Y，並且兩個插入都沒有丟失。
如果 M 先更新 X->，N 的 X->Y 副本與 X -> M 不匹配，因此 CAS 在這裡也會失敗，並且上面重試插入 N 的程序將具有 X ->N -> M -> Y 的序列化結果。
**刪除** 操作依賴於在“物理”刪除之前進行單獨的“邏輯”刪除步驟。
“邏輯”刪除涉及將下一個指標更改為“標記”指標的 CAS。Java 實現用原子地將代理標記節點插入到下一個節點來代替。
這可以防止未來的插入在具有標記下一個指標的節點之後插入，使後一個節點“邏輯地”刪除。
**插入** 操作依賴於另一個函式，*search*，返回在呼叫時為2個**未標記**的節點指標：第一個指向節點，其下一個指標等於第二個。
第一個節點是插入點之前的節點。
*insert* CAS 操作檢查第一個節點的當前下一個指標是否與第二個的未標記引用相對應，因此如果第一個節點的 *next* 指標在呼叫上面的 *search* 函式後變為標記，則“邏輯上”會失敗，因為第一個節點已併發地邏輯地刪除。
這滿足了防止在節點刪除後併發地進行插入的目標。
如果插入操作失敗，則前一個節點的下一個指標的 CAS，則從**整個列表的開頭**重新開始搜尋插入點，因為需要找到一個新的未標記的前一個節點，並且由於列表節點是單鏈表，因此沒有前一個節點指標。
上面概述的**刪除** 操作也依賴於 *search* 操作返回兩個 *未標記* 的節點，以及刪除中的兩個 CAS 操作，一個用於邏輯刪除或標記第二個指標的下一個指標，另一個用於透過使第一個節點的下一個指標指向第二個節點的未標記的下一個指標來進行物理刪除。
刪除的第一個 CAS 僅在檢查第二個節點原始下一個指標的副本未被標記之後才會發生，並確保只有讀取第二個節點的當前下一個指標為未標記的併發刪除成功。
第二個 CAS 檢查前一個節點是否已被邏輯地刪除，因為它的下一個指標與由 search 函式返回的當前第二個節點的未標記指標不同，因此僅更新活動的前一個節點的下一個指標為正在刪除的節點的原始未標記下一個指標的副本（其下一個指標已由第一個 CAS 標記）。
如果第二個 CAS 失敗，那麼前一個節點已被邏輯地刪除，並且它的下一個指標被標記，當前節點的下一個指標也是如此。再次呼叫 *search* 函式會整理好事情，因為它試圖找到當前節點的鍵並返回相鄰的未標記的前一個和當前指標，並且在這樣做的過程中，它截斷了一系列邏輯刪除的節點。
飢餓可能是可能的，因為失敗的插入必須從列表的開頭重新開始。無等待性是一個概念，在這個概念中，演算法的所有執行緒都免受飢餓的困擾。
存在 ABA 問題，其中垃圾收集器回收指標 A，但地址被載入為不同的地址，並且在另一個執行緒讀取 A 並執行 CAS 檢查 A 未更改時，指標被重新新增到一個點：地址相同並且未標記，但 A 的內容已更改。