1. Обзор
В этом уроке мы увидим, как мы можем использовать BitSet для представления вектора битов.
Во-первых, мы начнем с обоснования отказа от использования boolean[] . Затем, ознакомившись с внутренним устройством BitSet , мы более подробно рассмотрим его API.
2. Массив битов
Кто-то может возразить, что для хранения массивов битов и управления ими следует использовать логическое значение [] в качестве нашей структуры данных. На первый взгляд, это может показаться разумным предложением.
Однако каждый логический элемент в boolean[] обычно занимает один байт вместо одного бита . Поэтому, когда у нас есть жесткие требования к памяти или мы просто стремимся уменьшить объем памяти, boolean[] далеко не идеален.
Для конкретики давайте посмотрим, сколько места занимает логическое значение [] с 1024 элементами:
boolean[] bits = new boolean[1024];
System.out.println(ClassLayout.parseInstance(bits).toPrintable());
В идеале мы ожидаем, что этот массив займет 1024 бита памяти. Однако Java Object Layout (JOL) раскрывает совершенно другую реальность:
[Z object internals:
OFFSET SIZE TYPE DESCRIPTION VALUE
0 4 (object header) 01 00 00 00 (00000001 00000000 00000000 00000000) (1)
4 4 (object header) 00 00 00 00 (00000000 00000000 00000000 00000000) (0)
8 4 (object header) 7b 12 07 00 (01111011 00010010 00000111 00000000) (463483)
12 4 (object header) 00 04 00 00 (00000000 00000100 00000000 00000000) (1024)
16 1024 boolean [Z. N/A
Instance size: 1040 bytes
Если мы проигнорируем накладные расходы заголовка объекта, элементы массива потребляют 1024 байта вместо ожидаемых 1024 бит. Это на 700% больше памяти, чем мы ожидали.
Проблемы с адресацией и разрывы слов являются основными причинами, по которым логические значения представляют собой нечто большее, чем один бит.
Чтобы решить эту проблему, мы можем использовать комбинацию числовых типов данных (таких как long ) и побитовых операций. Вот тут-то и появляется BitSet .
3. Как работает BitSet
Как мы упоминали ранее, для достижения использования памяти в один бит на флаг API BitSet использует комбинацию основных числовых типов данных и побитовых операций.
Для простоты предположим, что мы собираемся представить восемь флагов одним байтом . Сначала мы инициализируем все биты этого единственного байта нулями:
Теперь, если мы хотим установить бит в позиции три в true , мы должны сначала сдвинуть число 1 влево на три:
А затем или его результат с текущим значением байта :
Тот же процесс произойдет, если вы решите установить бит в индексе семь:
Как показано выше, мы выполняем сдвиг влево на семь бит и объединяем результат с предыдущим значением байта с помощью оператора или .
3.1. Получение битового индекса
Чтобы проверить, установлен ли конкретный битовый индекс в значение true или нет, мы будем использовать оператор and . Например, вот как мы проверяем, установлен ли третий индекс:
- Выполнение сдвига влево на три бита для значения один
Ирезультат с текущим значениембайта- Если результат больше нуля, то мы нашли совпадение, и этот битовый индекс фактически установлен. В противном случае запрошенный индекс ясен или равен
false
На приведенной выше диаграмме показаны этапы операции получения для третьего индекса. Однако если мы запросим чистый индекс, результат будет другим:
Поскольку результат и равен нулю, индекс четыре ясен.
3.2. Расширение хранилища
В настоящее время мы можем хранить только 8-битный вектор. Чтобы выйти за пределы этого ограничения, нам просто нужно использовать массив байтов вместо одного байта , вот и все!
Теперь каждый раз, когда нам нужно установить, получить или очистить определенный индекс, мы должны сначала найти соответствующий элемент массива. Например, предположим, что мы собираемся установить индекс 14:
Как показано на диаграмме выше, после нахождения нужного элемента массива мы установили соответствующий индекс.
Кроме того, если мы хотим установить здесь индекс больше 15, BitSet сначала расширит свой внутренний массив. Только после расширения массива и копирования элементов он установит запрошенный бит. Это чем-то похоже на внутреннюю работу ArrayList .
До сих пор мы использовали тип данных byte для простоты. Однако API BitSet использует массив длинных значений для внутреннего использования .
4. API -интерфейс BitSet
Теперь, когда мы достаточно знаем о теории, пришло время посмотреть, как выглядит BitSet API.
Для начала давайте сравним объем памяти, занимаемый экземпляром BitSet с 1024 битами, с логическим значением [] , которое мы видели ранее:
BitSet bitSet = new BitSet(1024);
System.out.println(GraphLayout.parseInstance(bitSet).toPrintable());
Это напечатает как неглубокий размер экземпляра BitSet , так и размер его внутреннего массива:
java.util.BitSet@75412c2fd object externals:
ADDRESS SIZE TYPE PATH VALUE
70f97d208 24 java.util.BitSet (object)
70f97d220 144 [J .words [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Как показано выше, внутри используется long[] с 16 элементами (16 * 64 бита = 1024 бита). В любом случае, этот экземпляр использует в общей сложности 168 байт, в то время как логическое значение[] использует 1024 байта .
Чем больше у нас битов, тем больше увеличивается разница в занимаемой площади. Например, для хранения 1024 * 1024 бит логическое значение [] занимает 1 МБ, а экземпляр BitSet — около 130 КБ.
4.1. Создание BitSet s
Самый простой способ создать экземпляр BitSet — использовать конструктор без аргументов :
BitSet bitSet = new BitSet();
Это создаст экземпляр BitSet с long[] размера one . Конечно, он может автоматически увеличить этот массив, если это необходимо.
Также возможно создать BitSet с начальным количеством битов :
BitSet bitSet = new BitSet(100_000);
Здесь внутренний массив будет иметь достаточно элементов для хранения 100 000 бит. Этот конструктор пригодится, когда у нас уже есть разумная оценка количества битов для хранения. В таких случаях использования он может предотвратить или уменьшить ненужное копирование элементов массива при его увеличении .
Можно даже создать BitSet из существующих long[] , byte[] , LongBuffer и ByteBuffer . Например, здесь мы создаем экземпляр BitSet из данного long[] :
BitSet bitSet = BitSet.valueOf(new long[] { 42, 12 });
Есть еще три перегруженные версии статического фабричного метода valueOf() для поддержки других упомянутых типов.
4.2. Установка битов
Мы можем установить значение определенного индекса в true , используя метод set(index) :
BitSet bitSet = new BitSet();
bitSet.set(10);
assertThat(bitSet.get(10)).isTrue();
Как обычно, индексы отсчитываются от нуля. Можно даже установить для диапазона битов значение true , используя метод set(fromInclusive, toExclusive ) :
bitSet.set(20, 30);
for (int i = 20; i <= 29; i++) {
assertThat(bitSet.get(i)).isTrue();
}
assertThat(bitSet.get(30)).isFalse();
Как видно из сигнатуры метода, начальный индекс является инклюзивным, а конечный — исключающим.
Когда мы говорим об установке индекса, мы обычно имеем в виду установку для него значения true . Несмотря на эту терминологию, мы можем установить конкретный битовый индекс в false , используя метод set(index, boolean) :
bitSet.set(10, false);
assertThat(bitSet.get(10)).isFalse();
Эта версия также поддерживает установку диапазона значений:
bitSet.set(20, 30, false);
for (int i = 20; i <= 29; i++) {
assertThat(bitSet.get(i)).isFalse();
}
4.3. Очистка битов
Вместо того, чтобы устанавливать для определенного битового индекса значение false , мы можем просто очистить его с помощью метода clear(index) :
bitSet.set(42);
assertThat(bitSet.get(42)).isTrue();
bitSet.clear(42);
assertThat(bitSet.get(42)).isFalse();
Более того, мы также можем очистить диапазон битов с помощью перегруженной версии clear(fromInclusive, toExclusive) :
bitSet.set(10, 20);
for (int i = 10; i < 20; i++) {
assertThat(bitSet.get(i)).isTrue();
}
bitSet.clear(10, 20);
for (int i = 10; i < 20; i++) {
assertThat(bitSet.get(i)).isFalse();
}
Интересно, что если мы вызовем этот метод без передачи каких-либо аргументов, он очистит все установленные биты :
bitSet.set(10, 20);
bitSet.clear();
for (int i = 0; i < 100; i++) {
assertThat(bitSet.get(i)).isFalse();
}
Как показано выше, после вызова метода clear() все биты обнуляются.
4.4. Получение битов
До сих пор мы довольно широко использовали метод get(index) . Когда запрошенный битовый индекс установлен, этот метод вернет true . В противном случае он вернет false :
bitSet.set(42);
assertThat(bitSet.get(42)).isTrue();
assertThat(bitSet.get(43)).isFalse();
Подобно set и clear , мы можем получить диапазон битовых индексов, используя метод get(fromInclusive, toExclusive) :
bitSet.set(10, 20);
BitSet newBitSet = bitSet.get(10, 20);
for (int i = 0; i < 10; i++) {
assertThat(newBitSet.get(i)).isTrue();
}
Как показано выше, этот метод возвращает другой BitSet в диапазоне [20, 30) от текущего. То есть индекс 20 переменной bitSet эквивалентен нулевому индексу переменной newBitSet .
4.5. Переворачивание битов
Чтобы инвертировать текущее значение битового индекса, мы можем использовать метод flip (index) . То есть он превратит истинные значения в ложные и наоборот:
bitSet.set(42);
bitSet.flip(42);
assertThat(bitSet.get(42)).isFalse();
bitSet.flip(12);
assertThat(bitSet.get(12)).isTrue();
Точно так же мы можем добиться того же для диапазона значений, используя метод flip(fromInclusive, toExclusive) :
bitSet.flip(30, 40);
for (int i = 30; i < 40; i++) {
assertThat(bitSet.get(i)).isTrue();
}
4.6. Длина
Существует три метода длины для BitSet . Метод size() возвращает количество битов, которое может представлять внутренний массив . Например, поскольку конструктор без аргументов выделяет массив long[] с одним элементом, то size() вернет для него 64:
BitSet defaultBitSet = new BitSet();
assertThat(defaultBitSet.size()).isEqualTo(64);
С одним 64-битным числом мы можем представить только 64 бита. Конечно, это изменится, если мы передадим количество бит явно:
BitSet bitSet = new BitSet(1024);
assertThat(bitSet.size()).isEqualTo(1024);
Более того, метод кардинальности() представляет количество установленных битов в BitSet :
assertThat(bitSet.cardinality()).isEqualTo(0);
bitSet.set(10, 30);
assertThat(bitSet.cardinality()).isEqualTo(30 - 10);
Сначала этот метод возвращает ноль, так как все биты равны false . После установки диапазона [10, 30) в значение true вызов метода cardinality() возвращает 20.
Кроме того, метод length() возвращает один индекс после индекса последнего установленного бита :
assertThat(bitSet.length()).isEqualTo(30);
bitSet.set(100);
assertThat(bitSet.length()).isEqualTo(101);
Сначала последний заданный индекс равен 29, поэтому этот метод возвращает 30. Когда мы устанавливаем для индекса 100 значение true, метод length() возвращает 101. Также стоит упомянуть, что этот метод вернет ноль, если все биты очищены .
Наконец, метод isEmpty() возвращает false , если в BitSet есть хотя бы один установленный бит . В противном случае он вернет true :
assertThat(bitSet.isEmpty()).isFalse();
bitSet.clear();
assertThat(bitSet.isEmpty()).isTrue();
4.7. Объединение с другими BitSet'ами
Метод intersects(BitSet) принимает другой BitSet и возвращает true , когда два BitSet имеют что-то общее . То есть у них есть хотя бы один установленный бит в одном и том же индексе:
BitSet first = new BitSet();
first.set(5, 10);
BitSet second = new BitSet();
second.set(7, 15);
assertThat(first.intersects(second)).isTrue();
Диапазон [7, 9] установлен в обоих BitSet , поэтому этот метод возвращает true .
Также возможно выполнить логическую операцию и над двумя BitSet s :
first.and(second);
assertThat(first.get(7)).isTrue();
assertThat(first.get(8)).isTrue();
assertThat(first.get(9)).isTrue();
assertThat(first.get(10)).isFalse();
Это выполнит логическое и между двумя BitSet и изменит первую переменную с результатом. Точно так же мы можем выполнить логическое xor для двух BitSet :
first.clear();
first.set(5, 10);
first.xor(second);
for (int i = 5; i < 7; i++) {
assertThat(first.get(i)).isTrue();
}
for (int i = 10; i < 15; i++) {
assertThat(first.get(i)).isTrue();
}
Существуют и другие методы, такие как andNot(BitSet) или or(BitSet) , ` которые могут выполнять другие логические операции над двумя BitSet` .
4.8. Разнообразный
Начиная с Java 8, существует метод stream() для потоковой передачи всех установленных битов BitSet . Например:
BitSet bitSet = new BitSet();
bitSet.set(15, 25);
bitSet.stream().forEach(System.out::println);
Это выведет все установленные биты на консоль. Поскольку это вернет IntStream , мы можем выполнять обычные числовые операции, такие как суммирование, среднее значение, подсчет и т. д. Например, здесь мы подсчитываем количество установленных битов:
assertThat(bitSet.stream().count()).isEqualTo(10);
Кроме того, метод nextSetBit(fromIndex) вернет следующий установленный битовый индекс, начиная с fromIndex :
assertThat(bitSet.nextSetBit(13)).isEqualTo(15);
Сам fromIndex включен в этот расчет. Когда в BitSet не осталось истинного бита , он вернет -1: ``
assertThat(bitSet.nextSetBit(25)).isEqualTo(-1);
Точно так же nextClearBit (fromIndex) возвращает следующий чистый индекс, начиная с fromIndex :
assertThat(bitSet.nextClearBit(23)).isEqualTo(25);
С другой стороны, previousClearBit(fromIndex) возвращает индекс ближайшего чистого индекса в противоположном направлении:
assertThat(bitSet.previousClearBit(24)).isEqualTo(14);
То же самое верно и для previousSetBit(fromIndex) : ``
assertThat(bitSet.previousSetBit(29)).isEqualTo(24);
assertThat(bitSet.previousSetBit(14)).isEqualTo(-1);
Более того, мы можем преобразовать BitSet в byte[] или long[] , используя методы toByteArray() или toLongArray() соответственно:
byte[] bytes = bitSet.toByteArray();
long[] longs = bitSet.toLongArray();
5. Вывод
В этом руководстве мы увидели, как мы можем использовать BitSet для представления вектора битов.
Сначала мы познакомились с обоснованием отказа от использования boolean[] для представления вектора битов. Затем мы увидели, как BitSet работает внутри и как выглядит его API.
Как обычно, все примеры доступны на GitHub .