Was haltet ihr von Persistenten Datenstrukturen?

Hi,

bin noch ein wenig am Grübeln wie ich ein Konzept umsetze.

Ich habe mal eine Zeit lang mit Clojure programmiert und dort trifft man häufig auf

Das ganze finde ich recht genial und bin nun am überlegen ob ich sowas in einem aktuellen Javaprojekt einsetzen möchte.

Das Konzept lässt sich anhand von einer List sehr gut in Java veranschaulichen. (Keine Angst es kommt kein LISP Beispiel ;))

Wenn ich eine List habe und füge der Liste ein Element hinzu, so bekomme ich eine neue Liste mit dem hinzugefügten Element und zusätzlich einem Verweis auf die alte Liste, welche unverändert bleibt.

Als Beispiel wie sich das in Java anfühlen würde.

List<Integer> one2three = Arrays.asList(new Integer[]{1,2,3});

List<Integer> one2four = one2three.add(4);
//die java.util.List würde bei add true zurückgeben.


for(int i : one2three) {
  System.out.println(i);//1 2 3
//java.util.List würde verändert werden und 1,2,3,4 zurückgeben
}

for(int i : one2four) {
  System.out.println(i);//1 2 3 4
}```

Wenn man nun von der Implementierung, die dafür in Java folgen würde absieht, bei der alle Elemente aus der ersten Liste in eine zweite Liste kopiert werden müssten, was unperformant und speicherintensiv wäre und sich den Ansatz aus Clojure
Immutable List und neues Element + Verweis auf alte List zu Herzen nimmt, würdet ihr das ganze für sinnvoll halten.


Oder nutzt ihr sowas schon? und wie sind eure Erfahrungen damit.

Der Hintergrund dabei ist, dass ich damit auf einer etwas schwierigeren Datenstruktur Backtracking anwenden können möchte. 

Und bei einer Datenstruktur die Immutable ist sehe ich da so gewisse Vorteile.

 @Landei  et al. werden sowas bestimmt auch aus Scala kennen, das etwa genauso wie beschrieben funktioniert.

Aber nutzt ihr das dann auch auf anderen Datenstrukturen oder nur die bereits implementierten Collections.

“Fundierte” Aussagen kann ich dazu kaum machen, aber @Landei hatte mich, als ich mal eine Frage in diesem Dunstkreis gestellt hatte, auf http://pcollections.org/ aufmerksam gemacht. Mein unfundierter Senf: Das ist theoretisch natürlich super, aber der Gedanke, dass die Daten nicht als Block im Speicher liegen, und diese Strukturen zwangsläufig einen gewissen Verwaltungsoverhead haben müssen, bewirkt bei mir eine gewisse Skepsis bzgl. der Performance (aber dedizierte Tests dazu (oder das Websuchen nach selbigen) wären mal ganz interessant)

Die Frage ist immer, wofür man die Collections braucht, und da geht es nicht nur um mutable vs immutable, sondern auch um lazy vs strict, seriell vs parallel, lesen vs ändern und anderes. Eine einfach verkettete Liste und Banker’s Dequeue sind ja erst der Anfang. Es gibt z.B. auch Listen mit O(log(n)) Zugriff auf einen zufälligen Index (Okasakis Random Access List) und vieles mehr. Das macht eine generelle Aussage so schwierig. Aber es ist immer besser, die Wahl zu haben, und verschiedene Versionen ausprobieren zu können, denn in der Praxis (insbesondere in Gegenwart eines optimierenden JIT-Compilers) sieht es eben anders aus als auf dem Papier.

Übrigens sollte neben pcollections auch functionaljava genannt werden. Selbst meine highJ_Bibliothek bietet einige persistente immutable Datenstrukturen (von deren Praxiseinsatz ich dringend abraten würde). Im Beruf verwende ich sowas momentan nicht, aber das könnte sich mit Java 8 ändern. Allerdings bietet Java 8 selbst mit den neuen Streams etwas, das sich ähnlich “anfühlt” wie immutable Datenstrukturen. Trotzdem lassen schon die vorhandenen mutablen Collections in Java viel zu wünschen übrig, und ein integrativer Ansatz wie in Scala, der einem beide Varianten in einer gemeinsamen, kompatiblen Hierarchie bietet, liegt noch in weiter Ferne.

http://pcollections.org/ ist schonmal recht interessant.

Meine Sicht der Dinge sieht ein klein wenig anders aus. Wenn ich bedenke, dass ich aus solchen Strukturen einen Nutzen ziehen kann, in dem ich diese entsprechend verwende, dann spare ich mir Implementierungsaufwand, den ich hätte um dieses Verhalten nachzuimplementieren und den durch die Implementierung entstandenen Verwaltungsoverhead, der das ganze im Speicher verwaltet, so wie die Chance mir den ein oder anderen Bug einzuhacken.

Nur mal angenommen ich füge etwas einem Set hinzu dass in diesem schon vorhanden ist, dann verändert sich das Set überhaupt nicht.
Wenn ich darauf ein Undo anwende und das Element nun entferne, dann habe ich das Set verändert und nicht mehr den ursprünglichen Zustand.
Bei einem Element kann ich noch schauen, ob da das Element bei einem Undo entfernt werden muss.
Wenn ich allerdings zwei Sets zusammenführe, dann ist das kein Einzeiler mehr und die ganze vermaledeite Kopiererei fängt an.

Ein weiteres negativ Beispiel ist die Date und Calendar-Api. Wenn du zu einem Termin eine Woche dazuaddierst, dann verändert sich das ursprüngliche Datum, dass evtl. schon für was anderes benutzt wird.

Aber die eigentliche Fragestellung auf die ich hinausmöchte ist, ob auch jemand solche immutable-Geschichten ausserhalb von Collections anwendet.

Wenn ich etwas ohne großen Aufwand immutable machen kann, mache ich das, warum auch nicht? Die Java-API geht selbst in diese Richtung, siehe z.B. die neue Time-API (a.k.a. ThreeTen)

Die Vorteile von Immutabilität stehen ja außer Frage. Und wenn es das schon gibt (und es „gut“ implementiert ist), und man es einfach nutzen kann, umso besser. Es gibt viele Bereiche, wo das interessant ist, und gerade mit den Funktionalen Erweiterungen von Java8 wird das noch deutlicher - darauf bezog sich meine oben angesprochene Frage, und … meine Bedenken bezogen sich damals (das sollte man vielleicht erwähnen) weniger auf Listen und Sets, sondern eher auf so etwas wie eine Matrix mit 1000x1000 Elementen.

Und bei „trivialen“ Dingen wie verketteten Listen wäre so eine Persistenz ja noch recht einfach. Aber spätestens bei sowas wie Hash- oder Treebasierten Datenstrukturen bzw. Maps würde ich einen Teufel tun, und versuchen, das selbst zu implementieren - da muß man schon richtig Hirnschmalz reinstecken. Selbst bei dem vermeintlich trivialen wie einer Liste gibt es dann ja schonmal keinen O(1) Zugriff mehr, und … wenn sowas wie eine Liste schon einen Namen bekommt, weil sie O(log(n)) bietet, spricht das IMHO Bände :smiley:

String :wink:

(EDIT: Diese Frage kann unter http://forum.byte-welt.net/threads/12128-Persistente-Java-Collections?p=94740#post94740 weiter diskutiert werden)

Mal so in die Runde gefragt: Bestände Interesse, eine kleines Java-8-Projekt mit immutablen Gegenstücken zu den wichtigsten Java-Collections (List, Set, Map) aufzusetzen, dazu Tuple und Either?

Ich habe ja schon einige Implementierungen rumliegen, aber die sind halt an einigen Stellen recht eigenwillig und müssten erst einmal ausgemistet, aufeinander abgestimmt und in eine vernünftige Hierarchie gebracht werden. Was fehlt, ist also insbesondere eine verständliche API und eine gute Interoperabilität mit den mutablen Collections.

Natürlich kann man sich auf den Standpunkt stellen, dass pcollections oder functionaljava gut genug sind. Mir persönlich sind pcollections etwas beschränkt, und functionaljava zu weitläufig. Ich würde mich auf täglich benötigte Collections mit einer einfache, praktischen API beschränken, die aber genug “power” haben um Spaß zu machen. Dabei sollten Java 8 Features gebührend ausgenutzt werden.

Was meint ihr?

Kein Mensch würde das so machen… Wie du im richtig anmerkst, verwendet man dazu Baumstrukturen in dem nur die neuen Elemente tatsächlich abgespeichert werden. Einen kurzen Ausflug wie das implementiert werden kann wird in Functional Programming in Java gemacht.

Immutable Datenstrukturen verwende ich manchmal für die Modellklassen. Hat den Vorteil, dass so nur Objekte verwendet werden die den alten konsistenten Zustand oder den neuen Konsistenten Zustand aufweisen.

Doug Lea schon.

Auszug aus [japi]CopyOnWriteArrayList[/japi]:

    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}```

