算法合集之淺談跳躍表的相關(guān)操作及其應(yīng)用

1、華東師范大學(xué)第二附屬中學(xué) 魏冉 讓算法的效率“跳起來”！ 淺談“跳躍表”的相關(guān)操作及其應(yīng)用 上海市華東師范大學(xué)第二附屬中學(xué) 魏冉【目錄】 關(guān)鍵字······································

2、··················································

3、【2】 摘要·················································

4、·······································【2】 概述及結(jié)構(gòu)·········

5、83;·················································

6、83;······················【2】 基本操作··························&

7、#183;·················································&

8、#183;············【3】查找····································&#

9、183;·············································【3】插入···

10、83;·················································

11、83;····························【3】刪除····················

12、3;·················································

13、3;···········【4】“記憶化”查找·····································

14、································【5】 復(fù)雜度分析················

15、83;·················································

16、83;···············【6】空間復(fù)雜度分析·································

17、;·····································【7】跳躍表高度分析···········&

18、#183;·················································&

19、#183;········【7】查找的時間復(fù)雜度分析·······································

20、··················【7】插入與刪除的時間復(fù)雜度分析·····························&#

21、183;····················【8】實際測試效果····························

22、;·········································【8】 跳躍表的應(yīng)用·······&

23、#183;·················································&

24、#183;··················【9】 總結(jié)······························&

25、#183;·················································&

26、#183;········【10】 附錄········································

27、·················································【11】【關(guān)

28、鍵字】跳躍表 高效 概率 隨機(jī)化【摘要】本文分為三大部分。首先是概述部分。它會從功能、效率等方面對跳躍表作一個初步的介紹，并給出其圖形結(jié)構(gòu)，以便讀者對跳躍表有個形象的認(rèn)識。第二部分將介紹跳躍表的三種基本操作查找，插入和刪除，并對它們的時空復(fù)雜度進(jìn)行分析。第三部分是對跳躍表應(yīng)用的介紹，并通過實際測試效果來對跳躍表以及其它一些相關(guān)數(shù)據(jù)結(jié)構(gòu)進(jìn)行對比，體現(xiàn)其各自的優(yōu)缺點。最后一部分是對跳躍表數(shù)據(jù)結(jié)構(gòu)的總結(jié)?！靖攀黾敖Y(jié)構(gòu)】二叉樹是我們都非常熟悉的一種數(shù)據(jù)結(jié)構(gòu)。它支持包括查找、插入、刪除等一系列的操作。但它有一個致命的弱點，就是當(dāng)數(shù)據(jù)的隨機(jī)性不夠時，會導(dǎo)致其樹型結(jié)構(gòu)的不平衡，從而直接影響到算法的效率。跳躍

29、表（skip list）是1987年才誕生的一種嶄新的數(shù)據(jù)結(jié)構(gòu)，它在進(jìn)行查找、插入、刪除等操作時的期望時間復(fù)雜度均為o(logn),有著近乎替代平衡樹的本領(lǐng)。而且最重要的一點，就是它的編程復(fù)雜度較同類的avl樹，紅黑樹等要低得多，這使得其無論是在理解還是在推廣性上，都有著十分明顯的優(yōu)勢。首先，我們來看一下跳躍表的結(jié)構(gòu)（如圖1）53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 - - - - + + + + 圖1 有7個元素的跳躍表s0 s1 s2 s3 跳躍表由多條鏈構(gòu)成（s0，s1，s2 ，sh），且滿足如下三個條件：（1） 每條鏈必須包含兩個特殊元素

30、：+ 和 -（2） s0包含所有的元素，并且所有鏈中的元素按照升序排列。（3） 每條鏈中的元素集合必須包含于序數(shù)較小的鏈的元素集合，即：【基本操作】在對跳躍表有一個初步的認(rèn)識以后，我們來看一下基于它的幾個最基本的操作。一、 查找目的：在跳躍表中查找一個元素x在跳躍表中查找一個元素x，按照如下幾個步驟進(jìn)行：i) 從最上層的鏈（sh）的開頭開始ii) 假設(shè)當(dāng)前位置為p，它向右指向的節(jié)點為q（p與q不一定相鄰），且q的值為y。將y與x作比較(1)x=y輸出查詢成功及相關(guān)信息(2)x>y從p向右移動到q的位置(3)x<y從p向下移動一格iii)如果當(dāng)前位置在最底層的鏈中（s0），且還要往下

