Bitarray muito compacto em Java

Question

Estou procurando uma maneira muito compacta de armazenar um bitarray denso de comprimento variável em Java.No momento, estou usando BitSet, mas parece usar em média 1,5*n bits de espaço de armazenamento para um vetor de bits de tamanho n.Normalmente, isso não é um problema, mas neste caso os bitarrays armazenados são uma parte bastante significativa do consumo de memória do aplicativo.Então, realmente ajudaria se eles fossem um pouco menores.

O espaço requerido pelo BitSet parece ser devido ao fato de que o array de longs usado para apoiar a estrutura de dados tende a dobrar cada vez que é expandido para conter mais 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;
  }
}

Eu poderia escrever minha própria implementação alternativa do BitSet que dimensionasse a estrutura de dados de back-end de maneira mais conservadora.Mas eu realmente odiaria duplicar funcionalidades que já estão nas bibliotecas de classes padrão, se não for necessário.

Answer 1

Se você criar o BitSet usando o construtor BitSet(int nbits) você pode especificar a capacidade.Se você adivinhar a capacidade errada e ultrapassar, ela dobrará o tamanho.

O BitSet aula tem um trimToSize método que é privado e é chamado por writeObject e clone().Se você clonar seu objeto ou serializá-lo, ele será cortado no comprimento correto (assumindo que a classe o expandiu por meio do método garantirCapacity).

Answer 2

Você pode se beneficiar das alternativas compactadas do BitSet.Veja por exemplo:

https://github.com/lemire/javaewah

http://roaringbitmap.org/