Dort wird das zwar gemacht um Nebenläufigkeit zu ermöglichen, aber vom Prinzip her kann es in einigen Anwendungen schon sinnig sein.

… naja

Das macht nur Sinn wenn es sich bei den Elementen um mutable Elementen handelt.

Elemente = Objekte in der Liste?
was hätten deren Eigenschaften/ Veränderungen mit der Container-Datenstruktur zu tun?
außer bei so Dingen wie hashCode, equals, contains


und nebenbei, um zwei halbe Punkte zu einem Posting zu verbinden:
wie kommt es zum Titel-Begriff Persistent (deutsch) in beiden Themen?

in englisch **persistent **mag korrekt sein, wenn auch dort mit unglücklicher Doppelbedeutung (*),
aber Persistenz im Deutschen ist doch anscheinend nur auf die DB-Frage beschränkt?

**immutable **gibts im Deutschen nicht so recht als Fachbegriff übersetzt, **unveränderlich **vielleicht,
aber ist auf jeden Fall auch verbreitet, ein perfekter eindeutiger Begriff,
hier im Thread auch diverse Male verwendet, persistent seltener

nicht erste Wahl für Titel? :wink:


(*)
bemerkenswert im Wiki-Artikel:

(A persistent data structure is not a data structure committed to persistent storage, such as a disk; this is a different and unrelated sense of the word „persistent.“)

