Gibt es eine praktische Möglichkeit, eine verknüpfte Knotenstruktur unveränderlich zu machen?

26

Ich beschloss, eine einfach verknüpfte Liste zu schreiben, und plante, die interne verknüpfte Knotenstruktur unveränderlich zu machen.

Ich bin allerdings auf einen Haken gestoßen. Angenommen, ich habe die folgenden verknüpften Knoten (aus früheren addVorgängen):

1 -> 2 -> 3 -> 4

und sagen, ich möchte eine anhängen 5.

Da der Knoten 4unveränderlich ist, muss ich dazu eine neue Kopie von erstellen 4, aber sein nextFeld durch einen neuen Knoten ersetzen, der a enthält 5. Das Problem ist jetzt, 3auf das alte zu verweisen 4; der ohne das angehängte 5. Jetzt muss ich kopieren 3und das nextFeld ersetzen, um auf die 4Kopie zu verweisen , aber jetzt 2wird auf die alte 3...

Mit anderen Worten, um einen Anhang zu erstellen, muss anscheinend die gesamte Liste kopiert werden.

Meine Fragen:

  • Ist mein Denken richtig? Gibt es eine Möglichkeit zum Anhängen, ohne die gesamte Struktur zu kopieren?

  • Anscheinend enthält "Effective Java" die Empfehlung:

    Klassen sollten unveränderlich sein, es sei denn, es gibt einen sehr guten Grund, sie veränderlich zu machen ...

    Ist dies ein guter Grund für die Wandlungsfähigkeit?

Ich denke nicht, dass dies ein Duplikat der vorgeschlagenen Antwort ist, da ich nicht über die Liste selbst spreche. das muss natürlich veränderbar sein, um mit der Schnittstelle übereinzustimmen (ohne die neue Liste intern zu behalten und über einen Getter abzurufen. Auf den zweiten Blick würde dies jedoch eine gewisse Veränderung erfordern; es würde nur auf ein Minimum beschränkt sein). Ich spreche darüber, ob die Interna der Liste unveränderlich sein müssen oder nicht.

Karzigenat
quelle
Ich würde ja sagen - die seltenen unveränderlichen Sammlungen in Java sind entweder solche mit Mutationsmethoden, die zum Werfen überschrieben werden, oder die unglaublich teuren CopyOnWritexxxKlassen, die für Multithreading verwendet werden. Niemand erwartet, dass Sammlungen wirklich unveränderlich sind (obwohl es einige Macken schafft)
Ordous
9
(Kommentar zum Zitat.) Das, ein großartiges Zitat, wird oft stark missverstanden. Die Unveränderlichkeit sollte wegen ihrer Vorteile auf ValueObject angewendet werden. Wenn Sie jedoch in Java entwickeln, ist es unpraktisch, die Unveränderlichkeit an Stellen zu verwenden, an denen eine Veränderlichkeit zu erwarten ist. Meistens hat eine Klasse bestimmte Aspekte, die unveränderlich sein sollten, und bestimmte Aspekte, die je nach Anforderungen veränderlich sein müssen.
RWONG
2
verwandt (möglicherweise ein Duplikat): Ist das Sammlungsobjekt besser unveränderlich? "Kann diese Sammlung (Klasse LinkedList) ohne Performance-Overheads als unveränderliche Sammlung eingeführt werden?"
Dienstag,
Warum würden Sie eine unveränderliche verknüpfte Liste erstellen? Der größte Vorteil einer verknüpften Liste ist die Wandlungsfähigkeit. Wären Sie mit einem Array nicht besser dran?
Pieter B
3
Können Sie mir bitte helfen, Ihre Anforderungen zu verstehen? Sie möchten eine unveränderliche Liste haben, die Sie mutieren möchten? Ist das nicht ein Widerspruch? Was meinst du mit "den Interna" der Liste? Meinen Sie damit, dass zuvor hinzugefügte Knoten später nicht mehr geändert werden dürfen, sondern nur das Anhängen an den letzten Knoten in der Liste zulassen?
Null

Antworten:

46

Bei Listen in funktionalen Sprachen arbeiten Sie fast immer mit Kopf und Schwanz, dem ersten Element und dem Rest der Liste. Das Voranstellen ist weitaus häufiger, da das Anhängen, wie Sie vermutet haben, das Kopieren der gesamten Liste (oder anderer verzögerter Datenstrukturen, die einer verknüpften Liste nicht genau ähneln) erfordert.