31、移動的話，則輸出查詢失敗53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 - - - - + + + + 圖2 查詢元素53的全過程s0 s1 s2 s3 二、插入目的：向跳躍表中插入一個元素x首先明確，向跳躍表中插入一個元素，相當(dāng)于在表中插入一列從s0中某一位置出發(fā)向上的連續(xù)一段元素。有兩個參數(shù)需要確定，即插入列的位置以及它的“高度”。關(guān)于插入的位置，我們先利用跳躍表的查找功能，找到比x小的最大的數(shù)y。根據(jù)跳躍表中所有鏈均是遞增序列的原則，x必然就插在y的后面。而插入列的“高度”較前者來說顯得更加重要，也更加難以確定。由于它的不確定性，使得不同的決策可

32、能會導(dǎo)致截然不同的算法效率。為了使插入數(shù)據(jù)之后，保持該數(shù)據(jù)結(jié)構(gòu)進(jìn)行各種操作均為o(logn)復(fù)雜度的性質(zhì)，我們引入隨機(jī)化算法（randomized algorithms）。我們定義一個隨機(jī)決策模塊，它的大致內(nèi)容如下：·產(chǎn)生一個0到1的隨機(jī)數(shù)rr random()·如果r小于一個常數(shù)p，則執(zhí)行方案a，if r<pthen do a 否則，執(zhí)行方案belse do b初始時列高為1。插入元素時，不停地執(zhí)行隨機(jī)決策模塊。如果要求執(zhí)行的是a操作，則將列的高度加1，并且繼續(xù)反復(fù)執(zhí)行隨機(jī)決策模塊。直到第i次，模塊要求執(zhí)行的是b操作，我們結(jié)束決策，并向跳躍表中插入一個高度為i的列。

33、性質(zhì)1：根據(jù)上述決策方法，該列的高度大于等于k的概率為pk-1。此處有一個地方需要注意，如果得到的i比當(dāng)前跳躍表的高度h還要大的話，則需要增加新的鏈，使得跳躍表仍滿足先前所提到的條件。我們來看一個例子：假設(shè)當(dāng)前我們要插入元素“40”，且在執(zhí)行了隨機(jī)決策模塊后得到高度為4·步驟一：找到表中比40小的最大的數(shù)，確定插入位置53 53 53 45 45 37 30 30 30 29 15 - - - + + + 圖3.1 確定插入的位置s0 s1 s2 插入的位置·步驟二：插入高度為4的列，并維護(hù)跳躍表的結(jié)構(gòu)圖3.2 插入高度為4的列，并維護(hù)跳躍表s0 53 53 53 45 4

34、5 37 30 30 30 29 15 s1 s2 s3 40 40 40 40 - - - - + + + + 注意加入新的鏈 三、刪除目的：從跳躍表中刪除一個元素x刪除操作分為以下三個步驟：（1） 在跳躍表中查找到這個元素的位置，如果未找到，則退出*（2） 將該元素所在整列從表中刪除*s3 s2 s1 （3） 將多余的“空鏈”刪除*s0 圖4.1 刪除元素11的全過程- + 11 11 11 11 - + 30 30 30 53 53 53 - + 45 45 - + 15 29 37 53 53 53 45 45 37 30 30 30 29 15 - - - + + + 圖4.2 刪除

35、以后的結(jié)構(gòu)s0 s1 s2 四、“記憶化”查找（search with fingers）所謂“記憶化”查找，就是在前一次查找的基礎(chǔ)上進(jìn)行進(jìn)一步的查找。它可以利用前一次查找所得到的信息，取其中可以被當(dāng)前查找所利用的部分。利用“記憶化”查找可以將一次查找的復(fù)雜度變?yōu)閛(logk)，其中k為此次與前一次兩個被查找元素在跳躍表中位置的距離。下面來看一下記憶化搜索的具體實現(xiàn)方法：假設(shè)上一次操作我們查詢的元素為i，此次操作我們欲查詢的元素為j。我們用一個update數(shù)組來記錄在查找i時，指針在每一層所“跳”到的最右邊的位置。如圖4.1中橘黃色的元素。（藍(lán)色為路徑上的其它元素）53 53 53 45 45

