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跳过列表实现优化

回答

相关问题