Zugriff auf Skiplisten-Element mit gegebenem Index in O(log(n))

ChrisM

Hallo,

eigentlich sagt das Topic schon alles:

Ich möchte in einer Skipliste das x-te Element in O(log(n)) finden. Die Skipliste ist nicht perfekt, sondern randomisiert (sonst wäre es einfach, wenn man zusätzlich noch irgendwo die Anzahl der Elemente protokolliert). Ihre Struktur darf aber modifiziert werden (die Komplexität natürlich nicht, also Einfügen/Löschen/Schlüsselsuche weiterhin in O(log(n)). Das Element soll natürlich deterministisch und 100% korrekt gefunden werden, also ist der Ansatz für die perfekte Skipliste nicht einfach mit einer bestimmten Fehlerwahrscheinlichkeit bzw. Abweichung übertragbar.

Das ist die Aufgabe auf einem Übungsblatt für die Uni, weswegen ich hier keine Lösung oder Tipps haben möchte.

Ich möchte nur wissen, ob noch jemand der Meinung ist, dass die Aufgabe für eine randomisierte Skipliste unlösbar ist oder ob jemand eine Lösung kennt (ohne sie zu sagen!).

EDIT: Squolly hatte die Idee, einfach hilfsweise einen Baum zu verwenden. Das ist natürlich nicht erlaubt (nehme ich an)

Viele Grüße
Christian

Wäre es nicht möglich die Inidices mit in die Knoten zu speichern? So liese sich beim Suchen nach einem Index das Element in log(n) finden, aber dann hätte man noch das Problem den Index beim Einfügen und Löschen in log(n) zu aktualisieren was imho nicht möglich ist.

Alternativ könnte man einen RBTree, o.ä., nutzen und in diesem <Index,Pointer> Paare speichern, ihn nach Inidzes sortieren und in log(n) den entsprechenden Index löschen. Hätte, dann aber wieder das Problem den Index eines einzufügenden/löschenden Elements in log(n) rauszufinden.

Ne, also ich wüsste nicht wie man es hinbekommen soll. Man müsste schon in jedem Knoten wissen wo er sitzt und das ändert sich ja durch einfügen und löschen, wodurch man in Θ(n) liegt.

Nein, also ich halte es für nicht möglich.

ChrisM

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.

ChrisM

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?

Jester

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.

ChrisM

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?

Jester

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.

ChrisM

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
Chris

PS: 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.