In imperativen Sprachen ist das Anhängen viel häufiger, da es sich semantisch natürlicher anfühlt und es Ihnen egal ist, ob Verweise auf frühere Versionen der Liste ungültig sind.

Als Beispiel dafür, warum beim Voranstellen nicht die gesamte Liste kopiert werden muss, gilt Folgendes:

2 -> 3 -> 4

Das Voranstellen von 1gibt Ihnen:

1 -> 2 -> 3 -> 4

Beachten Sie jedoch, dass es keine Rolle spielt, ob eine andere Person noch einen Verweis 2als Kopf ihrer Liste führt, da die Liste unveränderlich ist und die Links nur in eine Richtung verlaufen. Es gibt keine Möglichkeit festzustellen, 1ob das überhaupt vorhanden ist, wenn Sie nur einen Verweis darauf haben 2. Wenn Sie nun eine an eine der 5Listen anhängen, müssen Sie eine Kopie der gesamten Liste erstellen, da sie sonst auch in der anderen Liste angezeigt wird.

Karl Bielefeldt
quelle
Ahh, ein guter Punkt, warum das Voranstellen keine Kopie erfordert; Daran habe ich nicht gedacht.
Carcigenicate
17

Sie haben Recht, zum Anhängen muss die gesamte Liste kopiert werden, wenn Sie keine Knoten an Ort und Stelle mutieren möchten. Denn wir müssen den nextZeiger des (jetzt) ​​vorletzten Knotens setzen, der in einer unveränderlichen Einstellung einen neuen Knoten erzeugt, und dann den nextZeiger des vorletzten Knotens setzen und so weiter.

Ich denke, das Hauptproblem ist hier nicht die Unveränderlichkeit, noch ist die appendOperation schlecht beraten. Beide sind in ihren jeweiligen Domänen vollkommen in Ordnung. Sie zu mischen ist schlecht: Die natürliche (effiziente) Schnittstelle für eine unveränderliche Liste betont die Manipulation am Anfang der Liste, aber für veränderbare Listen ist es oft natürlicher, die Liste durch sukzessives Anhängen der Elemente vom ersten bis zum letzten zu erstellen.

Daher schlage ich vor, dass Sie sich entscheiden: Möchten Sie eine kurzlebige oder eine dauerhafte Schnittstelle? Erstellen die meisten Operationen eine neue Liste und lassen eine unveränderte Version zugänglich (dauerhaft), oder schreiben Sie Code wie folgt (kurzlebig):

list.append(x);
list.prepend(y);

Beide Optionen sind in Ordnung, aber die Implementierung sollte die Schnittstelle widerspiegeln: Eine beständige Datenstruktur profitiert von unveränderlichen Knoten, während eine kurzlebige interne Veränderlichkeit erforderlich ist, um die implizit von ihr gemachten Leistungsversprechen tatsächlich zu erfüllen. java.util.Listund andere Schnittstellen sind kurzlebig: Die Implementierung in eine unveränderliche Liste ist unangemessen und stellt in der Tat eine Gefahr für die Leistung dar. Gute Algorithmen für veränderbare Datenstrukturen unterscheiden sich häufig erheblich von guten Algorithmen für unveränderliche Datenstrukturen. Wenn Sie also eine unveränderliche Datenstruktur als veränderliche Datenstruktur auslegen (oder umgekehrt), führt dies zu schlechten Algorithmen.

Während eine persistente Liste einige Nachteile aufweist (kein effizientes Anhängen), muss dies bei der funktionalen Programmierung kein ernstes Problem sein: Viele Algorithmen können effizient formuliert werden, indem die Denkweise geändert und Funktionen höherer Ordnung wie mapoder fold(um zwei relativ primitive zu nennen) verwendet werden ) oder durch wiederholtes Voranstellen . Darüber hinaus zwingt Sie niemand, nur diese Datenstruktur zu verwenden: Wenn andere (kurzlebige oder beständige, aber anspruchsvollere) geeigneter sind, verwenden Sie sie. Ich sollte auch beachten, dass persistente Listen einige Vorteile für andere Workloads haben: Sie teilen sich ihre Endpunkte, wodurch Speicherplatz gespart werden kann.


quelle
4

Wenn Sie eine einfach verknüpfte Liste haben, arbeiten Sie mit der Vorderseite, wenn dies mehr ist als mit der Rückseite.

Funktionssprachen wie prolog und haskel bieten einfache Möglichkeiten, um das Front-Element und den Rest des Arrays zu erhalten. An die Rückseite wird eine O (n) -Operation angehängt, bei der jeder Knoten kopiert wird.

