Я борюсь с реализацией списка пропусков в java. В основном все работает нормально, но метод 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...
}
есть идеи, почему так долго?
System.nanoTime()
агрегацию) - person zapl   schedule 26.11.2015SkipListItem
? - person Paul Boddington   schedule 26.11.2015put()
ведет себя так, как задумано (т. е. ищет с использованием индекса, а не списка 0-го уровня, и правильно строит индекс)? - person Alex Salauyou   schedule 26.11.2015put()
- когдаlevel = 0
, верхние уровни не задействованы. Чтобы заставить его работать,findLowerItem()
должен сначала искать на верхнем уровне (уровень = высота), затем все ниже и ниже, пока не будет достигнут заданный уровень. - person Alex Salauyou   schedule 26.11.2015