Zugriff auf Skiplisten-Element mit gegebenem Index in O(log(n))
-
Hallo,
genau, den Index als zweiten Key mitspeichern war auch meine erste Idee. Geht aber nicht, weil du beim Einfügen/Löschen in der Mitte alle danach folgenden Elemente aktualisieren musst, was offensichtlich wieder in O(n) liegt.
Der Baum ist wie gesagt m.E. ein Cheat (wenn es nicht anders geht, werde ich den aber natürlich nehmen).
Chris
-
ChrisM schrieb:
Hallo,
genau, den Index als zweiten Key mitspeichern war auch meine erste Idee. Geht aber nicht, weil du beim Einfügen/Löschen in der Mitte alle danach folgenden Elemente aktualisieren musst, was offensichtlich wieder in O(n) liegt.
Der Baum ist wie gesagt m.E. ein Cheat (wenn es nicht anders geht, werde ich den aber natürlich nehmen).
Chris
Hi,
wie gesagt, wenn du ein Element rauslöschst oder einfügst musst du von dem entsprechenden Element wieder den Index bestimmen, dazu bräuchtest du ja noch einen Baum der die Knoten auf ihre Indizes "abbildet", aber das wäre nicht das Problem, das Problem ist die Indizes ändern sich wieder, dieses mal jedoch in dem Look-Up Baum und du musst da in Θ(n) den Baum aktualisieren.
Mit Speichern der Indizes musst du immer die Indizes nach jedem Löschen/Einfügen aktualisieren und das liegt leider in Θ(n), es sei denn du hast noch eine Idee, die ich gerade nicht habe.
-
was ist, wenn du die indizes relativ zur höheren ebene speicherst?
beispiel: ebene 0 hat ein elemnt mit wert 10 (es überspring 10 elemente). eins tiefer ist es ebenso noch 10. aber das nächste element der liste der ebene 1 speichert nicht 15 sondern 5, da es 5 weitere element überspringt und nur die differenz gespeichert wird.
damit musst du nur sehr ca 2*log(n) element aktualisieren. ist aber ungetestet und eine erste idee.
-
Hallo,
naja, das habe ich leider vergessen zu erwähnen: "Index" bezieht sich auf eine gedachte Indizierung in der untersten Ebene der Skipliste. Also keine mehrdimensionalen Indizies oder ähnliches.
Chris
-
ChrisM schrieb:
Hallo,
naja, das habe ich leider vergessen zu erwähnen: "Index" bezieht sich auf eine gedachte Indizierung in der untersten Ebene der Skipliste. Also keine mehrdimensionalen Indizies oder ähnliches.
Chris
Hallo,
hast du dich denn schon einmal bei einem/dem Zuständigen erkundigt, ob es sich dabei nicht um einen Fehler in der Aufgabe handelt bzw. ob der/diese selbst (bereits) eine Lösung haben?
-
ich hab nur kurz draufgeschaut, aber ich denke schon, dass sich das lösen lässt.
edit: im prinzip hatte ich die gleiche idee wie besserwisser
@chrisM: wo genau siehst du da probleme? ich verstehe deinen einwand nicht.
-
Hallo,
okay, ich glaube, ich habe das Prinzip jetzt verstanden. Im wesentlichen läuft es halt darauf hinaus, dass man beim Einfügen und Löschen trotzdem viel Aufwand hat (aber halt nur ~log n Elemente anfassen muss).
Danke auf jeden Fall!
Christian
-
besserwisser schrieb:
was ist, wenn du die indizes relativ zur höheren ebene speicherst?
beispiel: ebene 0 hat ein elemnt mit wert 10 (es überspring 10 elemente). eins tiefer ist es ebenso noch 10. aber das nächste element der liste der ebene 1 speichert nicht 15 sondern 5, da es 5 weitere element überspringt und nur die differenz gespeichert wird.
damit musst du nur sehr ca 2*log(n) element aktualisieren. ist aber ungetestet und eine erste idee.
Bin ich der einzige der dieser Beschreibung nicht wirklich folgen kann?
-
Dipl. Inf. Doktor schrieb:
besserwisser schrieb:
was ist, wenn du die indizes relativ zur höheren ebene speicherst?
beispiel: ebene 0 hat ein elemnt mit wert 10 (es überspring 10 elemente). eins tiefer ist es ebenso noch 10. aber das nächste element der liste der ebene 1 speichert nicht 15 sondern 5, da es 5 weitere element überspringt und nur die differenz gespeichert wird.
damit musst du nur sehr ca 2*log(n) element aktualisieren. ist aber ungetestet und eine erste idee.
Bin ich der einzige der dieser Beschreibung nicht wirklich folgen kann?
ich beschreib mal meine idee, ich denke besserwisser meinte dasselbe.
Jeder Knoten weiß, wieviele Knoten übersprungen werden, wenn man von dort aus einen schritt in der liste weiter geht. Auf dem untersten Level werden natürlich keine Knoten übersprungen, auf den höheren Leveln natürlich schon.Diese Information ist weitgehend lokal, wenn ein Element gelöscht oder entfernt wird, muß man auf jedem der log n level den Knoten, der links vom gelöschten/entfernten Knoten liegt updaten.
-
Hallo,
genau so habe ich das auch verstanden.
Bei jeder horizontalen Verknüpfung speicherst du mit ab, wie viele Elemente diese Verknüpfung überspringt. In einer perfekten Skipliste waren das 1, 2, 4, 8, usw. (von "unten"). In der randomisierten muss man diese Zahlen natürlich immer anpassen, wenn man ein Element einfügt oder entfernt. Da man aber nirgends absolute Indizes speichert, muss man nicht alle Sprungweiten aktualisieren, sondern nur die, die über die bearbeitete Stelle darüberspringen (also genaue eine horizontale Verknüpfung auf jeder Höhe).
Das Suchen eines Indizies läuft dann ähnlich zur Schlüsselsuche: Du startest beim ersten Element auf der höchsten Ebene und prüfst, ob die Sprungweite kleinergleich deinem Index ist. Falls ja, springst du und subtrahierst die Sprungweite von deinem Index (bzw. das ist dann ne Hilfsvariable), ansonsten gehst du eine Ebene nach unten. Irgendwann bist du unten und damit beim Zielelement. Oder alternativ auf dem letzten Element mit der Hilfsvariable > 0 (dann war der Index außerhalb der Liste).
Viele Grüße
ChrisPS: Danke nochmal, wär ich so wahrscheinlich nicht drauf gekommen.
-
genau so war es gemeint. ich würde zwar den knoten als rechts bezeichnen, aber im endeffekt gibt es rechts oder links eh nicht. *g*
es ist jedenfalls immer der knoten, den man bei jedem schritt als zu groß betrachtet hat und deshalb an dessen vorgänger einen schritt tiefer ging. man löscht ja ein element zw. diesen beiden knoten, wobei damit der rechte knoten ein element weniger überspringt. beim einfügen muss man den wert des nächsten knoten erhöhen, da man ja zw. beiden knoten einen neuen einfügt und der nächste knoten damit einen knoten mehr überspringt.
ich hoffe, dass das jetzt klarer ist. solche algorithmen zu schreiben ist nicht so einfach.