Wie funktioniert eine Sprungliste?

Für eine Hausaufgabe muss ich verstehen, wie eine Sprungliste funktioniert.

Ich programmiere jetzt seit etwas mehr als 2 Jahren (ich weiß, dass das in Wirklichkeit nicht so lange dauert), und ich habe noch nie von einer Sprungliste gehört.

Ich habe alle Anleitungen durchgesehen, die ich finden kann, und verstehe immer noch kaum, wie sie funktionieren. Ich habe sogar in Code Review nach einer Beispielimplementierung gesucht und nur eine Überprüfung gefunden. und es ist nicht einmal eine vollständige Implementierung. Ich habe mir die Beispielimplementierung angesehen, die der Kurs geliefert hat, und sie ist absolut grausam. Ich habe keine Ahnung, wie es funktioniert, obwohl es keine geeigneten Methoden und Variablennamen mit einem Buchstaben gibt.

Wie funktioniert eine Sprungliste? Ist die Kenntnis einer Skip-Liste erforderlich, um fortgeschrittenere Datenstrukturen zu verstehen?

In früheren Tagen haben wir in Datenstrukturkursen gelernt, wie AVL-Bäume funktionieren . Ich hätte das in einer meiner Klassen gehabt, aber der Ausbilder sagte "Du wirst das nie wirklich benutzen" und ließ uns stattdessen 2-3 Bäume und B * -Bäume lernen. Das waren Tage, in denen der Speicher knapp war und die Prozesse einzeln abliefen. Sie haben keine Deque verwendet, wenn eine einfach verknüpfte Liste genauso gut funktioniert.

Die Überspringliste ist heutzutage weit verbreitet, da mehr verfügbarer Speicher und Parallelität ein Problem darstellen (Sie müssen nicht viel sperren, wenn Sie als Verfasser einer Überspringliste fungieren - im Vergleich zu allem, was mit einem AVL-Baum zu tun hat).

Ehrlich gesagt, ist es jetzt meine Lieblingsdatenstruktur, da ich leicht überlegen kann, wie es darunter funktioniert und wo es vorteilhaft oder nachteilig zu verwenden ist.

Sie müssen keinen von Grund auf neu schreiben (es sei denn, Sie erhalten ihn als Interviewfrage - aber dann werden Sie wahrscheinlich auch einen AVL-Baum implementieren).

Sie werden gehen zu müssen , verstehen , warum Sie eine auswählen möchten ConcurrentSkipListMapin Java , anstatt ein HashMapoder TreeMapoder eines der anderen Karten Implementierungen.

Um zu verstehen, wie es funktioniert, müssen Sie verstehen, wie ein Binärbaum funktioniert. Warten Sie, lassen Sie mich das ändern. Sie müssen verstehen, wie ein ausgeglichener Binärbaum funktioniert. Ohne einen Binärbaum auszugleichen, erhalten Sie mit seiner Suche keinen wirklichen Vorteil.

Nehmen wir an, wir haben diesen Baum:

Und wir fügen eine '8' ein. Jetzt haben wir:

Und das ist nicht ausgeglichen. Also machen wir den Zauber, ihn über eine Implementierung auszugleichen ...

Und du hast wieder einen ausgeglichenen Baum. Aber das war eine Menge Magie. Ich winkte mit der Hand.

Lassen Sie uns eine Liste überspringen.

Dieser ist ein idealisierter. Nur wenige sind es, aber es zeigt die ausgeglichene binäre Baumnatur, die der ideale Skifahrer annähert.

Nun wollen wir dort eine 6 einfügen. Dies fügt es ähnlich wie eine verknüpfte Liste ein. Wir beginnen aber oben und gehen runter. Die oberen Punkte bis 5. Ist 6> 5? Ja. Ok, die Spitze zeigt jetzt bis zum Ende, also gehen wir den Stapel runter (wir sind auf der 5). Der nächste ist 7. Ist 6> 7? Nee. Also gehen wir eine Ebene runter und sind auf der Basisebene, also fügen wir 6 rechts von der 5 ein.

Wir werfen eine Münze um - Köpfe, die wir bauen, Schwänze, die wir bleiben. Schwänze. Es muss nichts mehr getan werden.

Fügen wir die 8 jetzt ein. 8> 5 & le; ja. 8> 7 & le; Ja. Und jetzt sind wir wieder auf der untersten Ebene, nachdem wir den Pfeilen und dem Stapel gefolgt sind, und wir testen 8> 11? Nee. Also fügen wir die 8 rechts von der 7 ein.

Wir werfen eine Münze um - Köpfe, die wir bauen, Schwänze, die wir bleiben. Schwänze. Es muss nichts mehr getan werden.

Im ausgeglichenen Baum würden wir uns darüber aufregen, dass der Baum jetzt nicht ausgeglichen ist. Aber dies ist kein Baum - es ist eine Überspringliste. Wir nähern uns einem ausgeglichenen Baum.

Fügen wir nun eine 10 ein. Ich vermeide alle Vergleiche.

Wir werfen eine Münze um - Köpfe, die wir bauen, Schwänze, die wir bleiben. Köpfe! Und drehen Sie es noch einmal, Köpfe wieder! Dreh es nochmal um, ok, da ist ein Schwanz. Zwei Ebenen über der verknüpften Basisliste.

Der Vorteil hierbei ist , dass jetzt , wenn wir ein 12 einzufügen gehen, können wir überspringen von 5 bis 10 , ohne dabei all die anderen Vergleichen. Wir können sie mit der Überspringliste überspringen. Und wir müssen uns keine Sorgen um den ausgeglichenen Baum machen - die Wahrscheinlichkeit des Stapelns macht das für uns.

Warum ist das so nützlich? Denn beim Einfügen der 10 kann ich das tun, indem ich den Schreibzugriff auf die Zeiger 5 und 7 und 8 und nicht auf die gesamte Struktur sperre. Und während ich das tue, können die Leser immer noch die Überspringliste durchgehen, ohne einen inkonsistenten Zustand zu haben. Bei gleichzeitiger Nutzung ist es schneller, wenn Sie nicht sperren müssen. Wenn Sie über die unterste Ebene iterieren, ist dies schneller als ein Baum (die Vorteile der BFS- und DFS-Algorithmen für die Baumnavigation - Sie müssen sich nicht darum kümmern).

Wirst du es antreffen? Sie werden es wahrscheinlich an einigen Stellen im Einsatz sehen. Und dann wissen Sie, warum sich der Autor für diese Implementierung und nicht für a TreeMapoder HashMapfür die Struktur entschieden hat.

Ein Großteil davon wurde aus meinem Blog-Beitrag " The Skip List" ausgeliehen