CODEWITHSUNDEEP
javaoptimizationskip-lists
kcdsh
kcdsh

Reputation: 59

Java skiplist implementation optimization

Im strugling with skiplist implementation in java. Basically everything works fine but put method takes too long to perform. Here's my code, I've been through tutorials and viewed some people's codes and I don't seem to see where's the problem(If You measure putting 100000 random elements it takes ages to work).

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

any ideas why is it taking so long?

Upvotes: 0

Views: 1216

Answers (1)

Zbynek Vyskovsky - kvr000
Zbynek Vyskovsky - kvr000

Reputation: 18845

At the first sight, whenever you insert new item, you go potentially through the whole list to find the position. This leads to linear complexity, so at the end inserting n items require n*n operations.

Specifically in your case the final number is 10 billions operations already quite complex so I could imagine this will take minutes to populate.

Upvotes: 1

Related Questions