Ratschenfreak
quelle
1
Ich habe Haskell benutzt. Afaik, es umgeht auch einen Teil des Problems durch Faulheit. Ich mache Anhänge, weil ich dachte, dass dies das ist, was von der ListSchnittstelle erwartet wird (ich könnte mich dort jedoch irren). Ich denke, dass dieses Bit die Frage auch nicht wirklich beantwortet. Die gesamte Liste müsste noch kopiert werden. Es würde lediglich den Zugriff auf das letzte hinzugefügte Element beschleunigen, da kein vollständiger Durchlauf erforderlich wäre.
Carcigenicate
Das Erstellen einer Klasse gemäß einer Schnittstelle, die nicht mit der zugrunde liegenden Datenstruktur / dem zugrunde liegenden Algorithmus übereinstimmt, ist eine Aufforderung zu Schmerzen und Ineffizienzen.
Ratschenfreak
Die JavaDocs verwenden explizit das Wort "append". Sie sagen, es ist besser, das für die Implementierung zu ignorieren?
Carcigenicate
2
@Carcigenicate nein Ich sage , dass es ein Fehler ist eine einfach verkettete Liste mit unveränderlichen Knoten in die Form , um zu versuchen und zu passenjava.util.List
Ratsche Freak
1
Mit Faulheit gäbe es keine verknüpfte Liste mehr; Es gibt keine Liste, daher gibt es keine Mutation (Anhängen). Stattdessen gibt es einen Code, der auf Anfrage das nächste Element generiert. Es kann jedoch nicht überall dort verwendet werden, wo eine Liste verwendet wird. Wenn Sie eine Methode in Java schreiben, die erwartet, dass eine als Argument übergebene Liste geändert wird, muss diese Liste in erster Linie geändert werden können. Der Generator-Ansatz erfordert eine vollständige Umstrukturierung (Reorganisation) des Codes, damit dieser funktioniert - und die Liste physisch abgeschafft werden kann.
rwong
4

Wie bereits erwähnt, müssen Sie bei unveränderlichen einfach verknüpften Listen beim Ausführen von Anhängevorgängen die gesamte Liste kopieren.

Häufig können Sie die Problemumgehung zum Implementieren Ihres Algorithmus in Form von cons(Voranstellen) -Operationen verwenden und die endgültige Liste dann einmal umkehren. Die Liste muss noch einmal kopiert werden, aber der Aufwand für die Komplexität ist in der Länge der Liste linear, während durch wiederholtes Verwenden von append leicht eine quadratische Komplexität erhalten werden kann.

Differenzlisten (siehe zB hier ) sind eine interessante Alternative. Eine Differenzliste umschließt eine Liste und stellt eine Anfügungsoperation in konstanter Zeit bereit. Sie arbeiten im Grunde genommen so lange mit dem Wrapper, wie Sie ihn anhängen müssen, und konvertieren ihn anschließend wieder in eine Liste, wenn Sie fertig sind. Dies ähnelt in gewisser Weise dem, was Sie tun, wenn Sie StringBuildereinen String mit a konstruieren und am Ende das Ergebnis als String(unveränderlich!) Durch einen Aufruf erhalten toString. Ein Unterschied ist, dass a StringBuilderveränderlich ist, aber eine Differenzliste unveränderlich ist. Wenn Sie eine Differenzliste zurück in eine Liste konvertieren, müssen Sie die gesamte neue Liste erstellen, dies muss jedoch nur einmal ausgeführt werden.

Es sollte ziemlich einfach sein, eine unveränderliche DListKlasse zu implementieren , die eine ähnliche Schnittstelle wie die von Haskell bietet Data.DList.

Giorgio
quelle
4

Sie müssen dieses großartige Video von 2015 React Conf von Immutable.js 'Schöpfer Lee Byron ansehen . Es gibt Ihnen Hinweise und Strukturen, um zu verstehen, wie Sie eine effiziente unveränderliche Liste implementieren, die keinen Inhalt dupliziert. Die Grundideen sind: - Solange zwei Listen identische Knoten verwenden (gleicher Wert, gleicher nächster Knoten), wird derselbe Knoten verwendet. - Wenn die Listen unterschiedlich beginnen, wird am Knoten der Divergenz eine Struktur erstellt, die Zeiger auf den Knoten enthält nächster bestimmter Knoten jeder Liste

