Ich baue gerade einen LRU-Cache, in dem ich die letzten N eingefügten Elemente speichern muss. Elemente werden häufig eingefügt (d. H. Viele Schreiboperationen), und Leseoperationen geben typischerweise eine große Anzahl von Ereignissen immer strikt in der Reihenfolge zurück , obwohl sie an einem beliebigen Punkt im Cache beginnen. Angenommen, der Cache enthält Ereignisse:
%Vor% Eine legale Leseoperation wäre die Rückgabe eines Iterators über die Ereignisse [2, 3, 4] .
Da Lesevorgänge möglicherweise langlebig sind, möchte ich eine Datenstruktur verwenden, in der ich sicher über eine logische Kopie der Sequenz für jeden Leseversuch iterieren kann, wodurch ein Lesevorgang im Cache verhindert wird von irgendwelchen nachfolgenden Schreibvorgängen. Wenn Sie jedoch ein Java-Java ArrayList oder LinkedList verwenden, entsteht beim Erstellen einer vollständigen Kopie ein großer Aufwand.
Meine Frage: Gibt es Java-Bibliotheken von Drittanbietern, die unveränderliche Datenstrukturen ähnlich wie Scala bereitstellen, wobei Versuche, die Datenstruktur zu ändern, eine neue unveränderliche -Kopie zurückgeben (die tatsächlich auf dem Original basiert) Datenstruktur und damit der Kopiervorgang ist sehr schnell)? Offensichtlich konnte die Datenstruktur nicht mit der API für Java-Sammlungen übereinstimmen, da Operationen wie add(T) die neue Sammlung zurückgeben müssten (anstatt void ).
(Bitte keine Kommentare / Antworten, die dies als Fall einer vorzeitigen Optimierung bezeichnen.)
Vielen Dank im Voraus.
Hinweis
Guavas ImmutableList erreicht fast das, was ich brauche: Sie können copyOf aufrufen, wobei die Kopie normalerweise auf das Original verweist (wobei eine tatsächliche Kopie vermieden wird). Leider können Sie nicht in die andere Richtung gehen und ein Element zur Liste hinzufügen und erhalten eine Kopie, die das neue Element enthält.
Functional Java kommt in Form einer Bibliothek (keine andere Sprache) und bietet unveränderliche Sammlungen. Nicht sicher, ob es Ihren Bedürfnissen entspricht, aber einen Versuch wert.
Haben Sie sich die CopyOnWriteArrayList angesehen? Jede Mutation in der Liste kopiert alle Inhalte in ein neues Backing-Array, wobei das aktuelle Array, auf dem Sie uninterpretiert werden, unverändert bleibt.
Es sieht so aus, als ob Sie hier eine einfach verknüpfte Liste implementieren möchten, die dann von verschiedenen Wrapper-Objekten gemeinsam genutzt werden kann. Möchten Sie jemals Elemente entfernen oder nur neue hinzufügen?
Wenn nur hinzugefügt und nicht entfernt wird, nehme ich an, dass eine einfachere Variante von CopyOnWriteArrayList, die nur dann die Kopie erstellt, wenn das alte Array voll ist, ausreichen könnte. Die Methoden sublist() würden dann einfach ein neues Wrapper-Objekt erstellen.
Wenn dies von mehreren Threads geändert wird, sollten Sie die add Methode synchronisiert und die len Variable volatile , denke ich. (Ich habe nicht komplett überprüft, ob es dann threadsicher ist.)
Google Guava kann Ihre Anforderungen erfüllen.
Wenn Sie den Cache aktualisieren möchten, verwenden Sie Guavas Builder-Muster , um einen neuen Cache aus dem alten zu erstellen, und löschen Sie dann den alten Cache.
Um den Cache zu aktualisieren, erstellen Sie eine ImmutableList.Builder() und initialisieren Sie es mit Ihrer vorhandenen ImmutableList . Ändern Sie die Liste über die Builder-Benutzeroberfläche. Rufen Sie dann .build() auf, um eine neue ImmutableList zu erhalten, und löschen Sie den alten Cache. Der neue Cache wird alle alten Objekte wiederverwenden. Dies ist eine sehr einfache Operation.
Wenn jemand eine unveränderbare Kopie des Caches (oder eines seiner Elemente) haben möchte, geben Sie copyOf () zurück und sie erhalten Zugriff auf einen unveränderlichen Snapshot.
Achtung, wenn Sie mit Threads arbeiten, vergewissern Sie sich, dass Sie die Liste in ein Objekt einfügen und synchronisieren Sie es mit get () & amp; insert () - Methoden.
Weitere Informationen finden Sie unter auf der Guava-Website .
JDK 9 hat neue of() Methoden Factories. Z.B. Sie können ein unveränderliches Set haben als
Sie können das gleiche mit einer Liste machen, z. B.
%Vor% und ein Map :
Bietet unveränderbare Sammlungen über Kopien der persistenten Clojure-Sammlungsklassen. Es ist vielleicht nicht genau das, wonach Sie suchen, denn es geht darum, reine funktionale Semantik auf (Teilmengen von) Java-Programmen durchzusetzen.
Auf der anderen Seite hat es Unveränderlichkeitsgarantien für beide Elemente und Sammlungen. Wenn Sie ein Element aus einer Sammlung hinzufügen / entfernen, erhalten Sie eine neue Sammlung zurück und das Original bleibt unverändert.
Tags und Links java caching concurrency immutability