Definition
|
|
destruktiv
|
Zur Konstruktion neuer Listen werden in vorhandenen Listen
einzelne Knoten verändert.
|
|
Es wird mit Zuweisungen an Komponenten einzelner Knoten gearbeitet
|
|---|
|
...
next = next.f(...);
return this;
...
|
|---|
|
Speicherplatz-Effizienz
|
|
Seiteneffekte
|
persistent
|
Zur Konstruktion neuer Listen werden NIE in vorhandenen Listen
einzelne Knoten verändert, sondern IMMER nur gelesen
und daraus neue Knoten
mit den passenden Elementen erzeugt.
|
|
Es wird NIE mit Zuweisungen an Komponenten einzelner Knoten gearbeitet
|
|---|
|
...
return next.f(...).cons(info);
...
|
|---|
|
Speicherplatz-Effizienz
|
|
keine Seiteneffekte
|
| |
Vereinheitlichung |
Die Codestücke, in denen mit Zuweisungen (destruktiv)
oder mit Erzeugung neuer Objekte (persistent) gearbeitet wird, können
isoliert werden.
|
|
Beide Varianten können aus einer Codebasis abgeleitet werden
|
Lösung |
Setter-Methoden
|
Beispiel |
|
destruktiv |
LinkedList setNext(LinkedList l) {
next = l;
return
this;
}
|
persistent |
LinkedList setNext(LinkedList l) {
return
new Node(this.info, l);
}
|
kürzer |
LinkedList setNext(LinkedList l) {
return
l.cons(info);
}
|
Argumente
|
destruktiv
|
Listen als Argumente werden verbraucht.
|
|
Diese Listen dürfen nicht weiter verwendet werden.
|
|---|
Beispiel |
|
falsch |
...
l2 = l1.append(x);
...
l3 = l1.append(y);
...
|
|
Listen müssen geklont werden
|
|---|
richtig |
...
l2 = l1.copy().append(x);
...
l3 = l1.append(y);
...
|
|
Sehr fehleranfällig
|
|
Kann auch zu Speicher- und Laufzeit-Ineffizienzen führen
|
persistent
|
Listen als Argumente werden nur gelesen und behalten somit ihre Werte.
|
|
Sie dürfen beliebig weiterverwendet werden.
|
|---|
richtig |
...
l2 = l1.append(x);
...
l3 = l1.append(y);
...
|
|
keinerlei Fehlerquelle
|
| |
Mehrfachverwendung
|
destruktiv
|
Listen dürfen auch in einer Operation nie mehrfach verwendet werden.
|
Beispiel |
|
falsch |
...
l2 = l1.concat(l1);
...
|
?
|
Welches Ergebnis liefert l2.length()?
|
richtig |
...
l2 = l1.copy().concat(l1);
...
|
|
sehr fehleranfällig
|
persistent
|
Listen dürfen beliebig häufig verwendet werden.
|
richtig |
...
l2 = l1.concat(l1.concat(l1));
...
|
|
keinerlei Fehlerquelle
|
| |
Sharing |
Gemeinsame Nutzung von Teilstrukturen
|
destruktiv
|
nicht möglich
|
falsch |
...
l2 = l1.cons(x);
l1 = l1.append(y);
...
|
richtig |
...
l2 = l1.copy().cons(x);
l1 = l1.append(y);
...
|
|
Speicherplatz-Effizienz
|
persistent
|
Listen dürfen gemeinsame Teile besitzen
|
|
...
l2 = l1.cons(x);
l1 = l1.append(y);
...
|
|---|
|
keinerlei Fehlerquelle, das Verdoppeln geschieht automatisch
|
| |
Speicherverwaltung |
|
destruktiv |
händisch: Durch Freigabe aller Knoten
|
|
(relativ) einfach
|
persistent |
händisch (in C): Zum Beispiel durch Referenz-Zähler
|
|
schwierig, aufwändig
|
|
Bei Sprachen mit automatischer Speicherverwaltung
(Java, Javascript, Python, Ruby, Scala, Haskell, ...) entfällt dieses Problem
|
| |
Korrektheit |
|
destruktiv |
|
|
Sehr fehleranfällig durch viele verschiedene Zugriffspfade
auf die gleichen Knoten und durch Zuweisungen an Komponenten der Knoten
|
persistent |
|
|
Einfach: Es gibt keinen Unterschied zwischen einfachen
Werten und Listen.
|
| |
|
Der hier für Listen gemachte Vergleich ist allgemeingültig für alle dynamischen Datenstrukturen,
z.B. für Suchbäume, Warteschlangen, Hash-Tabellen, ...
|
?
|
Strings sind Listen von Zeichen.
Welche Implementierungsstrategie für Strings ist in Java gewählt worden?
|
Algorithmen & Datenstrukturen mit Java: Persistente und destruktive Datenstrukturen
