Compressed SortedSet implementazione
-
26-10-2019 - |
Domanda
ho bisogno di memorizzare un gran numero di valori Long
in un'implementazione SortedSet
in maniera efficiente dello spazio. Stavo considerando bit-set implementazioni e scoperto Javaewah . Tuttavia, le API aspetta int
valori piuttosto che long
s.
Qualcuno può raccomandare eventuali alternative o suggerire un buon modo per risolvere questo problema? Sto riguarda principalmente l'efficienza dello spazio. Sulla costruzione del set dovrò accedere all'elemento minimo e massimo una volta. Tuttavia, il tempo di accesso non è una preoccupazione enorme (vale a dire in modo completamente run-length codificato implementazione andrà bene).
Modifica
I dovrebbe essere chiaro che l'applicazione non deve implementare l'interfaccia SortedSet
fornendo posso accedere elementi massime della raccolta e minimo.
Soluzione
Si potrebbe utilizzare TLongArrayList che utilizza un sotto long[]
. Supporta sort()
in modo che il min e max sarà il primo e l'ultimo valore.
In alternativa si potrebbe utilizzare un long[]
con una lunghezza e farlo da soli. ;)
Questo userà circa 64 byte più che i valori grezzi stessi. È possibile ottenere più compatta se è possibile fare alcune ipotesi circa l'intervallo di valori lunghi. per esempio. se sono in realtà limitati a 48 bit.
Si potrebbe considerare l'utilizzo di LongBuffer. Se si tratta di memoria mappata evita usando heap o diretto alla memoria, ma si sarebbe implementare una routine di ordinamento te stesso.
Se sono raggruppati, si potrebbe essere in grado di rappresentare i dati come un insieme di intervalli. Gli intervalli potrebbero essere un puro A - B, o una BitSet con un valore iniziale. Più tardi funziona bene per i numeri di telefono. ;)
Altri suggerimenti
Non sono sicuro se ha Set o quanto efficiente sia rispetto al normale JCF, ma dare un'occhiata a questo: