Yocker
  1. Yocker
  3. Array sparse efficiente in memoria in Java
Intereting Posts
Come modificare questo javascript con Greasemonkey? “BEGIN_OBJECT atteso, ma era STRING alla riga 1 colonna 1” Javascript – inline vs script esterno – qual è la differenza? 800A0401 – Fine del rendiconto atteso Errore: richiesta di entity framework troppo grande Trovare il più piccolo valore in un array nel modo più efficiente In esecuzione MSBuild non riesce a leggere SDKToolsPath Qual è la differenza tra jQuery’s mouseout () e mouseleave ()? Esiste un modo conciso per scorrere su un stream con indici in Java 8? Come aggiungere la convalida alle mie classi POCO (template) Errore in plot.new (): i margini delle figure sono troppo grandi, la trama dispersa Ordine di inizializzazione delle variabili statiche Prototipo di richiesta AJAX inviata come OPZIONI anziché GET; risultati nell’errore 501 Perché l’interpolazione delle stringhe funziona in Ruby quando non ci sono parentesi graffe? stenografia javascript se istruzione, senza la parte else

Array sparse efficiente in memoria in Java

(Ci sono alcune domande sugli array sparsi efficienti nel tempo ma sto cercando l’efficienza della memoria.)

Ho bisogno dell’equivalente di una List o di Map che

  1. Può crescere su richiesta semplicemente impostando una chiave più grande di qualsiasi altra prima. (Può assumere che le chiavi siano non negative).
  2. È efficiente in termini di memoria come ArrayList nel caso in cui la maggior parte degli indici non sia null , cioè quando i dati reali non sono molto sparsi.
  3. Quando gli indici sono sparsi, consuma spazio proporzionale al numero di indici non null .
  4. Usa meno memoria di HashMap (poiché questo autoboxes le chiavi e probabilmente non sfrutta il tipo di chiave scalare).
  5. Può ottenere o impostare un elemento nel tempo di log ammortizzato (N) dove N è il numero di voci: non è necessario essere il tempo lineare, la ricerca binaria sarebbe accettabile.
  6. Implementato in una libreria Java pura non virale open source (preferibilmente in Maven Central).

Qualcuno sa di una tale class di utilità?

Mi sarei aspettato che le Collezioni di Commons ne avessero una ma non sembrava.

Mi sono imbattuto in org.apache.commons.math.util.OpenIntToFieldHashMap che sembra quasi corretto tranne che il tipo value è un FieldElement che sembra gratuito; Voglio solo che T extends Object . Sembra che sarebbe facile modificare il suo codice sorgente per essere più generico, anche se preferirei usare una dipendenza binaria se ne è disponibile una.

Vorrei provare con le raccolte di trove , c’è TIntObjectMap che può funzionare per i tuoi intenti.

Guarderei l’implementazione SparseArray di Android per l’ispirazione. È ansible visualizzare la fonte scaricando il codice sorgente di AOSP qui http://source.android.com/source/downloading.html

Ti suggerirò di usare OpenIntObjectHashMap dalla libreria Colt. collegamento

Ho salvato il mio caso di test come jglick / inthashmap . I risultati: 

 HashMap size: 1017504 TIntObjectMap size: 853216 IntHashMap size: 846984 OpenIntObjectHashMap size: 760472