Qualcuno sa di un'implementazione java.util.Map ottimizzata per l'utilizzo con poca memoria?

Question

Ho cercato nei soliti posti (apache comuni, google) e non sono riuscito a trovarne uno ...

Dovrebbe essere opensource.

Praticamente uno per uno basato su un elenco collegato. Il caso d'uso è 10'000 di mappe, con non necessariamente molti valori in. Non ha bisogno di scalare, in quanto posso convertirlo quando diventa troppo grande.

Alcuni numeri, dimensioni che utilizzano alcuni valori jvm calcolati (8bytes/java.lang.Object, 4bytes/ref) HashMap è di circa 100 + 32n byte, il migliore teorico è 12 + 20 * n. < - Lo voglio, per il piccolo n.

Answer 1

Ok, implementato da solo alla fine. Ho fatto un confronto di velocità e ho trovato che, rispetto ad una HashMap, era ancora leggermente più veloce con 4 voci, ma più lento con 5 o più. Ho fatto i test con una lunga lista di chiavi che ho cercato di dare un trucco simile a una lista di parole inglesi casuali.

import java.util.*; 

// PUBLIC DOMAIN 
public class SmallMap extends AbstractMap { 

    private Entry entry = null; 

    public void clear() { entry = null; } 
    public boolean isEmpty() { return entry==null; }  
    public int size() { 
     int r = 0; 
     for(Entry e = entry; e!=null; e = e.next) r++; 
     return r; 
    } 

    public boolean containsKey(Object key) { 
     for(Entry e = entry; e!=null; e = e.next){ 
      if(e.key.equals(key)){ 
       return true; 
      } 
     } 
     return false; 
    } 

    public boolean containsValue(Object value) { 
     for(Entry e = entry; e!=null; e = e.next){ 
      if(e.value==null){ 
       if(value==null) return true; 
      }else if(e.value.equals(value)){ 
       return true; 
      } 
     } 
     return false; 
    } 

    public Object get(Object key) { 
     for(Entry e = entry; e!=null; e = e.next){ 
      if(e.key.equals(key)){ 
       return e.value; 
      } 
     } 
     return null; 
    } 

    public Object put(Object key, Object value) { 
     for(Entry e = entry; e!=null; e = e.next){ 
      if(e.key.equals(key)){ 
       Object r = e.value; 
       e.value = value; 
       return r; 
      } 
     } 
     entry = new Entry(key, value, entry); 
     return null; 
    } 

    public Object remove(Object key) { 
     if(entry!=null){ 
      if(entry.key.equals(key)){ 
       Object r = entry.value; 
       entry = entry.next; 
       return r; 
      } 
      for(Entry e = entry; e.next!=null; e = e.next){ 
       if(key.equals(e.next.key)){ 
        Object r = e.next.value; 
        e.next = e.next.next; 
        return r; 
       } 
      } 
     } 
     return null; 
    } 

    public Set entrySet() { return new EntrySet(); } 

    class EntrySet extends AbstractSet{ 
     public Iterator iterator() { 
      return new Iterator(){ 

       Entry last = null; 
       Entry e = entry; 
       public boolean hasNext() { return e!=null; } 

       public Object next() { 
        last = e; 
        e = e.next; 
        return last; 
       } 

       public void remove() { 
        if(last == null) throw new IllegalStateException(); 
        SmallMap.this.remove(last.key); 
       } 
      }; 
     } 

     public int size() { return SmallMap.this.size();} 
    } 

    static private class Entry implements java.util.Map.Entry { 
     final Object key; 
     Object value; 
     Entry next; 
     Entry(Object key, Object value, Entry next){ 
      if(key==null) throw new NullPointerException(); 
      this.key = key; 
      this.value = value; 
      this.next = next; 
     } 
     public Object getKey() { return key; } 
     public Object getValue() { return value; } 
     public Object setValue(Object value) { 
      Object r = this.value; 
      this.value = value; 
      return r; 
     } 
     public int hashCode() { 
      return (key == null ? 0 : key.hashCode())^
       (value == null ? 0 : value.hashCode()); 
     } 
    } 
} 

Answer 2

Semplicemente, mi raccomando di utilizzare uno di HashMap, Hashtable e ConcurrentHashMap di JDK a seconda dei requisiti di sincronizzazione o di concorrenza. Se si decide di usarli, l'impostazione di InitialCapacity e loadFactor nel costruttore può essere d'aiuto.

Le collezioni Google e le raccolte di apache comuni forniscono ulteriori funzionalità: LRUMap, ReferenceMap, MultikeyMap e così via. Ma non penso che non ci siano solo piccole dimensioni.

Answer 3

LinkedHashMap utilizza una lista collegata, penso, ma dubito che sia ottimizzata per l'utilizzo a bassa memoria. Di solito l'intero punto di una mappa è di velocizzare le ricerche da chiave a valore, il che spiega perché non trovi ciò che ti serve nei luoghi comuni. Potrebbe essere più semplice scrivere la tua implementazione di Map, e forse potresti anche rilasciare il codice nel caso in cui qualcun altro abbia bisogno della stessa cosa.

Answer 4

