程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> 探索c#之跳躍表(SkipList)

探索c#之跳躍表(SkipList)

編輯:C#入門知識

探索c#之跳躍表(SkipList)


基本介紹 SkipList是William Pugh在1990年提出的,它是一種可替代平衡樹的數據結構。 SkipList在實現上相對比較簡單,比如在限定時間條件下,能非常輕松的實現SkipList,但卻實現不了B樹、紅黑樹、AVL樹等,想一想單B樹的刪除,就要考慮非常多的細節。雖說SkipList簡單,但性能卻非常高,在平均情況下,其插入、刪除、查找數據時間復雜度都是O(log(N)),其最壞情況下都為O(N),這點要低於平衡樹。  由於skipList的高效及維護簡單,所以很多大數據系統中在維護有序列表是都會使用SkipList,比如LevelDB在內存中暫存數據的結構MemTable就是使用SkipList實現的,Redis在Sorted Set數據結構時也采用的是SkipList,還有Lucene中同樣采用SkipList來對倒排列表進行快速查找。 SkipList依賴隨機生成數以一定概率來保持數據在樹上的平衡分布,所以SkipList也屬於概率算性的數據結構,和之前介紹的BoolFilter屬於一個類型C#之布隆過濾器(Bloom filter)。   算法思想 舉個例子,樓主逛完街要回張江玉蘭香苑,如果從人民廣場做公交車回去,要路過非常多的站:   想想這麼遠的路程,多悲慘(在大數據情況下找對應項同樣的問題),相較來說坐地鐵就快很多,然後到廣蘭路換程。 這就是SkipList最核心的思想非常簡單。 現在路線變成:      因為可以一次跨越很多不需要的站,所以就快了很多。如果可以搭朋友順風車的話,變成:   這個圖就非常接近SkipList的結構及思想了。   演化步驟 大致了解怎麼回事了、看具體怎麼實現。 首先我們忘記樹、圖等高級概念及結構,回到我們剛學到鏈表的時候。 再看上面的回家路線圖,我們把最下面一層當成一個鏈表,每個節點(站)指針指向下一個節點(站)。 單個有序鏈表:       按照傳統的操作有序鏈表的做法,如果需要查找其中一條數據,需要順序遍歷。 按照地鐵的思路,如果給一部分的節點增加個指向後面的節點指針,假設一半節點增加,最多遍歷[n/2]+1次即可找到任意節點。這裡把18、23、33、40、47節點都多增加個指針指向後面的節點:       以此類推,繼續增加3、4個等更多的指針,使其指向更遠的後方節點,這樣可以更好的提高查詢效率。 3個節點的情況:    如果理想情況下查找,就類似二分查找了。 SkipList通過隨機數(丟硬幣決定)在插入節點時,隨機判定該節點應該有多少個執行後續節點的指針。 有幾個執行後面節點指針,就是在第幾層,比如上圖18存在3個指針指向後面,它就在第三層,23有2個指針就在第二層。   實現細節 搜索   在同一層查找節點時和普通有序鏈表一樣,順序向後查找,查到返回,否則進入下一層繼續向後查找。比如查找35,會從最頂層搜索比較18、相等返回,大於比較40繼續下一層找,比較1、23、33、40後繼續下一層,比較33、35正確返回、否則不存在。   更新   搜索到值後更新:  
        SkipListNode<TKey, TValue> position;
        bool found = search(key, out position);
        if(found)
            position.value = value;

 

插入   插入時,如果值存在則更新,不存在插入。 如上圖,假如要插入29,需要先查找到27插入到後面,如果扔硬幣後得到3,那麼依次增加指向後面節點的指針。   隨機數   也稱丟硬幣做法。  
       Random generator = new Random();
        int levels = 0;
        while (generator.NextDouble() < 0.5&&levels<=maxlevel)
            levels++;
        return levels;

 

刪除同插入一樣,如果找到,調整相對應的指針順序,然後刪除節點。

  1. 上一頁:
  2. 下一頁: