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

Question

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

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

// 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, который является закрытым и вызывается writeObject и clone (). Если вы клонируете свой объект или сериализуете его, он обрежет его до правильной длины (при условии, что класс расширил его с помощью метода sureCapacity).

Answer 2

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

https://github.com/lemire/javaewah

http://roaringbitmap.org/