Bitarray muy compacto en Java

Question

Estoy buscando una manera muy compacta de almacenar una bitarra de longitud variable densa en Java. En este momento, estoy usando BitSet, pero parece utilizar en promedio 1.5 * n bits de espacio de almacenamiento para un vector de bits de tamaño n. Normalmente, esto no es un problema, pero en este caso los bitarrays que se almacenan son una parte bastante importante de la memoria de la aplicación. Por lo tanto, realmente ayudaría a que sean un poco más pequeños.

El espacio requerido por BitSet parece ser debido al hecho de que la matriz de largos utilizados para respaldar la estructura de datos tiende a duplicarse cada vez que se expande para contener más bits:

// BitSet's resizing code 
private void ensureCapacity(int wordsRequired) { 
    if (words.length < wordsRequired) { 
    // Allocate larger of doubled size or required size 
    int request = Math.max(2 * words.length, wordsRequired); 
    words = Arrays.copyOf(words, request); 
    sizeIsSticky = false; 
    } 
} 

podría escribir mi propia implementación alternativa de BitSet que escala la estructura de datos de back-end de manera más conservadora. Pero, realmente no me gustaría duplicar la funcionalidad que ya está en las bibliotecas de clases estándar si no es necesario.

Answer 1

Si crea el BitSet utilizando el constructor BitSet(int nbits), puede especificar la capacidad. Si adivina la capacidad incorrecta y la revisa, duplicará el tamaño.

La clase BitSet tiene un método trimToSize que es privado, y es llamado por writeObject y clone(). Si clonas tu objeto o lo serializas, lo recortará a la longitud correcta (suponiendo que la clase lo haya expandido mediante el método ensureCapacity).

Answer 2

Puede beneficiarse de las alternativas comprimidas de BitSet. Véase, por ejemplo:

https://github.com/lemire/javaewah

http://roaringbitmap.org/