Compressed SortedSet implementazione

Question

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 longs.

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.

Answer 1

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. ;)

Answer 2

Non sono sicuro se ha Set o quanto efficiente sia rispetto al normale JCF, ma dare un'occhiata a questo:

http://commons.apache.org/primitives/