java - Javaにはスキップリストの実装がありますか

Question

ConcurrentSkipListSetスキップリストでバックアップされているJava Collection Frameworkで見つけました。しかし、Javaにスキップリストはありますか? 私のユースケースではセットが機能しません。重複をサポートするインデックス可能なリストが必要です。

Answer 1

この回答は3年遅れていますが、現時点からJavaスキップリストが必要な人に役立つことを願っています:)

このソリューションは、あなたが尋ねたように重複を許可します。ここのガイドに大まかに従っていますhttp://igoro.com/archive/skip-lists-are-fascinating、したがって、複雑さはそれと似ていますが、削除コスト O(nlogn) を除いて-二重リンクを使用することを気にしなかったためですそうすることで、O(logn) まで削除されると思います。

コードは、インターフェイス、インターフェイスを実装するスキップ リスト、およびノー​​ド クラスで構成されます。また、一般的です。

パラメータLEVELSをパフォーマンスのために調整できますが、空間と時間のトレードオフに注意してください。

import java.util.Random;

interface SkippableList<T extends Comparable<? super T>> {
    int LEVELS = 5;

    boolean delete(T target);
    void print();
    void insert(T data);
    SkipNode<T> search(T data);
}

public class SkipList<T extends Comparable<? super T>> implements SkippableList<T> {

    public static void main(String[] args) {
        SkipList<Integer> sl = new SkipList<>();
        int[] data = {4,2,7,0,9,1,3,7,3,4,5,6,0,2,8};
        for (int i : data) {
            sl.insert(i);
        }

        sl.print();
        sl.search(4);

        sl.delete(9);
        sl.print();

        sl.insert(69);
        sl.print();
        sl.search(69);
    }

    private final SkipNode<T> head = new SkipNode<>(null);
    private final Random rand = new Random();

    @Override
    public void insert(T data) {
        SkipNode<T> SkipNode = new SkipNode<>(data);
        for (int i = 0; i < LEVELS; i++) {
            if (rand.nextInt((int) Math.pow(2, i)) == 0) { //insert with prob = 1/(2^i)
                insert(SkipNode, i);
            }
        }
    }

    @Override
    public boolean delete(T target) {
        System.out.println("Deleting " + target.toString());
        SkipNode<T> victim = search(target, false);
        if (victim == null) return false;
        victim.data = null;

        for (int i = 0; i < LEVELS; i++) {
            head.refreshAfterDelete(i);
        }

        System.out.println();
        return true;
    }

    @Override
    public SkipNode<T> search(T data) {
        return search(data, true);
    }

    @Override
    public void print() {
        for (int i = 0; i < LEVELS; i++) {
            head.print(i);
        }

        System.out.println();
    }

    private void insert(SkipNode<T> SkipNode, int level) {
        head.insert(SkipNode, level);
    }

    private SkipNode<T> search(T data, boolean print) {
        SkipNode<T> result = null;
        for (int i = LEVELS-1; i >= 0; i--) {
            if ((result = head.search(data, i, print)) != null) {
                if (print) {
                    System.out.println("Found " + data.toString() + " at level " + i + ", so stoppped" );
                    System.out.println();
                }

                break;
            }
        }

        return result;
    }

}

class SkipNode<N extends Comparable<? super N>> {

    N data;
    @SuppressWarnings("unchecked")
    SkipNode<N>[] next = (SkipNode<N>[]) new SkipNode[SkippableList.LEVELS];

    SkipNode(N data) {
        this.data = data;
    }

    void refreshAfterDelete(int level) {
        SkipNode<N> current = this.getNext(level);
        while (current != null && current.getNext(level) != null) {
            if (current.getNext(level).data == null) {
                SkipNode<N> successor = current.getNext(level).getNext(level);
                current.setNext(successor, level);
                return;
            }

            current = current.getNext(level);
        }
    }

    void setNext(SkipNode<N> next, int level) {
        this.next[level] = next;
    }

    SkipNode<N> getNext(int level) {
        return this.next[level];
    }

    SkipNode<N> search(N data, int level, boolean print) {
        if (print) {
            System.out.print("Searching for: " + data + " at ");
            print(level);
        }

        SkipNode<N> result = null;
        SkipNode<N> current = this.getNext(level);
        while (current != null && current.data.compareTo(data) < 1) {
            if (current.data.equals(data)) {
                result = current;
                break;
            }

            current = current.getNext(level);
        }

        return result;
    }

    void insert(SkipNode<N> SkipNode, int level) {
        SkipNode<N> current = this.getNext(level);
        if (current == null) {
            this.setNext(SkipNode, level);
            return;
        }

        if (SkipNode.data.compareTo(current.data) < 1) {
            this.setNext(SkipNode, level);
            SkipNode.setNext(current, level);
            return;
        }

        while (current.getNext(level) != null && current.data.compareTo(SkipNode.data) < 1 && 
                current.getNext(level).data.compareTo(SkipNode.data) < 1) {

            current = current.getNext(level);
        }

        SkipNode<N> successor = current.getNext(level);
        current.setNext(SkipNode, level);
        SkipNode.setNext(successor, level);
    }

    void print(int level) {
        System.out.print("level " + level + ": [");
        int length = 0;
        SkipNode<N> current = this.getNext(level);
        while (current != null) {
            length++;
            System.out.print(current.data.toString() + " ");
            current = current.getNext(level);
        }

        System.out.println("], length: " + length);
    }

}

Answer 2

Indexable (迅速な取得が必要だと思います) であり、重複を許可する必要がある List について言及したので、おそらく LinkedList または ArrayList を使用してカスタム Set を使用することをお勧めします。

たとえば HashSet などの基本セットが必要で、それに値を追加し続ける必要があります。重複に直面した場合、そのセットの値はリストを指している必要があります。そのため、迅速な取得と、もちろん、疑似コレクションの方法でオブジェクトを保存することができます。

これにより、検索の効率が向上するはずです。理想的には、キーが重複していない場合、取得速度として O(1) を達成できます。

Answer 3

を作成するときはConcurrentSkipListSet、コンパレーターをコンストラクターに渡します。

new ConcurrentSkipListSet<>(new ExampleComparator());

public class ExampleComparator implements Comparator<Event> {//your impl }

SkipListSet通常のリストとして動作させるコンパレータを作成できます。

Answer 4

apache-collections の TreeList を使用し、それを Happy Java Libraries の SortedList で装飾することを承認します https://sourceforge.net/p/happy-guys/wiki/Sorted%20List/