淺談“跳躍表”的相關(guān)操作及其應(yīng)用

1、讓算法的效率“跳起來”！ 淺談“跳躍表”的相關(guān)操作及其應(yīng)用 “跳躍表” 新生的寵兒 跳躍表（skip list）是1987年才誕生的一種嶄新的數(shù)據(jù)結(jié)構(gòu)，它在進(jìn)行查找、插入、刪除等操作時(shí)的時(shí)間復(fù)雜度均為o(logn),有著近乎替代平衡樹的本領(lǐng)。而且最重要的一點(diǎn)，就是它的編程復(fù)雜度較同類的avl樹，紅黑樹等要低得多，這使得其無論是在理解還是在推廣性上，都有著十分明顯的優(yōu)勢(shì)。“跳躍表”的結(jié)構(gòu)跳躍表由多條鏈構(gòu)成（s0，s1，s2 ，sh），且滿足如下三個(gè)條件：1.每條鏈必須包含兩個(gè)特殊元素：+ 和 -2.s0包含所有的元素，并且所有鏈中的元素按照升序排列。3.每條鏈中的元素集合必須包含于序數(shù)較小的鏈的

2、元素集合，即：hssss.210hssss.210hssss.21053 53 53 45 45 37 30 30 30 29 15 11 11 11 11 - - - - + + + + s0 s1 s2 s3 跳躍表的實(shí)例“跳躍表” 的時(shí)空效率 空間復(fù)雜度： o(n) （期望） 跳躍表高度： o(logn)（期望）相關(guān)操作的時(shí)間復(fù)雜度：查找： o(logn)（期望）插入： o(logn)（期望）刪除： o(logn)（期望）基本操作一 查找目的：在跳躍表中查找一個(gè)元素 x在跳躍表中查找一個(gè)元素x，按照如下幾個(gè)步驟進(jìn)行：i.從最上層的鏈（sh）的開頭開始ii.假設(shè)當(dāng)前位置為p，它向右指向的節(jié)

3、點(diǎn)為q（p與q不一定相鄰），且q的值為y。將y與x作比較lx=y輸出查詢成功，輸出相關(guān)信息lxy從p向右移動(dòng)到q的位置lxy從p向下移動(dòng)一格iii.如果當(dāng)前位置在最底層的鏈中（s0），且還要往下移動(dòng)的話，則輸出查詢失敗53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 - - - - + + + + 查詢?cè)?3的全過程s0 s1 s2 s3 查找成功！基本操作二 插入目的：在跳躍表中插入一個(gè)元素 x 插入操作由兩部分組成：查找插入的位置和插入對(duì)應(yīng)元素。為了確定插入的“列高”，我們引入一個(gè)隨機(jī)決策模塊：產(chǎn)生一個(gè)0到1的隨機(jī)數(shù)rr random()如果r小于

4、一個(gè)概率因子p，則執(zhí)行方案a，if rpthen do a否則，執(zhí)行方案belse do b列的初始高度為1。插入元素時(shí)，不停地執(zhí)行隨機(jī)決策模塊。如果要求執(zhí)行的是a操作，則將列的高度加1，并且繼續(xù)反復(fù)執(zhí)行隨機(jī)決策模塊。直到第i次，模塊要求執(zhí)行的是b操作，我們結(jié)束決策，并向跳躍表中插入一個(gè)高度為i的列。基本操作二 插入 假設(shè)我們現(xiàn)在要插入一個(gè)元素40到已有的跳躍表中。37 30 30 30 29 15 - - - - s0 s1 s2 s3 插入的位置53 53 53 45 45 + + + + 40 40 4040 高度+1隨機(jī)化模塊運(yùn)行狀況：高度=4高度+1高度+1 結(jié)束53 - - - -

5、 s0 s1 s2 s3 基本操作三 刪除目的：從跳躍表中刪除一個(gè)元素 x刪除操作分為以下三個(gè)步驟：1.在跳躍表中查找到這個(gè)元素的位置，如果未找到，則退出2.將該元素所在整列從表中刪除3.將多余的“空鏈”刪除11 11 11 11 53 53 53 45 45 37 30 30 30 29 15 + + + + 53 53 53 45 45 37 30 30 30 29 15 - - - + + + s0 s1 s2 概率因子 p 對(duì)跳躍表的影響在插入操作中，我們引入了一個(gè)概率因子p，它決定了跳躍表的高度，并影響到了整個(gè)數(shù)據(jù)結(jié)構(gòu)的效率。讓我們來看看在實(shí)際評(píng)測(cè)過程中，不同的p在時(shí)空效率上的差異。