[QUOTE=SlaterB]
und nebenbei, um zwei halbe Punkte zu einem Posting zu verbinden:
wie kommt es zum Titel-Begriff Persistent (deutsch) in beiden Themen?

in englisch **persistent **mag korrekt sein, wenn auch dort mit unglücklicher Doppelbedeutung (*),
aber Persistenz im Deutschen ist doch anscheinend nur auf die DB-Frage beschränkt?[/QUOTE]

Die “unglückliche Doppelbedeutung” gibt es genau so auch im Deutschen:

Persistente Datenstrukturen

In den meisten Fällen bedeutet “Persistieren” das Speichern von Daten auf einen nichtflüchtigen Datenträger, meist eine Festplatte. Eine “persistente Datenstruktur” hingegen hat mit Persistenz im Sinn des Erhalts der Werte auch nach einem Stromausfall nichts zu tun, sondern bezeichnet das beobachtete Verhalten, dass nach einer Manipulation der Datenstruktur die vorherige Version ebenfalls noch vorhanden ist (siehe auch den Blog-Eintrag “Grokking Functional Data Structures” von Debasish Ghosh). In dem Sinn sind Clojures persistente Datenstrukturen nichtflüchtig. Die von Sprachen wie Java oder C bekannten Datenstrukturen hingegen, die eine direkte Manipulation erlauben, sind flüchtig: Nach einer Manipulation ist die vorherige Version nicht mehr erreichbar.

Immutable Datenstrukturen sind natürlich immer persistent, persistente Datenstrukturen müssen aber nicht immutable sein: Es gibt auch Implementierungen, die eine Veränderung erlauben, ohne alte Versionen wegzuwerfen (etwa um ein Undo zu ermöglichen).

Wenn ich immutable Objekte in der Liste habe, können Threads wie sie lustig sind darauf zugreifen. Zu jedem Zeitpunkt handelt es sich um einen Zustand der zumindest zu einem anderen Zeitpunkt konsistent war. Das gilt nicht, für Code-Blöcke wie folgenden:


  arr[0].Wert1 = 'asdf';
  arr[0].Wert2 = 'asdf2';

Da gibt’s dann auch Zustände in denen Wert1 gesetzt ist und Wert2 noch nicht. Das lässt sich verhindern wenn man das ganze Objekt austauschen muss um Felder zu ändern. Geht natürlich auch mit Locks, die sind aber teuer.