0

我正在努力使用 java 中的 skiplist 实现。基本上一切正常，但put方法执行时间太长。这是我的代码，我浏览过教程并查看了一些人的代码，但我似乎看不出问题出在哪里（如果您测量放置 100000 个随机元素需要很长时间才能工作）。

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...
}

任何想法为什么要花这么长时间？

4

1 回答 1

1

乍一看，每当您插入新项目时，您都可能会遍历整个列表以找到位置。这会导致线性复杂性，因此最后插入n项目需要n*n操作。

特别是在您的情况下，最终数字是 100 亿次操作已经非常复杂，所以我可以想象这将需要几分钟来填充。

于 2015-11-26T16:14:53.670 回答