36、37 30 30 30 29 15 11 11 11 11 - - - - + + + + 圖4.1 查找元素37s0 s1 s2 s3 在插入元素j時，分為兩種情況：（1） i<=j從s0層開始向上遍歷update數(shù)組中的元素，直到找到某個元素，它向右指向的元素大于等于j，并于此處開始新一輪對j的查找（與一般的查找過程相同）（2） i>j從s0層開始向上遍歷update數(shù)組中的元素，直到找到某個元素小于等于j，并于此處開始新一輪對j的查找（與一般的查找過程相同）圖4.2十分詳細(xì)地說明了在查找了i=37之后，繼續(xù)查找j=15或53時的兩種不同情況。53 53 53 45 45 37

37、 30 30 30 29 15 11 11 11 11 - - - - + + + + 圖4.2 新一輪查找元素為15（53）的步驟流程s0 s1 s2 s3 記憶化查找（search with fingers）技術(shù)對于那些前后相關(guān)性較強(qiáng)的數(shù)據(jù)效率極高，這點可以在后文中的實際測試報告中略見一斑。【復(fù)雜度分析】一個數(shù)據(jù)結(jié)構(gòu)的好壞大部分取決于它自身的空間復(fù)雜度以及基于它一系列操作的時間復(fù)雜度。跳躍表之所以被譽(yù)為幾乎能夠代替平衡樹，其復(fù)雜度方面自然不會落后。我們來看一下跳躍表的相關(guān)復(fù)雜度：空間復(fù)雜度： o(n) （期望）跳躍表高度： o(logn)（期望）相關(guān)操作的時間復(fù)雜度：查找： o(logn)

38、（期望）插入： o(logn)（期望）刪除： o(logn)（期望）之所以在每一項后面都加一個“期望”，是因為跳躍表的復(fù)雜度分析是基于概率論的。有可能會產(chǎn)生最壞情況，不過這種概率極其微小。下面我們來一項一項分析。一、 空間復(fù)雜度分析 o(n)假設(shè)一共有n個元素。根據(jù)性質(zhì)1，每個元素插入到第i層（si）的概率為pi-1 ，則在第i層插入的期望元素個數(shù)為npi-1，跳躍表的元素期望個數(shù)為 ，當(dāng)p取小于0.5的數(shù)時，次數(shù)總和小于2n。所以總的空間復(fù)雜度為o(n)二、跳躍表高度分析 o(logn)根據(jù)性質(zhì)1，每個元素插入到第i層（si）的概率為pi ，則在第i層插入的期望元素個數(shù)為npi-1?？紤]一個

39、特殊的層：第1+層。層的元素期望個數(shù)為 = 1/n2，當(dāng)n取較大數(shù)時，這個式子的值接近0，故跳躍表的高度為o(logn)級別的。三、查找的時間復(fù)雜度分析 o(logn)我們采用逆向分析的方法。假設(shè)我們現(xiàn)在在目標(biāo)節(jié)點，想要走到跳躍表最左上方的開始節(jié)點。這條路徑的長度，即可理解為查找的時間復(fù)雜度。設(shè)當(dāng)前在第i層第j列那個節(jié)點上。i) 如果第j列恰好只有i層（對應(yīng)插入這個元素時第i次調(diào)用隨機(jī)化模塊時所產(chǎn)生的b決策，概率為1-p），則當(dāng)前這個位置必然是從左方的某個節(jié)點向右跳過來的。ii) 如果第j列的層數(shù)大于i（對應(yīng)插入這個元素時第i次調(diào)用隨機(jī)化模塊時所產(chǎn)生的a決策，概率為p），則當(dāng)前這個位置必然是從

