Welche Klassen von Datenstrukturen können persistent gemacht werden?

Persistente Datenstrukturen sind unveränderliche Datenstrukturen. Operationen auf ihnen geben eine neue "Kopie" der Datenstruktur zurück, die jedoch durch die Operation geändert wurde. Die alte Datenstruktur bleibt jedoch unverändert. Effizienz wird im Allgemeinen dadurch erreicht, dass einige der zugrunde liegenden Daten gemeinsam genutzt werden und ein vollständiges Kopieren der Datenstruktur vermieden wird.

Fragen:

• Gibt es Ergebnisse zu Datenstrukturklassen, die persistent gemacht werden können (bei gleichbleibender oder sehr ähnlicher Komplexität)?

• Können alle Datenstrukturen persistent gemacht werden (unter Beibehaltung der gleichen oder sehr ähnlichen Komplexität)?

• Können Datenstrukturen bekanntermaßen nicht persistent gemacht werden (bei gleicher oder sehr ähnlicher Komplexität)?

Positives Ergebnis: Beharrlichkeit kostet nicht zu viel. Man kann zeigen, dass jede Datenstruktur mit höchstens einer Verlangsamung von vollständig persistent gemacht werden kann .$O(\lg n)$

Beweis: Sie können ein Array mit Hilfe von Standarddatenstrukturen (z. B. einem ausgeglichenen Binärbaum; weitere Informationen finden Sie am Ende dieser Antwort) dauerhaft machen. Dies verursacht eine Verlangsamung: jeder Array - Zugriff nimmt O ( lg n ) Zeit mit der persistenten Datenstruktur, anstelle von O ( 1 ) Zeit für den nicht-persistente - Array. Nehmen wir nun einen beliebigen zwingenden Algorithmus, dessen Laufzeit im RAM-Modell O ( f ( n ) ) ist , wobei n die Menge des verwendeten Speichers bezeichnet. Stellen Sie den gesamten Speicher als ein großes Array dar (mit$O(\lg n)$$O(\lg n)$$O(1)$$O(f(n))$$n$ Elemente), und machen Sie es mit einer persistenten Karte persistent. Jeder Schritt des imperativen Algorithmus führt zu höchstens einerVerlangsamung von O ( lg n ) , sodass die Gesamtlaufzeit O ( f ( n ) lg n ) beträgt.$n$$O(\lg n)$$O(f(n) \lg n)$

Anscheinend ist es möglich, es ein bisschen besser zu machen: Anscheinend kann man den Verlangsamungsfaktor auf (erwartete, abgeschriebene Zeit) reduzieren , indem man die Techniken aus dem unten genannten Demaine-Papier verwendet - aber ich kenne die Details nicht von dieser Arbeit, so kann ich nicht selbst dafür bürgen. Vielen Dank an jbapple für diese Beobachtung.$O(\lg \lg n)$

Negatives Ergebnis: Bei einigen Datenstrukturen können Sie eine gewisse Verlangsamung nicht vermeiden. Zur Beantwortung Ihrer dritten Frage gibt es Datenstrukturen, bei denen bekannt ist, dass die Persistenz zu einer gewissen Verlangsamung führt.

$n$$O(1)$$O(1)$$\Omega(\lg \lg n)$

• Konsequent persistente Versuche zur effizienten Versionskontrolle . Erik D. Demaine, Stefan Langerman und Eric Price. Algorithmica, Band 57, Nummer 3, 2010, Seiten 462–483.

Die Untergrenze wird Mihai Patrascu zugeschrieben, aber es gibt kein Zitat zu einer Quelle, die die Details des Beweises dieser behaupteten Untergrenze angibt.

$O(1)$

Es besteht auch ein enger Zusammenhang mit funktionalen Programmiersprachen. Insbesondere ist jede Datenstruktur, die rein funktional (ohne Mutationen) implementiert werden kann, bereits eine persistente Datenstruktur. (Das Gegenteil ist leider nicht unbedingt der Fall.) Wenn Sie die Augen zusammenknicken möchten, könnten Sie dies als eine Art schwachen Teilklassifikationssatz ansehen: Wenn er in einer rein funktionalen Programmiersprache mit denselben Zeitgrenzen wie in implementiert werden kann eine imperative Sprache, dann gibt es eine persistente Datenstruktur mit den gleichen Zeitgrenzen wie die nicht persistente. Mir ist klar, dass dies wahrscheinlich nicht das ist, wonach Sie gesucht haben - es ist meistens nur eine triviale Umformulierung der Situation.

$O(\lg n)$

$\ell$$d$$d$

$n$$O(\lg n)$$O(\lg n)$$O(\lg n)$

Weitere Erklärungen mit schönen Bildern finden Sie in den folgenden Quellen:

• Lesen Sie die Abschnitte "Binäre Suchbäume" und "Strukturen mit wahlfreiem Zugriff" (insbesondere die Baummethode) unter http://toves.org/books/persist/index.html .

• Oder lesen Sie http://netcode.ru/dotnet/?artID=6592#BinaryTrees und einige der folgenden Abschnitte.

• Oder lesen Sie die Abschnitte "Funktionale Datenstrukturen" und "Kopieren von Pfaden" (ab Seite 4) des oben genannten Demaine-Dokuments: http://erikdemaine.org/papers/ConfluentTries_Algorithmica/paper.pdf

Das gibt Ihnen die Hauptidee. Es gibt zusätzliche Details, um die man sich kümmern muss, aber die Details sind für diese Frage nicht relevant. Glücklicherweise ist dies alles Standard, und in der Literatur finden Sie viele Informationen zum Aufbau solcher Datenstrukturen. Sie können auch eine separate Frage stellen, wenn die oben genannten Ressourcen nicht ausreichen und Sie weitere Informationen zum Erstellen einer persistenten Array-Datenstruktur benötigen.