wake-up-neo.com

HashMap-Alternativen zur speichereffizienten Datenspeicherung

Ich habe derzeit ein Tabellenkalkulationsprogramm, das seine Daten in einer ArrayList von HashMaps speichert. Sie werden zweifellos schockiert sein, wenn ich Ihnen sage, dass dies nicht ideal ist. Der Overhead scheint 5x mehr Arbeitsspeicher als die Daten selbst zu benötigen.

Diese Frage fragt nach Bibliotheken für effiziente Sammlungen und die Antwort war Google Collections. Mein Follow-up ist " welcher Teil? ". Ich habe die Dokumentation durchgelesen, fühle mich aber nicht so, als würde sie ein sehr gutes Gefühl dafür vermitteln, welche Klassen dafür gut geeignet sind. (Ich bin auch offen für andere Bibliotheken oder Vorschläge).

Ich suche also nach etwas, mit dem ich dichte Daten vom Spreadsheet-Typ mit minimalem Speicheraufwand speichern kann.

  • Meine Spalten werden derzeit von Field-Objekten referenziert, Zeilen nach ihren Indizes und Werte sind Objekte, fast immer Strings
  • Einige Spalten enthalten viele wiederholte Werte
  • zu den primären Vorgängen gehören das Aktualisieren oder Entfernen von Datensätzen basierend auf den Werten bestimmter Felder sowie das Hinzufügen/Entfernen/Kombinieren von Spalten

Ich kenne Optionen wie H2 und Derby, aber in diesem Fall suche ich keine eingebettete Datenbank.

EDIT: Wenn Sie Bibliotheken vorschlagen, wäre ich auch dankbar, wenn Sie mich auf eine bestimmte Klasse oder zwei davon verweisen könnten, die sich hier bewerben würden. Während die Dokumentation von Sun normalerweise Informationen darüber enthält, welche Operationen O (1), O (N) usw. sind, sehe ich davon nicht viel in Bibliotheken von Drittanbietern und auch keine Beschreibung, welche Klassen für was am besten geeignet sind .

26
Brad Mace

Ich gehe also davon aus, dass Sie eine Karte von Map<ColumnName,Column> haben, wobei die Spalte tatsächlich etwas wie ArrayList<Object> ist. 

Ein paar Möglichkeiten - 

  • Sind Sie absolut sicher, dass Speicher ein Problem ist? Wenn Sie sich im Allgemeinen nur Sorgen um die Größe machen, lohnt es sich zu bestätigen, dass dies in einem laufenden Programm wirklich ein Problem sein wird. Es dauert eine Menge Zeilen und Karten, um eine JVM zu füllen. 

  • Sie können Ihren Datensatz mit verschiedenen Kartentypen in den Sammlungen testen. Abhängig von Ihren Daten können Sie Karten auch mit voreingestellten Kombinationen aus Größe und Lastfaktor initialisieren, die helfen können. Ich habe in der Vergangenheit damit herumgespielt. Wenn Sie Glück haben, können Sie den Speicher um 30% reduzieren.

  • Wie wäre es mit dem Speichern Ihrer Daten in einer einzigen matrixartigen Datenstruktur (einer vorhandenen Bibliotheksimplementierung oder einem Wrapper um eine Listenliste), mit einer einzigen Zuordnung, die Spaltenschlüssel Matrixspalten zuordnet? 

4
Steve B.

Einige Spalten enthalten viele Wiederholte Werte

schlägt mir sofort die mögliche Verwendung des FlyWeight-Musters vor, unabhängig von der Lösung, die Sie für Ihre Kollektionen wählen.

11
Brian Agnew

Trove Collections sollte besonders auf den besetzten Speicherplatz achten (ich denke, sie haben auch maßgeschneiderte Datenstrukturen, wenn Sie sich an primitive Typen halten). Schauen Sie hier .

Ansonsten können Sie mit Apache-Kollektionen .. versuchen, Ihre Benchmarks zu machen!

In jedem Fall, wenn Sie viele Verweise auf dieselben Elemente haben, versuchen Sie, ein geeignetes Muster (wie flyweight ) zu entwerfen.

5
Jack

Wenn Sie davon ausgehen, dass alle Zeilen die meisten der gleichen Spalten haben, können Sie einfach ein Array für jede Zeile und Map <ColumnKey, Integer> verwenden, um nachzuschlagen, welche Spalten auf welche Zelle verweisen. Auf diese Weise haben Sie nur 4-8 Byte Overhead pro Zelle.

Wenn Strings häufig wiederholt werden, können Sie einen String-Pool verwenden, um die Duplizierung von Strings zu reduzieren. Objektpools für andere unveränderliche Typen können hilfreich sein, um den Speicherbedarf zu reduzieren.

EDIT: Sie können Ihre Daten entweder zeilen- oder spaltenbasiert strukturieren. Wenn die Zeilen auf Zeilen basieren (ein Array von Zellen pro Zeile), müssen Sie nur diese Zeile entfernen oder entfernen. Wenn die Spalten basieren, können Sie ein Array pro Spalte erstellen. Dies kann die Handhabung primitiver Typen wesentlich effizienter machen. Das heißt, Sie können eine Spalte haben, die int [] ist, und eine andere, die double [] ist. Häufig ist es üblich, dass eine gesamte Spalte denselben Datentyp hat, anstatt denselben Datentyp für eine ganze Zeile zu haben.