40、上方跳下來的。（不可能從左方來，否則在以前就已經(jīng)跳到當(dāng)前節(jié)點上方的節(jié)點了，不會跳到當(dāng)前節(jié)點左方的節(jié)點）設(shè)c(k)為向上跳k層的期望步數(shù)（包括橫向跳躍）有：c(0) = 0c(k) = (1-p)(1+向左跳躍之后的步數(shù))+p(1+向上跳躍之后的步數(shù)) = (1-p)(1+c(k) + p(1+c(k-1)c(k) = 1/p + c(k-1)c(k) = k/p而跳躍表的高度又是logn級別的，故查找的復(fù)雜度也為logn級別。對于記憶化查找（search with fingers）技術(shù)我們可以采用類似的方法分析，很容易得出它的復(fù)雜度是o(logk)的（其中k為此次與前一次兩個被查找元素在跳躍表

41、中位置的距離）。四、插入與刪除的時間復(fù)雜度分析 o(logn)插入和刪除都由查找和更新兩部分構(gòu)成。查找的時間復(fù)雜度為o(logn)，更新部分的復(fù)雜度又與跳躍表的高度成正比，即也為o(logn)。所以，插入和刪除操作的時間復(fù)雜度都為o(logn)五、實際測試效果（1）不同的p對算法復(fù)雜度的影響p平均操作時間平均列高總結(jié)點數(shù)每次查找跳躍次數(shù)（平均值）每次插入跳躍次數(shù)（平均值）每次刪除跳躍次數(shù)（平均值） 2/30.0024690 ms3.0049123339.87841.60441.5661/20.0020180 ms1.9956068327.80729.94729.0721/e0.0019870

42、ms1.5844757027.33228.23828.4521/40.0021720 ms1.3304047828.72629.47229.6641/80.0026880 ms1.1443442035.14735.82136.007表1 進(jìn)行106次隨機(jī)操作后的統(tǒng)計結(jié)果從表1中可見，當(dāng)p取1/2和1/e的時候，時間效率比較高（為什么？）。而如果在實際應(yīng)用中空間要求很嚴(yán)格的話，那就可以考慮取稍小一些的p，如1/4。（2）運(yùn)用“記憶化”查找 (search with fingers) 的效果分析所謂“記憶化”查找，就是在前一次查找的基礎(chǔ)上進(jìn)行進(jìn)一步的查找。它可以利用前一次查找所得到的信息，取其中可

43、以被當(dāng)前查找所利用的部分。利用“記憶化”查找可以將一次查找的復(fù)雜度變?yōu)閛(logk)，其中k為此次與前一次兩個被查找元素在跳躍表中位置的距離。p數(shù)據(jù)類型平均操作時間（不運(yùn)用記憶化查找）平均操作時間（運(yùn)用記憶化查找）平均每次查找跳躍次數(shù)（不運(yùn)用記憶化查找）平均每次查找跳躍次數(shù)（運(yùn)用記憶化查找）0.5隨機(jī)（相鄰被查找元素鍵值差的絕對值較大）0.0020150 ms0.0020790 ms23.26226.5090.5前后具備相關(guān)性（相鄰被查找元素鍵值差的絕對值較?。?.0008440 ms0.0006880 ms26.1574.932表1 進(jìn)行106次相關(guān)操作后的統(tǒng)計結(jié)果從表2中可見，當(dāng)數(shù)據(jù)相鄰被

44、查找元素鍵值差絕對值較小的時候，我們運(yùn)用“記憶化”查找的優(yōu)勢是很明顯的，不過當(dāng)數(shù)據(jù)隨機(jī)化程度比較高的時候，“記憶化”查找不但不能提高效率，反而會因為跳躍次數(shù)過多而成為算法的瓶頸。合理地利用此項優(yōu)化，可以在特定的情況下將算法效率提升一個層次。【跳躍表的應(yīng)用】高效率的相關(guān)操作和較低的編程復(fù)雜度使得跳躍表在實際應(yīng)用中的范圍十分廣泛。尤其在那些編程時間特別緊張的情況下，高性價比的跳躍表很可能會成為你的得力助手。能運(yùn)用到跳躍表的地方很多，與其去翻陳年老題，不如來個趁熱打鐵，拿noi2004第一試的第一題郁悶的出納員(cashier)來“小試牛刀”吧。例題一：noi2004 day1 郁悶的出納員(cas

45、hier)點擊查看附錄中的原題這道題解法的多樣性給了我們一次對比的機(jī)會。用不同的算法和數(shù)據(jù)結(jié)構(gòu)，在效率上會有怎樣的差異呢？首先定義幾個變量r 工資的范圍n 員工總數(shù)我們來看一下每一種適用的算法和數(shù)據(jù)結(jié)構(gòu)的簡要描述和理論復(fù)雜度：（1） 線段樹簡要描述：以工資為關(guān)鍵字構(gòu)造線段樹，并完成相關(guān)操作。i命令時間復(fù)雜度：o(logr)a命令時間復(fù)雜度：o(1)s命令時間復(fù)雜度：o(logr)f命令時間復(fù)雜度：o(logr)（2） 伸展樹(splay tree)簡要描述：以工資為關(guān)鍵字構(gòu)造伸展樹，并通過“旋轉(zhuǎn)”完成相關(guān)操作。i命令時間復(fù)雜度：o(logn)a命令時間復(fù)雜度：o(1)s命令時間復(fù)雜度：o(lo

46、gn)f命令時間復(fù)雜度：o(logn)（3） 跳躍表(skip list)簡要描述：運(yùn)用跳躍表數(shù)據(jù)結(jié)構(gòu)完成相關(guān)操作。i命令時間復(fù)雜度：o(logn)a命令時間復(fù)雜度：o(1)s命令時間復(fù)雜度：o(logn)f命令時間復(fù)雜度：o(logn)實際效果評測：（單位：秒）test1test2test3test4test5test6test7test8test9test10線段樹0.0000.0000.0000.0310.0620.0940.1090.2030.2650.250伸展樹0.0000.0000.0160.0620.0470.1250.1410.3600.4530.422跳躍表0.0000.0

47、000.0000.0470.0620.1090.1560.3680.4380.375從結(jié)果來看，線段樹這種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)似乎占據(jù)著很大的優(yōu)勢?？捎幸稽c萬萬不能忽略，那就是線段樹是基于鍵值構(gòu)造的，它受到鍵值范圍的約束。在本題中r的范圍只有105級別，這在內(nèi)存較寬裕的情況下還是可以接受的。但是如果問題要求的鍵值范圍較大，或者根本就不是整數(shù)時，線段樹可就很難適應(yīng)了。這時候我們就不得不考慮伸展樹、跳躍表這類基于元素構(gòu)造的數(shù)據(jù)結(jié)構(gòu)。而從實際測試結(jié)果看，跳躍表的效率并不比伸展樹差。加上編程復(fù)雜度上的優(yōu)勢，跳躍表盡顯出其簡單高效的特點。參考程序：例題二：hnoi2004 day1 寵物收養(yǎng)所(pet) 點擊

