Einfache Bestellung für eine verkettete Liste

Question

Ich möchte eine doppelt verkettete Liste mit einer Reihenfolge (ein Integer-Attribut) erstellen, so dass die Sortierung nach der Reihenfolge der Reihenfolge ein Array erstellen könnte, das effektiv der verknüpften Liste entsprechen würde.

given: a <-> b <-> c 

a.index > b.index 
b.index > c.index 

Dieser Index müsste effizient viele Einfügungen handhaben.

Gibt es einen bekannten Algorithmus, um dies zu erreichen? Das Problem ist, wenn die Liste groß wird und die Index-Sequenz gepackt wurde. In dieser Situation muss die Liste gescannt werden, um die Lücke wieder herzustellen. Ich bin mir einfach nicht sicher, wie dies erreicht werden soll. Idealerweise würde es eine Art automatischen Ausgleich geben, so dass diese Kreditaufnahme sowohl schnell als auch selten ist.

Die naive Lösung, alle linken oder rechten Indecies um 1 zu ändern, um Platz für das Insert zu schaffen, ist O (n).

Ich würde es vorziehen, Ganzzahlen zu verwenden, wie ich weiß Zahlen tendenziell weniger zuverlässig in Fließkommazahl, wie sie in den meisten Implementierungen Null erreichen.

Answer 1

Dies ist eines meiner Lieblingsprobleme. In der Literatur heißt das "Online List Labelling" oder einfach "List Labelling". Es gibt ein bisschen darauf in Wikipedia hier: https://en.wikipedia.org/wiki/Order-maintenance_problem#List-labeling

Wahrscheinlich der einfachste Algorithmus, der für Ihre Zwecke praktisch sein wird, ist der erste hier: https://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf.

Es verarbeitet Einfügungen in amortisierten O (log N) -Zeit, und um N Elemente zu verwalten, müssen Sie Integer verwenden, die groß genug sind, um N^2 zu halten. 64-Bit-Ganzzahlen sind in fast allen praktischen Fällen ausreichend.

Answer 2

Was ich in die Wege leitete, war eine Roll-meine-eigene Lösung, weil es so aussah, als ob der Algorithmus die gesamte Liste im Speicher haben wollte, bevor sie den nächsten Knoten einfügen würde. Und das ist nicht gut.

Meine Idee ist es, einige der Ideen für den Algorithmus zu leihen. Was ich getan habe, war Ids zu machen und Aufträge zu sortieren. Dann ist der Algorithmus faul und füllt Einträge überall dort, wo sie passen. Sobald irgendwo in irgendeinem kleinen Klumpen kein Platz mehr ist, beginnt ein Scan auf und ab von dem Klumpen und versucht, einen gleichmäßigen Abstand zu schaffen, so dass, wenn n Objekte gescannt werden, sie einen n^2 Abstand zwischen ihnen teilen müssen.

In der Theorie wird dies bedeuten, dass die Liste im Laufe der Zeit perfekt aufgefüllt wird, und da meine IDs Ints sind und meine Sortierreihenfolgen lang sind, wird es niemals ein Szenario geben, in dem Sie kein n^2 Padding erreichen können . Ich kann nicht mit den oberen Grenzen der Anzahl der Operationen sprechen, aber meine Eingeweide sagen mir, dass ich mit Polynomarbeit bei 1/Polynomfrequenz gut zurecht komme.