Wenn Sie die Daten jedoch für eine Änderung der Zeilen- oder Spaltenoptimierung optimieren, wird beim Hinzufügen/Entfernen des anderen Typs der gesamte Datensatz neu erstellt.

(Ich habe zeilenbasierte Daten und fügt am Ende columnns hinzu. Angenommen, eine Zeile ist nicht lang genug, die Spalte hat einen Standardwert. Dies vermeidet eine Neuerstellung beim Hinzufügen einer Spalte. Anstatt eine Spalte zu entfernen, habe ich ein Mittel, um es zu ignorieren)

3
Peter Lawrey

Guava enthält eine Table - Schnittstelle und eine Hash-basierte Implementierung. Scheint wie eine natürliche Anpassung an Ihr Problem. Beachten Sie, dass dies immer noch als Beta markiert ist.

2
whiskeysierra

Chronicle Map kann einen Eintrag von weniger als 20 Bytes pro Eintrag haben (siehe einen Test , der dies beweist). Zum Vergleich variiert der Overhead von Java.util.HashMap zwischen 37-42 Bytes mit -XX:+UseCompressedOops bis 58-69 Bytes ohne komprimierte Oops ( reference ).

Darüber hinaus speichert Chronicle Map Schlüssel und Werte außerhalb des Heapspeichers, sodass keine Objekt-Header gespeichert werden, die nicht als HashMap-Overhead oben aufgeführt werden. Chronicle Map integriert mit Chronicle-Values ​​ , eine Bibliothek zur Erzeugung von Flyweight-Implementierungen von Interfaces. Das Muster wird von Brian Agnew in einer anderen Antwort vorgeschlagen.

1
leventov

Ich habe mit dem SparseObjectMatrix2D aus dem Colt - Projekt experimentiert. Meine Daten sind ziemlich dicht, aber ihre Matrix-Klassen bieten keine Möglichkeit, sie zu vergrößern. Daher habe ich eine spärliche Matrix auf die maximale Größe gesetzt.

Es scheint ungefähr 10% weniger Speicher zu verbrauchen und lädt für dieselben Daten etwa 15% schneller und bietet außerdem einige clevere Manipulationsmethoden. Immer noch an anderen Optionen interessiert.

1
Brad Mace

speichert seine Daten in einer ArrayList von HashMaps
Nun, dieser Teil erscheint mir furchtbar ineffizient. Leere HashMap reserviert bereits 16 * size of a pointer Bytes (16 steht für die Standardkapazität) und einige Variablen für Hash-Objekte (14 + psize). Wenn Sie viele dünn besetzte Reihen haben, könnte dies ein großes Problem sein.

Eine Option wäre die Verwendung eines einzelnen großen Hash mit zusammengesetztem Schlüssel (Kombination von Zeile und Spalte). Das macht Operationen an ganzen Zeilen jedoch nicht sehr effektiv. 

Da Sie das Hinzufügen von Zellen nicht erwähnen, können Sie Hashes nur mit dem erforderlichen internen Speicher erstellen (Parameter initialCapacity).

Ich weiß nicht viel über Google-Sammlungen, daher kann ich nicht helfen. Wenn Sie eine nützliche Optimierung finden, schreiben Sie bitte hier! Es wäre interessant zu wissen.

1
Nikita Rybak

Aus Ihrer Beschreibung scheint es, dass Sie anstelle einer ArrayList von HashMaps lieber eine (Linked) HashMap von ArrayList möchten (jede ArrayList wäre eine Spalte).

Ich würde eine Doppelkarte von Feldname zu Spaltennummer hinzufügen und einige clevere Getter/Setter, die niemals IndexOutOfBoundsException werfen.

Sie können auch einen ArrayList<ArrayList<Object>> (im Grunde eine gezackte dinamisch wachsende Matrix) verwenden und die Zuordnung zu Feldnamen (Spaltennamen) außerhalb behalten.

Einige Spalten enthalten viele Wiederholte Werte

Ich bezweifle, dass dies von Bedeutung ist, insbesondere wenn es sich um Strings handelt (sie sind verinnerlicht) und Ihre Sammlung würde Verweise darauf enthalten.

0
leonbloy

Warum versuchen Sie nicht, die Cache-Implementierung wie EHCache . Zu verwenden? Dies erwies sich als sehr effektiv für mich, wenn ich dieselbe Situation habe.
Sie können Ihre Sammlung einfach in der EHcache-Implementierung speichern. Es gibt Konfigurationen wie:

Maximum bytes to be used from Local heap.

Sobald die von der Anwendung verwendeten Bytes die im Cache konfigurierten Bytes überlaufen, übernimmt die Cache-Implementierung das Schreiben der Daten auf die Festplatte. Außerdem können Sie die Zeitspanne konfigurieren, nach der die Objekte mit dem Least Recent Used-Algorithmus auf die Festplatte geschrieben werden. Mit diesen Cache-Implementierungen können Sie sicher sein, dass keine Speicherfehler mehr auftreten. Erhöht die IO -Operationen Ihrer Anwendung nur geringfügig.
Dies ist nur eine Vogelperspektive der Konfiguration. Es gibt viele Konfigurationen, um Ihre Anforderungen zu optimieren.

0
NiranjanBhat