48、查看附錄中的原題此題與郁悶的出納員最大的不同，就在于它的鍵值范圍達(dá)到了231級別。這對線段樹來說可是一大考驗。雖然采取邊做邊開空間的策略勉強(qiáng)可以緩解內(nèi)存的壓力，但此題對內(nèi)存的要求很苛刻，元素相對范圍來說也比較少，如果插入的元素稍微分散一些，就很有可能使得空間復(fù)雜度接近o（nlogn）！何況如果稍微拓展一下，插入的元素不是整數(shù)而是實數(shù)呢？而這道題對于跳躍表來說,可真是再適合不過了。幾乎對標(biāo)準(zhǔn)的算法不需要做修改，如果熟練的話，從思考到編寫完成也就20分鐘左右的時間，最終的算法效率也很高。更加重要的一點，跳躍表絕不會因鍵值類型的變化而失效，推廣性很強(qiáng)。參考程序：【總結(jié)】跳躍表作為一種新興的數(shù)據(jù)結(jié)構(gòu)，

49、以相當(dāng)高的效率和較低的復(fù)雜度散發(fā)著其獨特的光芒。和同樣以編程復(fù)雜度低而聞名的“伸展樹”相比，跳躍表的效率不但不會比它差，甚至優(yōu)于前者（見附表1）。人們在思考一類問題的時候，往往會無意中被局限在一個小范圍當(dāng)中。就拿和平衡樹相關(guān)的問題來說，人們憑借自己的智慧，創(chuàng)造出了紅黑樹，avl樹等一些很復(fù)雜的數(shù)據(jù)結(jié)構(gòu)?？墒乔ё?nèi)f變，卻一直走不出“樹”這個范圍。過高的編程復(fù)雜度使得這些成果很難被人們所接受。而跳躍表的出現(xiàn)，使得人們眼前頓時豁然開朗。原來用與樹完全不相關(guān)的數(shù)據(jù)結(jié)構(gòu)也能夠?qū)崿F(xiàn)樹的功能！“跳躍表”這個名字有著其深遠(yuǎn)的意義。不僅是因為它形象地描述了自身的結(jié)構(gòu)，更有一點，它象征著一種思考方法，一種“跳出定

