2013年4月2日 星期二

[ 文章收集 ] Skip List 的介绍以及查找插入删除等操作

參考自 這裡 
Preface: 
什麼是 Skip List?要說清楚這個問題,我們就要先從普通的 Linked List 說起. 考慮我們有一個 Sorted Linked List 如下: 
 

上面鍊表的元素依小到大排序 (ascending), 如果要插入一個元素, 範例代碼如下: 
  1. public boolean insert(int data)  
  2. {  
  3.     if(head==null)  
  4.     {  
  5.         head = new Node(data);            
  6.     }  
  7.     else  
  8.     {  
  9.         Node tmp = head;  
  10.         if(tmp.data
  11.         {  
  12.             while(tmp.next!=null && tmp.next.data
  13.             if(tmp.next!=null && tmp.next.data==data||tmp.data==data) return false;  
  14.             else  
  15.             {  
  16.                 Node newNode = new Node(data);  
  17.                 newNode.next = tmp.next;  
  18.                 tmp.next = newNode;           
  19.             }  
  20.         }  
  21.         else  
  22.         {  
  23.             Node newNode = new Node(data);  
  24.             newNode.next = head;  
  25.             head = newNode;  
  26.         }  
  27.     }     
  28.     return true;  
  29. }  
如果要查找一個元素的範例代碼: 
  1. public Node find(int data)  
  2. {  
  3.     if(head!=null)  
  4.     {  
  5.         Node tmp = head;  
  6.         while(tmp!=null)  
  7.         {  
  8.             if(tmp.data==data) return tmp;  
  9.             else if(tmp.data
  10.             else break;  
  11.         }  
  12.     }  
  13.     return null;  
  14. }  
最後如果是要刪除一個元素: 
  1. public boolean delete(int data)  
  2. {  
  3.     if(head!=null)  
  4.     {  
  5.         Node tmp = head, prv = null;  
  6.         while(tmp!=null)  
  7.         {  
  8.             if(tmp.data == data)  
  9.             {  
  10.                 if(prv==null) head = tmp.next;  
  11.                 else  
  12.                 {  
  13.                     prv.next = tmp.next;  
  14.                 }  
  15.                 return true;  
  16.             }  
  17.             prv = tmp;  
  18.             tmp = tmp.next;  
  19.         }  
  20.     }  
  21.     return false;  
  22. }  
不難發現這些操作的複雜度都是 O(n) , n 是鏈表中的元素數量. (完整代碼下載 LinkedList.java

Skip List 簡介: 
好,下面我們正式開始介紹 Skip List (跳表)。 Skip List 是個概率性數據結構,可以被看作是 BST(二元搜尋數) 的一個變種。跳表是由William Pugh在1990年發明的。它是一種用戶維護有序元素的數據結構. 跳表的構造過程是: 
1. 給定一個有序的鏈表。
2. 避開鏈表中最大和最小的元素,然後從其他元素中按照一定算法隨機選出一些元素,將這些元素組成有序鏈表形成新鏈表。這個新的鏈表稱為一層,原鏈表稱為其下一層。
3. 為剛選出的每個元素添加一個指針域,這個指針指向下一層中值同自己相等的元素。Top指針指向該層首元素
4. 重複2、3步,直到不再能選擇出除最大最小元素以外的元素

一個跳表,應該具有以下特徵: 
1. 一個跳表應該有幾個層(level)組成;
2. 跳表的第一層包含所有的元素;
3. 每一層都是一個有序的鍊錶;
4. 如果元素 x 出現在第 i 層,則所有比 i 小的層都包含x;
5. 第 i 層的元素通過一個 down 指針指向下一層擁有相同值的元素.
6. 因為跳表是隨機生成, 故即使元素相同的鏈表, 最終的生成的跳表有可能不一樣.

接著讓我們用一個跳表來重新構建文章開頭的有序鏈表 (底下是其中一種可能的跳表): 
 

上面的跳表中的 head 是一個陣列, 分別指向各個 Level 的鍊表中第一個元素, 而我們可以透過它在不同 Level 的鍊表中移動; 而相同元素在不同 Level 間也有一個類似的陣列以方便搜尋時在不同 Level 上下移動. 接著假設我們要搜尋數字 "117", 則會按照下面的規則進行搜尋: 
1. 由最上層開始搜尋 (該層需最少有一個元素)
2. 在當前層搜尋並停留在當層比搜尋值小但是最大的 pointer 上. (即該層所有比 "搜尋值" 小的值中最大的值)
3. 檢查下一個位置上是否為 "搜尋值":
3.1 如果是則搜尋成功.
3.2 如果不是, 則往下一層 (層數須大於等於 0). 如果下一層小於 0 則搜尋失敗.
4. 重複步驟 2, 3.



搜尋 "117" 過程如下: 
 

搜尋 "21" 過程如下: 
 

底下是搜尋過程的範例代碼: 
  1. public SNode find(E searchValue)  
  2. {  
  3.     int curLevel = level;  
  4.     SNode x = header;        
  5.     while(curLevel>=0 && x!=null)  
  6.     {  
  7.         while (x.forward[curLevel] != null &&   
  8.                x.forward[curLevel].value.compareTo(searchValue) < 0)   
  9.                 x = x.forward[curLevel];  
  10.             System.out.printf("\t[Test] Hold in %s in level(%d)...\n", x.value!=null?x.value:"header", curLevel);  
  11.             if(x.forward[curLevel]!=null &&   
  12.                x.forward[curLevel].value.equals(searchValue)) return x.forward[curLevel];  
  13.             else  
  14.             {                     
  15.                 if(curLevel>0// 還有下一層, 往下一層移動. 此時 x 會停留當前層在小於 的最大 pointer 上.  
  16.                 {                         
  17.                     curLevel--; // 往下層移動  
  18.                 }  
  19.                 else return null;                 
  20.             }  
  21.           
  22.     }         
  23.     return null;  
  24. }  
根據數學的推導, 這樣的時間複雜度會是 O(log n)n 是元素的數量. 底下是 Skip List (跳表) 的各項操作的時間複雜度: 
 

From Linked List to Skip List: 
現在問題來了, 假設我有一個 ascending order sorted 的 Linked List, 但我想把它轉成 Skip List (跳表) 的話, 該怎麼進行呢? 這個部分我分兩個部分來說明. 首先我們知道 Level 0 層需包含所有元素, 所以不假思索就硬幹了: 
  1. Random rdm = new Random(); // Random 物件稍後會用到  
  2. Iterator iter = sortedList.iterator(); // 為來源 sorted ascending order Linked List  
  3. SNode zeroLevel = header.forward[0]; // header 為每層的入口陣列, 使用 index 說明第幾層.         
  4. HashMap> nodeMap = new HashMap>(); // 記載某個 Node 與其值的 mapping  
  5. while(iter.hasNext())  
  6. {  
  7.     E data = iter.next();  
  8.     SNode x = new SNode(MAX_LEVEL, (E)data); // 建立 Skip List 的 SNode.  
  9.     nodeMap.put(data, x); // 紀錄 SNode mapping, 方便後續取出.  
  10.       
  11.     if(zeroLevel==null)  
  12.     {  
  13.         // 為 null 說明 為 Level 0 的第一個元素.  
  14.         header.forward[0] = x;  
  15.         zeroLevel = header.forward[0];  
  16.     }  
  17.     else {  
  18.         // 串接 下一個元素為 後將 指向    
  19.         zeroLevel.forward[0] = x;  
  20.         zeroLevel = zeroLevel.forward[0];  
  21.     }  
  22.       
  23. }  
因為會遍歷 Linked List 的所有元素, 故其時間複雜度為 O(n), 接著便是要處理上一層的部分了, 因為上一層是從 Level 1 起跳, 故我們下面代碼的 for loop 的變數 level 是從 1 開始; 另外在處理每一層的過程, 會從上一層隨機挑元素出來 (去頭去尾後) 當作此層的元素. 如此一直到再也沒有辦法從上一層取出元素為止. 範例代碼如下: 
  1. for(int level=1; level<=MAX_LEVEL; level++)  
  2. {  
  3.     SNode nextLevel = null;  
  4.     SNode prevSN = header.forward[level-1]; // 去頭            
  5.     if(prevSN==null||prevSN.forward[level-1]==nullcontinue;  
  6.     do  
  7.     {  
  8.         E data = prevSN.value;  
  9.         if(rdm.nextFloat()>P)  
  10.         {  
  11.             System.out.printf("\t[Test] Level%d: %d\n", level, data);  
  12.             if(nextLevel == null)  
  13.             {  
  14.                 // 為 null 說明處理此層的第一個元素.  
  15.                 header.forward[level] = nodeMap.get(data);                        
  16.                 nextLevel = header.forward[level];  
  17.             }  
  18.             else  
  19.             {  
  20.                 nextLevel.forward[level] = nodeMap.get(data);                         
  21.                 nextLevel = nextLevel.forward[level];  
  22.             }  
  23.         }  
  24.         prevSN = prevSN.forward[level-1];  
  25.         if(prevSN==nullbreak;  
  26.     }while(prevSN.forward[level-1]!=null); // 去尾  
  27.     // 設定目前最高層的 level 為當前處理的 level.  
  28.     if(nextLevel!=null// nextLevel 不為 null 說明當前層至少有一個元素.  
  29.     {  
  30.         this.level = level;  
  31.         nextLevel = null;  
  32.     }  
  33. }  
上面的過程, 在走訪下一層的每一個元素時(去頭去尾:P), 我們設定一個常數變數 P=0.5, 當使用 Random 物件隨機產生一個浮點數 (0.0<=x<=1.0) 大於 P 時, 我們便將該元素加到當前這一層. 另外我們也設定另一個常數變數 MAX_LEVEL 來限定最高的層數, 通常該值會是 Linked List 的元素數量取 log (類似 Complete Binary Tree 的 Height). 而這邊的外層 for loop 會執行 log(n) 次, 而內部的 while loop 會執行最多 n 次 (走訪上一層元素), 故我們的時間複雜度會是 O(n log n)

至於 Skip List 的其他操作如 delete, insert 等, 有興趣的可以去下載 SkipList.java. 裡面有完整的實作代碼. 而該範例代碼是改寫自 這裡 的 SkipSet.java

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...