Scrivi il codice in un modo che nasconde l'uso delle mappe (dovresti farlo comunque e sembra che lo sia anche tu). Nel momento in cui conta, perché hai profilato il codice e puoi vedere che la memoria è davvero un problema, trovane una :-)

Se sai che a questo punto c'è un problema, allora, scusa Non ne conosco uno. Tuttavia, troppo spesso le persone si occupano di "idea" che il codice sarà lento/se molta memoria/etc ... e inizieranno a cercare di ottimizzarlo in anticipo piuttosto che rendere il codice corretto.

Detto questo, se si sta scrivendo qualcosa che si sa che importa, si dovrebbe misurare come si va. Per esempio sto lavorando sul codice per analizzare i file di classe, faccio una piccola modifica e poi vedo come influenza le prestazioni. Ad esempio, sapevo per certo che un cambiamento che ho apportato (3 righe) ha reso il mio programma 4 volte più lento ... Ho trascorso il tempo a quel punto e ho scoperto il modo più veloce per farlo.

Inoltre, sei sicuro che le mappe siano necessarie se il valore di "n" è piccolo? Forse una lista è abbastanza veloce? Hai anche provato a sintonizzare la mappa esistente per farla usare meno memoria?

Answer 5

potrebbe avere uno sguardo a Commons-collezioni Flat3Map, è ottimizzato per memorizzare i 3 valori in 3 campi e trabocca ad un'altra mappa a 4.

non ho guardato alla realizzazione ma può essere la pena di pensare . L'unico problema è che dal momento che le commons-collections sono compatibili con 1.3 non ci sono generici.

Answer 6

Avvolgi una lista array con l'interfaccia mappa. ArrayList utilizza solo pochi byte. Ogni nodo ha bisogno di due puntatori, uno per la chiave e uno per il valore. Utilizzare la ricerca sequenziale per cercare i valori. Finché ci sono solo poche voci, le prestazioni saranno OK [*]. Questo ti darà la possibilità di usare mappe reali per i pochi vasi in cui hai un gran numero di valori.

*: Supponiamo che la dimensione media della mappa sia 10. I computer di oggi possono confrontare circa 100 milioni di chiavi al secondo, quindi ogni ricerca impiegherà in media meno di cinque microsecondi.

Se le prestazioni sono ancora pessime per il tuo caso d'uso, puoi provare a ordinare l'array per chiave e utilizzare la ricerca binaria.

Answer 7

Dipende molto da come si utilizzeranno queste mappe, è possibile popolare in un'unica ripresa e quindi eseguire semplicemente le ricerche (è necessario che tali ricerche siano veloci)?

Un'implementazione utilizzando una quantità minima di memoria sarebbe quello di mettere tutti gli elementi di un array e per fare una scansione per trovare elementi (ma credo che questo non è veloce sufficiente per le vostre esigenze) ...

Se conosci tutti gli elementi all'inizio puoi provare a selezionare un buon metodo di hash senza troppe collisioni.

O forse si potrebbe utilizzare TreeMap se si consente il tempo di inserimento lento ...

Answer 8

Forse questa risposta è un po 'tardi, ma un'occhiata a Javolution progetto. Contiene implementazioni di molte strutture dati, pensate per ambienti embedded e in tempo reale. Concretamente, esiste una classe FastMap che potrebbe semplicemente fare ciò che vuoi.

Answer 9

Se si memorizzano solo String s, un'occhiata a http://code.google.com/p/flatmap

modificare Oh, scusa, vedo che siete alla ricerca di piccole mappe non enormi, dimenticare il mio consiglio, allora.

Answer 10

So che è una vecchia domanda ma forse qualcuno potrebbe aggiungere ulteriori idee.

NB: Le seguenti sarebbe veramente solo senso per uno specifico sottoinsieme di casi di utilizzo:

Se il requisito comprende altamente sovrapposti mazzi di chiavi (nel caso estremo lo stesso insieme di chiavi per tutte le mappe) quindi una molto soluzione efficace potrebbe essere quella di "esternalizzare" le chiavi rispetto alle mappe e fare in modo che le mappe contengano solo valori, in una matrice.

L'implementazione non deve dipendere "strutturalmente" dal fattore di sovrapposizione, ma la mia funziona meglio più le chiavi si sovrappongono. Come ti aspetteresti.

Non riesco a fornire dettagli esatti della mia implementazione, ma è importante disporre di un meccanismo adeguato per convertire chiavi (memorizzate al di fuori dell'oggetto mappa) in indici nell'array dei valori, consentendo anche il mantenimento della matrice di valori compact, ovvero avere la lunghezza cinque se la mappa contiene cinque mappature.

Dire che le chiavi di tutte queste mappe si trovano in una mappa separata, mappata ai numeri. Quindi si tratta di un modo per mettere in relazione numeri e indici di array.

Scusate se questo non è abbastanza specifico, ma ho pensato che l'idea sia interessante e semplice allo stesso tempo, e potrebbe essere usata come una direzione alternativa nello sviluppo di una mappa efficiente della memoria.

Anche in questo caso, è intrinsecamente adatto a casi di utilizzo di "sovrapposizione di chiavi" elevate, ma è esso stesso generico. Potrebbero verificarsi problemi di prestazioni se la sovrapposizione è troppo bassa, a seconda dei dettagli di implementazione.