50、式”的思考方法。在你面臨一個困難卻山窮水復(fù)疑無路的時候，不妨找到問題的原點，“跳”出思維的定式，說不定在另一條全新的路上，你將會看到勝利的曙光。【參考文獻(xiàn)】1 william pugh. skip lists: a probabilistic alternative to balanced trees2 william pugh. a skip list cookbook【附錄】·附表：跳躍表與avl樹、2-3樹、伸展樹在時間效率上的對比（摘自 1 william pugh. skip lists: a probabilistic alternative to balanced tr

51、ees）·程序：“跳躍表”的程序(pascal語言實現(xiàn))：附解：為什么p=1/e的時候時間效率最高？解：由復(fù)雜度分析中得出，跳躍表的時間效率取決于跳躍的次數(shù)，也就是k/p（k為跳躍表高度），而k是級別。故有：令 x = 1/p ，則有：對求導(dǎo)，有當(dāng)x=e時，g(x)=0，即f(x)到達(dá)極值點。此時p = 1/e 返回“實際測試效果部分”附題：noi2004 day1 郁悶的出納員返回“跳躍表的應(yīng)用”部分郁悶的出納員【問題描述】oier公司是一家大型專業(yè)化軟件公司，有著數(shù)以萬計的員工。作為一名出納員，我的任務(wù)之一便是統(tǒng)計每位員工的工資。這本來是一份不錯的工作，但是令人郁悶的是，我們的老

52、板反復(fù)無常，經(jīng)常調(diào)整員工的工資。如果他心情好，就可能把每位員工的工資加上一個相同的量。反之，如果心情不好，就可能把他們的工資扣除一個相同的量。我真不知道除了調(diào)工資他還做什么其它事情。工資的頻繁調(diào)整很讓員工反感，尤其是集體扣除工資的時候，一旦某位員工發(fā)現(xiàn)自己的工資已經(jīng)低于了合同規(guī)定的工資下界，他就會立刻氣憤地離開公司，并且再也不會回來了。每位員工的工資下界都是統(tǒng)一規(guī)定的。每當(dāng)一個人離開公司，我就要從電腦中把他的工資檔案刪去，同樣，每當(dāng)公司招聘了一位新員工，我就得為他新建一個工資檔案。老板經(jīng)常到我這邊來詢問工資情況，他并不問具體某位員工的工資情況，而是問現(xiàn)在工資第k多的員工拿多少工資。每當(dāng)這時，我就不得不對數(shù)萬個員工進(jìn)行一次漫長的排序，然后告訴他答案。好了，現(xiàn)在你已經(jīng)對我的工作了解不少了。正如你猜的那樣，我想請你編一個工資統(tǒng)計程序。怎么樣，不是很困難吧？【輸入文件】第一行有兩個非負(fù)整數(shù)n和min。n表示下面有多少條命令，min表示工資下界。接下來的n行，每行表示一條命令。命令可以是以下四種之一：名稱格式作用i命令i_k新建一個工資檔案，初始工資為k。如果某員工的初始工資低于