Dieses Bild aus einem Reaction-Tutorial ist möglicherweise deutlicher als mein gebrochenes Englisch:Bildbeschreibung hier eingeben

Feydaykyn
quelle
2

Es ist nicht ausschließlich Java, aber ich schlage vor, dass Sie diesen Artikel über eine unveränderliche, aber performante indizierte persistente Datenstruktur lesen, die in Scala geschrieben wurde:

http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala

Da es sich um eine Scala-Datenstruktur handelt, kann sie auch von Java aus verwendet werden (mit etwas mehr Ausführlichkeit). Es basiert auf einer Datenstruktur, die in Clojure verfügbar ist, und ich bin mir sicher, dass es auch eine "native" Java-Bibliothek gibt, die dies anbietet.

Auch ein Hinweis auf die Konstruktion unveränderlichen Datenstrukturen: Was Sie in der Regel wollen , ist eine Art von „Builder“, die Sie zu „mutieren“ Ihre „im Bau“ Datenstruktur ermöglicht durch Elemente , um es (in einem einzigen Thread) anhängt; Nachdem Sie das Anhängen abgeschlossen haben, rufen Sie eine Methode für das Objekt "under-construction" auf, z. B. " .build()or .result()", wodurch das Objekt "erstellt" wird, sodass Sie eine unveränderliche Datenstruktur erhalten, die Sie dann sicher freigeben können.

Sandro Gržičić
quelle
1
Es gibt eine Frage zu Java-Ports von PersistentVector unter stackoverflow.com/questions/15997996/…
James_pic
1

Ein Ansatz, der manchmal hilfreich sein kann, besteht darin, zwei Klassen von Listenobjekten zu haben - ein Weiterleitungslistenobjekt mit einer finalReferenz auf den ersten Knoten in einer weitergeleiteten Liste und eine anfänglich leere Nichtreferenz, finaldie (wenn nicht -null) identifiziert ein Reverse-List-Objekt, das die gleichen Elemente in umgekehrter Reihenfolge enthält, und ein Reverse-List-Objekt mit einer finalReferenz auf das letzte Element einer Reverse-Linked-List und einer anfänglich null nicht-finalen Referenz, die (wenn nicht -null) identifiziert ein Forward-List-Objekt, das die gleichen Elemente in entgegengesetzter Reihenfolge enthält.

Das Voranstellen eines Elements an eine Vorwärtsliste oder das Anhängen eines Elements an eine Rückwärtsliste würde lediglich das Erstellen eines neuen Knotens erfordern, der mit dem durch die finalReferenz identifizierten Knoten verknüpft ist, und das Erstellen eines neuen Listenobjekts des gleichen Typs wie das Original mit einer finalReferenz zu diesem neuen Knoten.

Das Anhängen eines Elements an eine Forward-Liste oder das Voranstellen an eine Reverse-Liste erfordert eine Liste des entgegengesetzten Typs. Wenn eine bestimmte Liste zum ersten Mal bearbeitet wird, sollte ein neues Objekt des entgegengesetzten Typs erstellt und eine Referenz gespeichert werden. Wiederholen der Aktion sollte die Liste wiederverwenden.

Beachten Sie, dass der externe Status eines Listenobjekts gleich ist, unabhängig davon, ob sein Verweis auf eine Liste entgegengesetzten Typs null ist oder eine Liste entgegengesetzter Reihenfolge identifiziert. Auch finalbei Verwendung von Multithread-Code müssen keine Variablen erstellt werden, da jedes finalListenobjekt auf eine vollständige Kopie seines Inhalts verweist.

Wenn Code in einem Thread eine umgekehrte Kopie einer Liste erstellt und zwischenspeichert und das Feld, in dem diese Kopie zwischengespeichert wird, nicht flüchtig ist, ist es möglich, dass Code in einem anderen Thread die zwischengespeicherte Liste nicht sieht, sondern den einzigen nachteiligen Effekt Dies würde bedeuten, dass der andere Thread zusätzliche Arbeit leisten müsste, um eine weitere umgekehrte Kopie der Liste zu erstellen. Da eine solche Aktion im schlimmsten Fall die Effizienz beeinträchtigen würde, die Korrektheit jedoch nicht beeinträchtigen würde und die volatileVariablen selbst Effizienzbeeinträchtigungen verursachen, ist es häufig besser, die Variable nichtflüchtig zu halten und die Möglichkeit gelegentlicher redundanter Operationen zu akzeptieren.

Superkatze
quelle