6、p 平均操作時(shí)間 平均列高 總結(jié)點(diǎn)數(shù) 每次查找跳躍次數(shù)（平均值） 每次插入跳躍次數(shù)（平均值） 每次刪除跳躍次數(shù)（平均值） 2/3 0.0024690 ms 3.004 91233 39.87841.60441.5661/2 0.0020180 ms1.995 60683 27.80729.94729.0721/e 0.0019870 ms1.584 47570 27.33228.23828.4521/4 0.0021720 ms1.33040478 28.72629.47229.6641/8 0.0026880 ms1.14434420 35.14735.82136.007跳躍表的應(yīng)用 高效率

7、的相關(guān)操作和較低的編程復(fù)雜度使得跳躍表在實(shí)際應(yīng)用中的范圍十分廣泛。尤其在那些編程時(shí)間特別緊張的情況下，高性價(jià)比的跳躍表很可能會(huì)成為你的得力助手。您正為找不到合適的數(shù)據(jù)結(jié)構(gòu)而感到煩惱嗎？您正為自己編寫程序的效率高低而感到擔(dān)憂嗎？您正為陷入r-b tree的深淵又無法自拔而感到苦悶嗎？朋友！試試跳躍表吧！它將給您的編程帶來超高的效率與無盡的快樂！機(jī)不可失，時(shí)不再來！詳情請(qǐng)致電：1381xxxxxxx跳躍表的應(yīng)用 noi2004 day1 郁悶的出納員（cashier） 抽象題意：要求維護(hù)這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)，使得它支持以下四種操作：i(x)插入一個(gè)值為 x 元素a(x)現(xiàn)有全體元素加上一個(gè)值 xs(x

8、)現(xiàn)有全體元素減去一個(gè)值 xf(i)查找現(xiàn)有元素中第 i 大的元素值（x為105級(jí)別）同時(shí)還要保持這樣一個(gè)性質(zhì)：現(xiàn)有的元素必須都大于一個(gè)特定的值min，小于min的要?jiǎng)h去。 我們利用一個(gè)虛擬的“零線”來表示0在數(shù)據(jù)結(jié)構(gòu)中的相對(duì)位置。這樣在進(jìn)行a和s操作的時(shí)候，只要對(duì)“零線”進(jìn)行調(diào)整即可，并不需要對(duì)所有元素的值做全面的修改。而在做s操作時(shí)，為了維持題意中的性質(zhì)，要注意將值低于（“零線”+min）的元素刪除。 支持這些操作的數(shù)據(jù)結(jié)構(gòu)有很多，比如說線段樹，伸展樹，跳躍表等。跳躍表的應(yīng)用 noi2004 day1 郁悶的出納員（cashier）評(píng)測(cè)結(jié)果：（單位：秒）test1test2test3tes

9、t4test5test6test7test8test9test10線段樹0.0000.0000.0000.0310.0620.0940.1090.2030.2650.250伸展樹0.0000.0000.0160.0620.0470.1250.1410.3600.4530.422跳躍表0.0000.0000.0000.0470.0620.1090.1560.3680.4380.375i命令時(shí)間復(fù)雜度 a命令時(shí)間復(fù)雜度 s命令時(shí)間復(fù)雜度 f命令時(shí)間復(fù)雜度 線段樹o(logr) o(1) o(logr) o(logr) 伸展樹 o(logn) o(1) o(logn) o(logn) 跳躍表 o(logn) o(1) o(logn) o(logn) 1. 空間復(fù)雜度o（n）2. 擺脫實(shí)數(shù)的約束3. 極小的編程復(fù)雜度能夠使你很短的內(nèi)解決此題！跳躍表的應(yīng)用 hnoi2004 day1 寵物收養(yǎng)所 （pet） 抽象題意：維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)，使得它支持以下兩種操作： 插入一個(gè)元素 x (0 x231) 給定一個(gè)元素y，刪除現(xiàn)有與y差值最小的元素x （|x-y|為最小）所有操作次數(shù)不超過80000思考.線段樹? 如果采取邊做邊開空間的策略，勉強(qiáng)可以緩解內(nèi)存的壓力。但此題對(duì)內(nèi)存的要求很苛刻，元素相對(duì)范圍來說也比較少，如果插入的元素稍微分散一些，就很有可能使得空間復(fù)雜度