Java跳過列表實現優化

我正在用java中的跳過列表實現。基本上一切正常，但put方法需要太長的時間來執行。這裏是我的代碼，我已經通過教程並查看了一些人的代碼，我似乎沒有看到問題出在哪裏（如果您測量放置100000個隨機元素需要幾年才能運行）。Java跳過列表實現優化

public class SkipList<K,V> { 

    private final SkipListItem<K,V> head; 
    private int currentLevel = 0; 
    private static final Random random = new Random(); 
    private int height = 0; 

    public SkipList() { 
     this.head = new SkipListItem<>(null, null); 
    } 

    public V put(K key, V value) { 
     return this.put(key, value, null, 0); 
    } 

    private V put(K key, V value, SkipListItem<K,V> previous, int level) { 
     if(level > this.height) { 
      for(int i=0,s=level-this.height ; i<s ; ++i) { 
       this.addHeadItem(); 
      } 
     } 
     SkipListItem<K,V> addedItem = new SkipListItem<>(key, value); 
     SkipListItem<K,V> insertAfter = this.findLowerItem(key, level); 
     addedItem.setPrevious(insertAfter); 
     if(insertAfter.getNext() != null) { 
      insertAfter.getNext().setPrevious(addedItem); 
      addedItem.setNext(insertAfter.getNext()); 
     } 
     insertAfter.setNext(addedItem); 
     if(previous != null) { 
      addedItem.setBelow(previous); 
      previous.setAbove(addedItem); 
     } 

     return (SkipList.random.nextBoolean()) ? this.put(key, value, addedItem, level+1) : value ; 
    } 

    private void addHeadItem() { 
     SkipListItem<K,V> item = this.head; 
     while(item.getAbove() != null) { 
      item = item.getAbove(); 
     } 
     SkipListItem<K,V> newHead = new SkipListItem<>(null,null); 
     item.setAbove(newHead); 
     newHead.setBelow(item); 
     ++this.height; 
    } 

    private SkipListItem<K,V> findLowerItem(K key) { 
     return this.findLowerItem(key,0); 
    } 

    private SkipListItem<K,V> findLowerItem(K key, int level) { 
     SkipListItem<K,V> currentItem = this.head; 
     for(int i=0 ; i<level ; ++i) { 
      currentItem = currentItem.getAbove(); 
     } 
     while( currentItem.getNext() != null && 
       currentItem.getNext().getKey() != null && 
       currentItem.getNext().compareTo(key) < 0) { 
      currentItem = currentItem.getNext(); 
     } 
     return currentItem; 
    } 
    //...some other functions... 
}

有什麼想法爲什麼需要這麼長時間？

來源

2015-11-26 kcdsh

做一些方法分析。什麼需要這麼久？（http://stackoverflow.com/questions/2267594/java-profiling-how-can-i-get-a-method-by-method-analysis-of-my-application或一些手冊'System.nanoTime（）'聚合） – zapl

您可以包含「SkipListItem」的代碼嗎？ –

您是否嘗試了一步一步的調試以確保'put（）'的行爲符合預期（即使用索引而不是0級列表進行搜索並正確構建索引）？ –

乍一看，只要您插入新項目，您就有可能通過整個列表查找位置。這導致線性複雜性，因此最後插入n項目需要n*n操作。

特別是在你的情況下，最後的數字是10億美元的操作已經相當複雜，所以我可以想象這需要幾分鐘時間來填充。

來源

2015-11-26 16:14:53

@yshavit n^2 = n * n –

@SashaSalauyou哦，我的天哪。我讀了n * n，並將其視爲n^n。讓我在咖啡前檢查是否正確 – yshavit

Java跳過列表實現優化

回答

相關問題