Alternative di HashMap per la memorizzazione dei dati a efficienza di memoria

Question

Attualmente ho un programma di tipo di foglio di calcolo che conserva i suoi dati in un ArrayList di HashMaps. Senza dubbio sarai scioccato quando ti dico che questo non si è dimostrato ideale. L'overhead sembra utilizzare 5 volte più memoria dei dati stessi.

This question chiede informazioni sulle raccolte di raccolte efficienti e la risposta era utilizzare Google Collections. Il mio follow-up è "quale parte?". Ho letto la documentazione, ma non mi sembra che dia un buon senso di quali classi sono adatte a questo. (Sono aperto anche ad altre librerie o suggerimenti).

Quindi sto cercando qualcosa che mi consenta di archiviare dati di tipo spreadsheet densi con un sovraccarico di memoria minimo.

• mie colonne sono attualmente riferimento da oggetti Field, righe dai loro indici e valori sono oggetti, quasi sempre stringhe
• Alcune colonne avranno un sacco di valori ripetuti
• operazioni principali sono per aggiornare o rimuovere record basati su valori di determinati campi e aggiunta/rimozione/combinazione di colonne

Sono a conoscenza di opzioni come H2 e Derby ma in questo caso non sto cercando di utilizzare un database incorporato.

EDIT: Se stai suggerendo le librerie, apprezzerei anche se potresti indicarmi una particolare classe o due in esse che si applicherebbero qui. Considerando che la documentazione di Sun di solito include informazioni su quali operazioni sono O (1), che sono O (N), ecc., Non sto vedendo molto di ciò nelle librerie di terze parti, e in realtà nessuna descrizione di quali classi sono più adatte a cosa .

Answer 1

Quindi presumo che tu abbia una mappa di Map<ColumnName,Column>, in cui la colonna è in realtà qualcosa come ArrayList<Object>.

alcune possibilità -

• Sei completamente sicuri che la memoria è un problema? Se sei solo generalmente preoccupato per le dimensioni, vale la pena di confermare che questo sarà davvero un problema in un programma in esecuzione. Ci vuole un sacco di file e mappe per riempire una JVM.

• È possibile testare il set di dati con diversi tipi di mappe nelle raccolte. A seconda dei dati, è anche possibile inizializzare le mappe con combinazioni di dimensioni/fattori di carico preimpostate che potrebbero essere utili. In passato mi sono scontrato con questo, potresti ottenere una riduzione del 30% della memoria se sei fortunato.

