Immutable Map-Implementierung für große Karten

Wenn ich eine unveränderliche Karte, die ich erwarten würde (über einen sehr kurzen Zeitraum - wie ein paar Sekunden) wird das Hinzufügen/Entfernen Hunderttausender von Elementen aus, wird der Standard HashMap eine schlechte Idee? Nehmen wir an, ich möchte 1 GB Daten über die Karte in < 10 Sekunden so weitergeben, dass die maximale Größe der Map zu jedem Zeitpunkt nur 256 MB beträgt.Immutable Map-Implementierung für große Karten

Ich habe den Eindruck, dass die Karte eine Art "Geschichte" hält, aber ich werde immer Zugriff auf die zuletzt aktualisierte Tabelle (dh ich übergebe die Karte nicht), weil es eine private Mitgliedsvariable von ist Actor, die nur innerhalb von Reaktionen aktualisiert/zugegriffen wird.

Grundsätzlich vermute ich, dass diese Datenstruktur (teilweise) for issues I am seeing around JVMs going out of memory Fehler beim Einlesen großer Datenmengen in kurzer Zeit sein kann.

Wäre ich besser mit einer anderen Kartenimplementierung und wenn ja, was ist das?

Quelle

2010-02-19 oxbow_lakes

Autsch. Warum müssen Sie eine unveränderliche Karte verwenden? Schlechter Müllsammler! Unveränderliche Karten erfordern normalerweise (log n) neue Objekte pro Operation zusätzlich zur (log n) Zeit, oder sie wickeln nur veränderliche Hash-Karten und Ebenenänderungssätze ganz oben ab (was die Dinge verlangsamt und die Anzahl der Objektschöpfungen erhöhen kann).

Unveränderlichkeit ist großartig, aber das scheint mir nicht die Zeit, es zu verwenden. Wenn ich du wäre, würde ich bei scala.collection.mutable.HashMap bleiben. Wenn Sie gleichzeitig Zugriff benötigen, packen Sie stattdessen das Java-Dienstprogramm util.concurrent ein.

Sie könnten auch die Größe der jungen Generation in der JVM erhöhen: -Xmn1G oder mehr (vorausgesetzt, Sie laufen mit -Xmx3G). Verwenden Sie auch den Garbage Collector mit Durchsatz (parallel).

Quelle

2010-02-19 17:06:41

Ja - ich habe es geändert, um die veränderbare Karte zu verwenden, aber ich dachte, dass der ganze Punkt von FP war, dass Unveränderlichkeit groß war! Diese App sollte leicht in weniger als 256 MB Speicher von einer "Wie viele Daten benötigt es wirklich zu einem bestimmten Zeitpunkt" Perspektive laufen. –

Wie groß die Unveränderlichkeit ist, hängt von der Anwendung ab. Wenn Sie eine Anwendung mit sagen wir Bäumen von Nachrichten-Threads ausführen, die an eine Gruppe von Clients gesendet werden, ist Unveränderlichkeit ein Glücksfall - Sie senden nur den aktuellen Baum und müssen sich keine Sorgen darüber machen, dass sich die Datenstruktur selbst ändert unter dir. (Sie müssen immer noch Fälle auffangen, in denen der Client einen Kommentar zu einem Thread hinzufügt, der gelöscht wird, wenn er antwortet.) Für das Hochdurchsatz-Arbeiten in privaten Datenstrukturen, die sehr schnell umkehren, bietet die Unveränderlichkeit nur wenige Vorteile verlangt viel Aufwand. –

Ja, das ist was ich herausgefunden habe! Wie geht es Haskell oder Clojure in diesen Situationen? Üben sie nicht * Unveränderlichkeit? –

Das wäre schrecklich. Sie sagen, Sie wollen immer auf die zuletzt aktualisierte Tabelle zugreifen, dh Sie benötigen nur eine ephemere Datenstruktur, es gibt keine Notwendigkeit, die Kosten für eine persistente Datenstruktur zu bezahlen - es ist wie Handelszeit und Speicher vollständig zu gewinnen diskutierbare "Stilpunkte". Sie sind nicht Bauen Sie Ihr Karma mit blind bleibenden Strukturen, wenn sie nicht gefordert sind.

Auch eine Hashtable ist eine besonders schwierige Struktur, die hartnäckig zu machen ist. Mit anderen Worten, "sehr, sehr langsam" (im Grunde ist es verwendbar, wenn viel mehr Schreibvorgänge gelesen werden - und Sie scheinen über viele Schreibvorgänge zu sprechen).

Übrigens, ein ConcurrentHashMap würde in diesem Design keinen Sinn ergeben, vorausgesetzt, dass die Karte von einem einzigen Akteur zugegriffen wird (das ist, was ich von der Beschreibung verstehe).

Quelle

2010-02-19 17:29:14

Sie haben Recht - ich habe keine Anforderung für Unveränderlichkeit oder Nebenläufigkeit. Meine Karte ist ein Cache, der für einen einzelnen Akteur privat ist. –

Ich nehme an, da Sie Schauspieler benutzen, möchten Sie Vorteile aus Nebenläufigkeitschancen ziehen. Diese Karte/Akteur, die jetzt wie ein potenzieller Engpass klingt, könnte eine gute Gelegenheit sein (irrelevant von Schauspielern), dh Sie könnten davon profitieren, die Karte zu einer gemeinsamen ConcurrentHashMap zu machen (nicht im Besitz eines einzelnen Akteurs) und Autoren gleichzeitig fortfahren zu lassen , wenn möglich/zumutbar. –

Die Daten sind die Karte muss nicht zwischen den Akteuren geteilt werden - es gibt etwa 30 actor-Instanzen, jede mit ihren eigenen Karten (von Daten nur für sie relevant) –

Die so genannte (*) unveränderliche Karte von Scala ist über die grundlegende Verwendung hinaus bis zu Scala 2.7 unterbrochen. Vertrauen Sie mir nicht, schauen Sie einfach die Anzahl der offenen Tickets nach. Und die Lösung ist nur "es wird durch etwas anderes auf Scala 2.8 ersetzt" (was es getan hat).

Also, wenn Sie eine unveränderliche Karte für Scala 2.7.x wollen, würde ich empfehlen, es in etwas anderem als Scala zu suchen. Oder benutze stattdessen TreeHashMap.

(*) Scalas unveränderliche Map ist nicht wirklich unveränderbar. Es ist intern eine veränderbare Datenstruktur, die viel Synchronisation erfordert.

Quelle

2010-02-19 17:39:00

Wo finde ich eine Alternative? Ist 'TreeMap' OK? Ich kann kaum einen in Java finden –

@oxbow Ich denke, dass Leute "HashTreeMap" als eine Alternative tatsächlich verwendeten, jetzt, wo Sie es erwähnen. –

Scalas unveränderliche Karte scheint in letzter Zeit repariert worden zu sein. Der Code ist jetzt ein Trie, das alte Protokollierungsschema scheint weg zu sein. –

Immutable Map-Implementierung für große Karten

Antwort

Verwandte Themen