Unveränderliche Datenstrukturen Leistung

Question

Ich verstehe nicht, wie etwas als Set unveränderlich sein kann und immer noch eine akzeptable Leistung haben.

Von dem, was ich in F # Sets intern gelesen habe, verwenden Sie Red Black Trees als ihre Implementierung. Wenn wir jedes Mal etwas Neues zu einem Red Black Tree hinzufügen wollen, müssen wir es grundlegend neu erschaffen, wie kann es jemals eine gute Leistung haben? Was fehlt mir hier?

Obwohl ich dies für F # 's Sets frage, denke ich, dass dies in jeder anderen Sprache relevant ist, die unveränderliche Datenstrukturen verwendet oder verwendet.

Dank

Answer 1

Fast alle unveränderlichen Sammlungen sind eine Form des ausgewogenen Baumes. Um einen neuen Baum zu erstellen, müssen Sie Knoten auf dem Pfad von der Änderung (Einfügen, Entfernen, "Aktualisieren") in den Stamm neu zuweisen. Solange der Baum balanciert ist, benötigt er logarithmische Zeit. Wenn Sie so etwas wie einen 2-3-4-Baum (ähnlich rot-schwarzen Bäumen) mit einem erwarteten outdegree drei haben, können Sie eine Million Elemente mit nur 10 Zuordnungen verarbeiten.

Und in Sprachen, in denen Datenstrukturen rein erwartet werden, sorgen sie für eine schnelle Zuordnung. Die Zuweisung eines Vier-Elemente-Knotens kostet einen Vergleich, ein Inkrement und vier Speicher. Und in vielen Fällen können Sie die Kosten eines Vergleichs über mehrere Zuweisungen amortisieren.

Wenn Sie mehr darüber wissen möchten, wie diese Strukturen funktionieren, ist eine ausgezeichnete Quelle Purely Functional Data Structures von Chris Okasaki.

Answer 2

Die Grenzen der Sprache Semantik bezieht sich nur auf den Quellcode in der Sprache. Die Implementierung (Compiler, Interpreter, Laufzeitumgebung usw.) kann frei tun, was immer sie für die beste Leistung wünscht, solange sie das gleiche Verhalten behält. Dies gilt für die meisten Sprachen.

Edit:

Mehrere Optimierungen können mit Datenfreigabe vorgenommen werden (gerade weil die Daten unveränderlich sind), hinter den Kulissen mit Veränderlichkeit, Endrekursion Optimierung (seit FP viel Rekursion verwendet) und andere.

Answer 3

nicht sicher, wie dies in der Sprache implementiert ist, aber die Datenstrukturen könnten als unveränderlich für den Programmierer wahrgenommen werden, aber hinter den Kulissen optimiert werden.

zum Beispiel habe ich eine Liste a = [1,2,3,4,5]. Ich füge 6. b = [a [6]] an und sie können beide unveränderlich sein. Sie verlieren dadurch keine Performance, und es ist schneller als das Kopieren der Werte.

Also, lassen Sie mich Sie fragen, weil ich nicht weiß, warum würde es langsamer sein, Dinge als unveränderlich zu tun? Im Fall des Baumes sehe ich deinen Standpunkt. Sie müßten Knoten oberhalb des aktuellen Knotens erstellen, den ich vermute, aber nicht darunter (vorausgesetzt, wir haben Kinderzeiger und keine Elternzeiger).

Answer 4

Sie müssen nicht den gesamten Baum neu erstellen. Viele Filialen bleiben gleich und können "wiederverwendet" werden. Als einfaches Beispiel, wenn der neue Knoten zu einem Blatt in der aktuellen Baumstruktur hinzugefügt werden muss, müssen nur die Eltern dieses Knotens geklont und neue Zweige gegeben werden.

Answer 5

Ganz einfach ist ein Set eine knotenbasierte Speichereinheit. Im Falle eines Sets können Sie es als einen Baum implementieren, in dem Sie nicht alle Kanten und Knoten neu erstellen, wenn Sie ein Element zur nächsten Version des Sets hinzufügen, stattdessen erstellen Sie einfach einen neuen Satz von Kanten . Sie können dies tun, da sich die Knoten selbst niemals ändern werden, noch werden die Objekte in ihnen bleiben.

Der echte Vorteil, den es in Single-Thread-Anwendungen, sondern in Multi-Thread-Anwendungen gefunden hat. Unveränderbare Datenstrukturen machen die Notwendigkeit von Sperrmechanismen überflüssig. Wenn sie sich nie ändern, müssen Sie sich keine Sorgen um den Zustand machen.

Answer 6

Wie andere darauf hingewiesen haben, müssen Sie nicht die gesamte Datenstruktur neu erstellen. Sie müssen nur Teile neu erstellen, die sich geändert haben, und auf vorhandene Teilbäume verweisen, die gleich geblieben sind. Dank der Unveränderlichkeit der Datenstruktur können Sie Sub-Bäume wiederverwenden, so dass das Kopieren fast nie nötig ist. In der Tat, wenn Sie eine veränderbare Datenstruktur nur selten klonen müssten, könnte dies viel größere Auswirkungen haben.

Insbesondere für ein gut kompensiert Bäume (wie Rot-Schwarz-Bäume), das gibt Ihnen:

• O (log N) Zeit der Hinzufügen/Entfernen von Elementen aus der Menge (gleich wie änderbare Implementierung
)
• O (log N) Raum (Neudotierungen) beim Hinzufügen/Entfernen von Elementen (wandelbar O hätte (1))

Dies kann - natürlich - zu viel Aufwand für einige applic Aber es ist eigentlich gar nicht so schlimm. Darüber hinaus ist die Zuordnung in .NET Garbage Collector sehr schnell (ich denke, im Wesentlichen O (1)), so ist dies nicht wirklich ein Problem. Mehr Zuweisung bedeutet, dass GC häufiger ausgeführt werden muss, aber dies ist auch nicht so kritisch wie es klingen mag - Computer haben heutzutage eine Menge Speicher. Die .NET 4.0 hilft in vielen Fällen tatsächlich (siehe auch Jon Harrop's answer here)

Answer 7

Siehe

functional programming: immutable data structure efficiency

(vor allem meine Antwort, die Rich Hickey Vortrag Punkte) für die ‚allgemeine‘ überzeugende Beweise, dass ja, unveränderliche Strukturen auch sehr effizient sein kann.

Wie gut das im konkreten Fall von F # Set, na ja, vielleicht nur mäßig so heute gilt. Es wäre großartig, eine effizientere zugrunde liegende Struktur zu verwenden (in pragmatischen Begriffen; theoretisch ist alles O (logN) (was in der Praxis O(1)) ist).

Answer 8

Wie andere angegeben haben, ist eine unveränderliche Datenstruktur doesn "Sie müssen vollständig neu erstellt werden, da sie alte Teile von sich selbst wiederverwenden kann. Sie können dies tun, weil die alten Teile unveränderlich sind und die Daten sich garantiert nicht ändern.

Ich habe ein realistisches Beispiel für unveränderliche Leistung Ich habe ein paar Tests mit einem immutable Red Black tree gemacht, das ich in F # gemacht habe und es läuft nur 3 mal langsamer als std :: sort in C++, was ich wirklich schnell finde, wenn man bedenkt, dass es nicht speziell zum Sortieren entwickelt wurde.