Ottimizza l'utilizzo della memoria di una raccolta di stringhe in Java

Question

Ho un gran numero di coppie nome-valore (circa 100k) che ho bisogno di memorizzare in una sorta di cache (ad esempio una mappa hash) dove il valore è una stringa con una dimensione media di circa 30k byte.

Ora so per certo che un gran numero di valori ha esattamente gli stessi dati di stringa. Per evitare di dover allocare più volte i dati di stringa identici, vorrei in qualche modo riutilizzare una stringa allocata in precedenza, consumando quindi meno memoria. Inoltre, questo deve essere ragionevolmente veloce. Ad esempio, la scansione di tutti i valori assegnati in precedenza uno per uno non è un'opzione.

Qualche raccomandazione su come risolvere questo problema?

Answer 1

fare non uso String.Intern (ci sono stati diversi problemi di memoria relativi a questo nel corso degli anni). invece, crea la tua cache, simile a String.intern. in sostanza, vuoi una mappa, in cui ogni chiave si associa a se stessa. poi, prima di cache qualsiasi stringa, è "stagista" è:

private Map<String,WeakReference<String>> myInternMap = new WeakHashMap<String,,WeakReference<String>>(); 
public String intern(String value) { 
    synchronized(myInternMap) { 
    WeakReference<String> curRef = myInternMap.get(value); 
    String curValue = ((curRef != null) ? curRef.get() : null); 
    if(curValue != null) { 
     return curValue; 
    } 

    myInternMap.put(value, new WeakReference<String>(value)); 
    return value; 
    } 
} 

nota, si utilizza WeakReferences per le chiavi e valori in modo da non tenere i riferimenti per le stringhe che non si è più in uso.

Answer 2

String.intern() ti aiuterà qui (molto probabilmente). Risolverà più istanze della stringa stessa su una copia.

EDIT: ho suggerito che questo sarebbe "molto probabile" aiuto. In quali scenari non sarà? Le stringhe Internazionali avranno l'effetto di memorizzare quelle rappresentazioni di stringa internate permanentemente. Se il dominio del problema è un processo one-shot, questo potrebbe non essere un problema. Se si tratta di un processo di lunga durata (come un'app Web), si potrebbe avere un problema.

esiterei a dire mai uso internato (I esiterei a dire mai fare nulla). Tuttavia ci sono scenari in cui non è l'ideale.

Answer 3

String.intern è la scelta più ovvia come dice Brian. Ma se non si desidera eseguire internamente tutta la stringa in memoria, è possibile utilizzare un Set per vedere prima se il valore è presente. Ecco il codice non testato. Si dovrà lavorare fuori la rimozione dalla mappa inversa quando viene rimosso dal principale

class Map2<K, V> implements Map<K, V> 
    { 
    Map<K, V> _map = Maps.newHashMap(); 
    Set<V, V> _rev = Maps.newHashMap(); 

    V put(K k, V v) { 
     if (_rev.containsKey(v)) { 
     V prev = _rev.get(v); 
     return _map.put(k, prev); 
     } else { 
     _rev.put(v, v); 
     return _map.put(k,v); 
     } 
    } 

Answer 4

Dipende in qualche modo da come si crea lo String.

Un modo possibile è quello di utilizzare TreeSet che utilizza un Comparator che può confrontare String s esistente e la fonte della vostra nuova String. Utilizzare SortedSet.tailSet e uno Iterator per trovare uno String esistente. O in alternativa NavigableSet.ceiling/floor o TreeMap con una configurazione simile.

Ho scritto uno weblog entry su un'altra tecnica per memorizzare nella cache oggetti immutabili (in particolare stringhe), ma è più adatto per oggetti più piccoli.

String.intern ha problemi di prestazioni.

Answer 5

Concordare con gli altri su non utilizzare String.intern(): una volta che hai messo una stringa lì, non andrà mai via.Guarda le prime revisioni di Xerces sul perché questa sia una cattiva idea.

Una soluzione migliore è quella di utilizzare un WeakHashMap, avvolgendo il valore in una WeakReference:

private Map<String,WeakReference<String>> _map 
    = new WeakHashMap<String,WeakReference<String>>(); 

public synchronized String intern(String str) 
{ 
    WeakReference<String> ref = _map.get(str); 
    String s2 = (ref != null) ? ref.get() : null; 
    if (s2 != null) 
     return s2; 
    str = new String(str); 
    _map.put(str, new WeakReference(str)); 
    return str; 
} 

Questo codice è da un article that I wrote sugli oggetti di riferimento Java. Troverai la spiegazione lì.

EDIT: necessario creare una nuova stringa qui (e aggiornerò l'articolo) perché l'originale potrebbe essere una sottostringa di un array di caratteri molto più grande. Ho pensato che fosse stato risolto attorno a JDK 1.3, ma apparentemente no (almeno non in 1.5).

Answer 6

È possibile comprimere le stringhe. Una stringa da 30 K dovrebbe ottenere un buon rapporto di compressione. Ho scritto un trucco per comprimere la grande stringa come esercizio, ma potresti usare un byte [] dei dati compressi per memorizzare la stringa.

Una stringa di caratteri da 30 K utilizzerà circa 60 KB (2 byte per carattere), quindi è probabile che anche l'utilizzo di getBytes() sia un miglioramento.

Answer 7

fare è effettivamente necessario Strings, o avete solo bisogno di qualsiasi vecchio CharSequence? In caso contrario, prendere in considerazione l'implementazione di uno "compact" CharSequence come quello che suggerisco nel collegamento.