Эффективный способ перебора истинных битов в std :: bitset?

Question

Есть ли способ итерации по (возможно, огромному) std::bitset, который равен линейному в количестве битов, которые установлены в true ?Я хочу предотвратить проверку каждой позиции в битах.Итерация должна последовательно возвращать индексы каждого бита, который установлен в true.

Answer 1

Стандартный битовый вектор не поддерживает эффективную итерацию по истинным битам - время выполнения всегда равно O (n), где n - это общее количество битов, которое не зависит от k.Однако специальная структура, называемая van Emde Boas Tree , поддерживает итерацию по битам во времени O (k lg lg n), где n - количество битов, а k - количество истинных бит.*

Как бесстыдная самореклама, у меня есть реализация vEB-дерева на моем личном сайте .Если мне неуместно рекламировать это здесь, пожалуйста, дайте мне знать, и я сниму это.

Answer 2

Для того, чтобы это было линейным, вам понадобится связанный список / массив / набор индексов, установленный в true. Сохранение такого вторичного индекса не является частью компромисса между производительностью и хранилищем, требуемого std :: bitset, и, учитывая то, что он поставил бы в невыгодное положение всех без вашего конкретного требования, реализация не сможет это обеспечить. Вы можете сами дополнить свой набор битов таким контейнером или использовать многоиндексную контейнерную библиотеку Boost.

Answer 3

Есть только два варианта, которые работают намного лучше, чем O (N) в общих битах:

1. Использование специальных инструкций по битовому сканированию, доступных в определенных архитектурах, таких как BSF в x86 .
2. Существует O (log2 (N)) алгоритмов для нахождения младшего бита, установленного в слове. Это, конечно, не очень хорошо масштабируется, когда битовый набор плотный, а не разреженный. Воскресив мою туманную память, я нашел источник в библиотеке FXT Подробности можно найти в книге FXT (pdf) , в разделе 1.3.2.

Answer 4

Одновременно можно проверять до 32 бит с аккумулятором u64 и таблицей с 32 записями, например

u32 kTable[]
{
0x01, 0x03, 0x07, 0x0F ..., 0xFFFFFFFF
};

Просто считайте 32 бита в накопитель u64 и сдвиньте его вниз в зависимости от смещения и сравните ваши биты с таблицей. Вы можете сделать это в двоичном режиме, чтобы число сравнений было максимально 5. Это будет медленнее для данных, которые не являются «линейными» в моде. Это становится временем регистрации.

Answer 5

Иногда люди используют кодировку длины прогона для подобных вещей.Если вы закодируете входящий набор битов в массив длин серий, количество выполненных вами циклов не превысит число переходов между установленным и очищенным битами, которое составляет максимум 2*k.Кроме того, во многих приложениях число переходов намного меньше, чем k, поэтому вы получите отличную среднюю производительность по времени в дополнение к линейному худшему.

Кроме того, добавить структуру данных просто.это позволит вам эффективно искать такие вещи, как «следующий установленный бит, начинающийся с n -ой позиции в массиве»: просто создайте сканирование длин серий.

Answer 6

Цикл по всему набору битов и простая проверка значения и сохранение индекса, если оно истинно, является линейным Вы можете ускорить это с помощью справочной таблицы. Смотрите этот код:

* ** 1003 тысяча два *http://xiangqi -engine.cvs.sourceforge.net / ViewVC / сянй двигатель / tsito2 / SRC / Utility.cpp? Пересмотр = 1,5 & вид = разметка