• Che dire di memorizzare i dati in una struttura dati a matrice singola (un'implementazione di libreria esistente o qualcosa come un wrapper attorno a un elenco di elenchi), con una singola mappa che associa le chiavi di colonna alle colonne di matrice?

Answer 2

Alcune colonne avranno un sacco di valori ripetuti

suggerisce immediatamente a me il possibile utilizzo del FlyWeight pattern, a prescindere dalla soluzione scelta per le vostre collezioni.

Answer 3

collezioni Trove dovrebbero avere una particolare attenzione per lo spazio occupato (penso che anche hanno adattato strutture di dati se vi limitate a tipi primitivi) .. dare un'occhiata here.

Altrimenti puoi provare con Apache collections .. basta fare i benchmarks!

In anycase, se hai molti riferimenti intorno al stessi elementi tentare di disegnare qualche modello adatto (come flyweight)

Answer 4

mantiene i suoi dati in un ArrayList di HashMaps
Bene, questa parte sembra terribilmente inefficiente per me. Empty HashMap assegnerà già 16 * size of a pointer byte (16 sta per capacità iniziale predefinita), più alcune variabili per l'oggetto hash (14 + psize). Se hai un sacco di file scarsamente riempite, questo potrebbe essere un grosso problema.

Un'opzione consisterebbe nell'utilizzare un singolo hash grande con chiave composita (combinazione di riga e colonna). Sebbene ciò non renda molto efficaci le operazioni su intere file.

Inoltre, poiché non si menziona l'operazione di aggiunta di celle, è possibile creare hash con solo memoria interna necessaria (parametro initialCapacity).

Non so molto sulle raccolte di Google, quindi non posso aiutarvi. Inoltre, se trovi qualche ottimizzazione utile, ti preghiamo di postare qui! Sarebbe interessante sapere.

Answer 5

Dalla tua descrizione, sembra che invece di un ArrayList di HashMaps voi piuttosto desidera un (Collegato) HashMap di ArrayList(ogni ArrayList sarebbe una colonna).

Aggiungerei una doppia mappa dal nome del campo al numero di colonna e alcuni getter/setter intelligenti che non generano mai IndexOutOfBoundsException.

È inoltre possibile utilizzare uno ArrayList<ArrayList<Object>> (fondamentalmente una matrice frastagliata dinamicamente crescente) e mantenere la mappatura al campo (colonna) nomi esterni.

Alcune colonne si hanno un sacco di valori ripetuti

Dubito che questo le cose, specialmente se sono stringhe, (sono interiorizzati) e la vostra collezione sarebbe memorizzare i riferimenti a loro.

Answer 6

Guava include un'interfaccia Table e un'implementazione basata su hash. Sembra un adattamento naturale al tuo problema. Si noti che questo è ancora contrassegnato come beta.

Answer 7

Supponendo che tutte le tue righe abbiano la maggior parte delle stesse colonne, puoi semplicemente utilizzare una matrice per ogni riga e una Mappa < ColumnKey, Integer> per cercare quali colonne si riferiscono a quale cella. In questo modo hai solo 4-8 byte di overhead per cella.

Se le stringhe vengono ripetute spesso, è possibile utilizzare un pool di stringhe per ridurre la duplicazione delle stringhe. I pool di oggetti per altri tipi immutabili possono essere utili per ridurre la memoria consumata.

MODIFICA: È possibile strutturare i dati come basati su righe o su colonne.Se le sue righe basate (una serie di celle per riga) aggiungendo/rimuovendo la riga è solo una questione di rimuovere questa riga. Se le sue colonne sono basate, puoi avere una matrice per colonna. Ciò può rendere molto più efficace la gestione dei tipi primitivi. vale a dire che puoi avere una colonna che è int [] e un'altra che è double [], è molto più comune per un'intera colonna avere lo stesso tipo di dati, piuttosto che avere lo stesso tipo di dati per un'intera riga.

Tuttavia, in entrambi i casi si sposteranno i dati che verranno ottimizzati per la modifica di righe o colonne e l'esecuzione di un'aggiunta/rimozione dell'altro tipo comporterà una ricostruzione dell'intero set di dati.

(Qualcosa che faccio è avere dati basati su righe e aggiungere colonne alla fine, assumendo che una riga non sia abbastanza lunga, la colonna ha un valore predefinito, questo evita una ricostruzione quando si aggiunge una colonna. colonna, ho un modo per ignorarlo)

Answer 8

Ho provato a utilizzare il SparseObjectMatrix2D dal progetto Colt. I miei dati sono piuttosto densi ma le loro classi Matrix non offrono alcun modo per ingrandirli, quindi sono andato con una matrice sparsa impostata alla dimensione massima.

Sembra utilizzare circa il 10% di memoria in meno e carica circa il 15% più veloce per gli stessi dati, oltre a offrire alcuni metodi di manipolazione intelligenti. Comunque sono interessato ad altre opzioni.

Answer 9

Perché non provare a utilizzare l'implementazione della cache come EHCache. Questo è risultato molto efficace per me, quando ho colpito la stessa situazione.
È possibile archiviare semplicemente la raccolta nell'implementazione di EHcache. Ci sono configurazioni come:

Maximum bytes to be used from Local heap. 

Una volta che i byte utilizzati dai vostri overflow dell'applicazione che configurate nella cache, quindi implementazione della cache si occupa di scrivere i dati sul disco. Inoltre è possibile configurare la quantità di tempo dopo la quale gli oggetti vengono scritti su disco utilizzando l'algoritmo Least Recent Used. Si può essere certi di evitare qualsiasi errore di memoria esaurita, utilizzando questo tipo di implementazioni della cache. Aumenta solo di poco le operazioni di I/O dell'applicazione.
Questa è solo una vista a volo d'uccello della configurazione. Ci sono molte configurazioni per ottimizzare i tuoi requisiti.

Answer 10

Chronicle Map potrebbe avere un sovraccarico inferiore a 20 byte per voce (vedere a test dimostrando ciò). Per confronto, l'overhead di java.util.HashMap varia da 37-42 byte con -XX:+UseCompressedOops a 58-69 byte senza oops compressi (reference).

Inoltre, Chronicle Map memorizza chiavi e valori off-heap, quindi non memorizza intestazioni oggetto, che non sono considerate come overhead di HashMap. Chronicle Map integrates con Chronicle-Values, una libreria per la generazione di implementazioni flyweight di interfacce, il modello suggested by Brian Agnew in un'altra risposta.