Welche verknüpften Listendatenstrukturanpassungen würden mir eine schnelle zufällige Suche geben?

Question

Ich verwende derzeit eine doppelt verknüpfte Liste (C ++ - std::list) um eine Reihe von Datensätzen zu halten, die jeweils eine eindeutige Ganzzahl -Kennung haben. Die verknüpfte Liste wird in sortierter Reihenfolge so erstellt, dass in der Liste das nächste Element immer eine größere eindeutige Kennung als sein Vorgänger hat.

Das Problem, mit dem ich konfrontiert bin, ist, dass ich gelegentlich in der Lage sein muss, einen Artikel schnell in seine relativ sortierte Position einzufügen, und die Verwendung einer einfachen verknüpften Liste bedeutet, dass dieser Vorgang $ O (n) $ ist, was für mich Leistungsprobleme verursacht. Im Allgemeinen bedeutet dies, dass ich so etwas wie einen binären Baum verwenden möchte (C ++ std::map) Ich bin jedoch auch abhängig von der folgenden Funktion einer doppelt verknüpften Liste für eine gute Leistung:

• Fähigkeit, einen zusammenhängenden Abschnitt aus einer verknüpften Liste in eine andere in $ O (1) $ Time zu spleißen. (Amortisiert $ o (1) $ oder $ O ( log log n) $ wäre gut genug.)

Eine Merkmal meiner Daten, die ich nutzen möchte, ist, dass ich oft lange Bereiche an zusammenhängenden Datensätzen habe, in denen die einzigartige Ganzzahl der einzelnen einzigartigen Ganzen genau mehr als sein Vorgänger ist. Bei der Suche nach der relativ sortierten Position eines Elements wären sie immer außerhalb solcher zusammenhängenden Aufzeichnungen, da es keine doppelten Kennungen gibt.

Ich möchte eine Ersatzdatenstruktur oder -vergrößerung zu einer doppelt verknüpften Liste finden, mit der ich in konstanter Zeit weiterhin ganze Abschnitte von einer Liste zur anderen spleifen kann, aber die sortierte Position für ein neues Datensatz einfügen kann in besser als $ o (n) $ time.

Andere Operationen umfassen die Vorwärts- und Rückwärts -Iteration über die Elemente hinweg. Die Datensatzindizes beginnen bei Null und wachsen im Allgemeinen in Richtung 64 Bit auf, und der Code funktioniert in solchen Fällen gut. Gelegentlich sind einige Aufzeichnungen vor den folgenden nicht verfügbar. Es ist die Einführung dieser fehlenden Aufzeichnungen, die jetzt die Leistungsprobleme verursachen.

Ein möglicher Ansatz, der mir eintritt, besteht darin, den Ort mehrerer Indizes zu zwischenstrahlen. Der Cache würde ungültig werden, wenn ein Spleiß Elemente beseitigt, die möglicherweise die zwischengespeicherten Einträge überlappen. Anstatt eine lineare Suche durchzuführen, könnte die Suche stattdessen vom Cache -Point -Iterator beginnen, dessen eindeutiger Index dem am nächsten ist, dessen Position gesucht wird. Ich möchte jedoch die Funktion der zusammenhängenden Datensätze umfassender nutzen. Ich habe auch über eine hierarchisch verknüpfte Liste nachgedacht, in der ich eine auf höchste Ebene verknüpfte Liste von zusammenhängenden Regionen habe, in denen jede Region eine verlinkte Liste von Aufzeichnungen ist, die aufeinanderfolgend sind, aber ich habe keinen sauberen Weg gesehen, um eine verknüpfte Liste anzupassen, um diese bereitzustellen, um diese bereitzustellen Funktionalität. Vielleicht wurde so etwas schon einmal gemacht? Ich finde, dass Skip -Lists in der Nähe sind, aber nicht die Funktionalität von Splice () angezeigt werden, und eine generische Skip -Liste würde nicht die Tatsache nutzen, dass das Einsetzen niemals in zusammenhängenden Datensätzen auftritt.

Answer 1

Ein einfacher Ansatz könnte darin bestehen, eine doppelt verknüpfte Liste von Ausgriffen zu verwenden, wobei jeder Umfang eine Abfolge von zusammenhängenden Datensätzen darstellt. Die Datensätze in jedem Umfang könnten wiederum mit einer doppelt verknüpften Liste dargestellt werden.

Dies bewahrt Ihre Fähigkeit, $ O (1) $ Time Spleißen zu machen, und jetzt dauert der Einsatzbetrieb $ O (k) $ Zeit, wobei $ K $ die Anzahl der Ausmaßstäbe (statt $ o (n) $, wobei $ $ ist n $ ist die Anzahl der Datensätze). Wenn Sie viel weniger Ausmaß als Aufzeichnungen haben, könnte dies eine teilweise Verbesserung sein.

Ich weiß nicht, ob dies besser sein wird als eine einfache Skip -Liste oder ein binärer Baum.

Beachten Sie, dass Sie, wenn Sie einen binären Baum verwenden, dennoch effizientes Spleißen durchführen können. Der Spleißvorgang ist nicht mehr $ O (1) $ Zeit, aber es kann in $ o ( log ell) $ time durchgeführt werden, wobei $ ell $ die Anzahl der Datensätze im Spleißsegment ist. Dies ist nicht so schnell wie $ O (1) $ Time Spleißen, aber abhängig von der relativen Häufigkeit Ihrer unterschiedlichen Operationen können Sie eine weitere Datenstruktur berücksichtigen (z. B. Benchmark für realistische Datensätze).

Und natürlich könnten Sie diese Ideen, z. B. mit einem binären Baum aus dem Ausmaß, kombinieren, wo jedes Ausmaß wiederum eine doppelt verknüpfte Liste von zusammenhängenden Aufzeichnungen ist. Einsätze dauern $ o ( lg k) $ Zeit, und das Spleißen kann in $ o ( lg ell) $ time erfolgen einfacher binärer Baum).