Dove posso trovare un buon esempio di tecniche per compattare i dati in memoria? [chiuso]

Question

Dove posso trovare un buon esempio di tecniche per compattare i dati in memoria? [chiuso]

#1 da (1 voti)
#2 da (1 voti)

4

Sto scrivendo un framework Java per manipolare una grande quantità di dati in memoria, dove molte "celle" vicine tra loro avranno lo stesso valore.

Sto cercando algoritmi e / o tecniche appositamente progettate per eliminare quei duplicati pur mantenendo una velocità di accesso in lettura veloce in memoria . Cioè, tecniche che mantengono una velocità di accesso di di O (1)

I miei dati sono archiviati in oggetti immutabili, per consentire una multi-threading veloce. I dati stessi possono essere qualsiasi cosa, da 4 bit per cella a doppi per matrici di bean, ecc.

java performance compression

posta Sebastien Diot 08.02.2012 - 13:51
fonte

2 risposte

1

Se c'è molta ripetizione dei valori allora qualche forma di codifica della lunghezza di esecuzione potrebbe funzionare per la compressione lato, la parte difficile sarebbe mantenere O (1) ricerca (o se rilassiamo quel vincolo leggermente, ricerca veloce)

potresti ottenere la ricerca di log m relativamente facilmente (dove m è il numero di esecuzioni, non il numero di valori) invece di memorizzare la lunghezza con ogni valore memorizza l'indice

es. usando l'esempio wikipedia di

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

invece di memorizzare le lunghezze con ogni valore per una corsa (aggiunto parens per chiarezza)

(12 W)(1 B)(12 W)(3 B)(24 W)(1 B)(14 W)

potremmo memorizzare gli indici a cui cambiamo il valore (pluss un valore finale se necessario)

(0 W)(12 B)(13 W)(25 B)(28 W)(52 B)(53 W)(67 null)

possiamo quindi utilizzare una ricerca binaria sull'indice per trovare il valore per qualsiasi indice nel log (m) che potrebbe essere abbastanza veloce?

risposta data 08.02.2012 - 14:31
fonte

1

Guarda nella memoizzazione. Potresti essere in grado di memorizzare i puntatori ai dati, o un prefisso parziale, invece dei dati stessi.

Naturalmente, se i tuoi dati sono abbastanza piccoli, potrebbe non essere una vittoria.

risposta data 08.02.2012 - 14:55
fonte

Leggi altre domande sui tag java performance compression

Come strutturare un'applicazione che legge i codici a barre UPC Dove posso trovare i dati aziendali da utilizzare nella mia applicazione?

score 1 · Accepted Answer

Se c'è molta ripetizione dei valori allora qualche forma di codifica della lunghezza di esecuzione potrebbe funzionare per la compressione lato, la parte difficile sarebbe mantenere O (1) ricerca (o se rilassiamo quel vincolo leggermente, ricerca veloce)

potresti ottenere la ricerca di log m relativamente facilmente (dove m è il numero di esecuzioni, non il numero di valori) invece di memorizzare la lunghezza con ogni valore memorizza l'indice

es. usando l'esempio wikipedia di

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

invece di memorizzare le lunghezze con ogni valore per una corsa (aggiunto parens per chiarezza)

(12 W)(1 B)(12 W)(3 B)(24 W)(1 B)(14 W)

potremmo memorizzare gli indici a cui cambiamo il valore (pluss un valore finale se necessario)

(0 W)(12 B)(13 W)(25 B)(28 W)(52 B)(53 W)(67 null)

possiamo quindi utilizzare una ricerca binaria sull'indice per trovare il valore per qualsiasi indice nel log (m) che potrebbe essere abbastanza veloce?