Bitarray très compact en Java

Question

Je cherche une manière très compacte de stocker un bitarray dense de longueur variable en Java. En ce moment, j'utilise BitSet, mais il semble utiliser en moyenne 1,5 * n bits de l'espace de stockage pour un vecteur bit de taille n. En règle générale, ce n'est pas un problème, mais dans ce cas, les bits stockés sont une partie assez importante de l'empreinte mémoire de l'application. Donc, cela aiderait vraiment à les rendre un peu plus petits.

L'espace requis par BitSet semble être dû au fait que le réseau de positions longues utilisé pour sauvegarder la structure de données tend à doubler chaque fois qu'il est étendu pour contenir plus de 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; 
    } 
} 

Je pourrais écrire ma propre implémentation alternative de BitSet qui met à l'échelle la structure de données backend de façon plus conservatrice. Mais, je détesterais vraiment dupliquer des fonctionnalités qui sont déjà dans les bibliothèques de classe standard si je n'ai pas à le faire.

Answer 1

Si vous créez le BitSet en utilisant le constructeur BitSet(int nbits), vous pouvez spécifier la capacité. Si vous devinez que la capacité est mauvaise, et que vous passez la barre, la taille sera doublée. La classe BitSet possède une méthode trimToSize qui est privée et appelée par writeObject et clone(). Si vous clonez votre objet, ou si vous le sériez, il le découpera à la bonne longueur (en supposant que la classe l'ait développée à l'aide de la méthode ensureCapacity).

Answer 2

Vous pourriez bénéficier des solutions BitSet compressées. Voir par exemple:

https://github.com/lemire/javaewah

http://roaringbitmap.org/