Очень компактный Bitarray в Java

Question

Я ищу очень компактный способ хранения плотной битрейты переменной длины в Java. Прямо сейчас, я использую BitSet, но, похоже, он использует в среднем 1.5 * n бит пространства для хранения бит-вектора размера n. Как правило, это не проблема, но в этом случае битрейты, которые хранятся, являются довольно значительной частью области памяти приложения. Таким образом, это действительно помогло бы получить их немного меньше.

Пространство требует BitSet, как представляется, в связи с тем, что массив длинных позиций используется для резервного структуры данных имеет тенденцию в два раза каждый раз, когда он расширен, чтобы держать больше битов:

// 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; 
    } 
} 

Я мог бы написать моя собственная альтернативная реализация BitSet, которая более консервативно масштабирует структуру данных. Но мне бы очень не хотелось дублировать функциональные возможности, которые уже есть в стандартных библиотеках классов, если мне это не нужно.

Answer 1

Если вы создаете BitSet, используя конструктор BitSet(int nbits), вы можете указать емкость. Если вы угадаете, что емкость неправильная, и перейдите, она удвоит размер.

Класс BitSet класс имеет метод trimToSize, который является private и вызывается writeObject и clone(). Если вы клонируете свой объект или сериализуете его, он будет обрезать его до нужной длины (предполагая, что класс расширил его с помощью метода securityCapacity).

Answer 2

Вы можете воспользоваться сжатыми альтернативами BitSet. Смотрите, например:

https://github.com/lemire/javaewah

http://roaringbitmap.org/