Есть ли способ итерации над (возможно огромным) std::bitset, который является линейным по числу бит, которые установлены в true? Я хочу запретить проверять каждую позицию в битете. Итерация должна последовательно возвращать индексы каждого бита, для которых установлено значение true.
Эффективный способ итерации по истинным битам в std:: bitset?
Ответ 1
Стандартный битвектор не поддерживает эффективную итерацию по истинным битам - время выполнения всегда равно O (n), где n - количество полных битов, которое не зависит от k. Однако специальная структура, называемая van Emde Boas Tree, поддерживает итерацию по битам во времени O (k lg lg n), где n - число бит и k - количество истинных битов.
Как немного бесстыдного самопродвижения, я реализация vEB-дерева на моем личном веб-сайте. Если мне неуместно рекламировать это здесь, пожалуйста, дайте мне знать, и я сниму его.
Ответ 2
Для того, чтобы быть линейным, вам понадобится связанный список/массив/набор индексов, установленный true. Хранение такого вторичного индекса не является частью компромиссов производительности/хранения, требуемых std:: bitset, и, учитывая, что это будет ущемлять всех без вашего конкретного требования, не может быть реализована реализация. Вы можете подумать о дополнении своего битового набора таким контейнером самостоятельно или использовать расширенную библиотеку контейнеров с несколькими индексами.
Ответ 3
Вы можете проверить до 32 бит за раз с аккумулятором u64 и таблицей с 32 входами, например
u32 kTable[]
{
0x01, 0x03, 0x07, 0x0F ..., 0xFFFFFFFF
};
Просто прочитайте 32 бита в аккумулятор u64 и сдвиньте его вниз в зависимости от смещения и проверьте свои биты на таблицу. Вы можете сделать это бинарным способом, чтобы число сравнения было равным max 5. Это будет медленнее для данных, которые не являются "линейными" в моде. Затем это время журнала.
Ответ 4
Есть только два варианта, которые намного лучше, чем O (N) для всех бит:
- Использование специальных инструкций бит-сканирования, доступных в некоторых архитектурах, таких как BSF в x86.
- Существуют алгоритмы O (log2 (N)) для нахождения младшего бита, установленного в слове. Это, конечно, плохо масштабируется, когда битсет плотный, а не разреженный. Воскрешая какую-то туманную память, я нашел источник в библиотеке FXT. Подробности можно найти в книга FXT (pdf), в разделе 1.3.2.
Ответ 5
Зацикливание по всему битрейту и просто проверка значения и сохранение индекса, если true, IS linear. Вы можете ускорить это, хотя с помощью таблицы поиска. Смотрите этот код:
Ответ 6
Иногда люди используют кодировку длины пробега для таких вещей. Если вы кодируете входящий бит в массив длин выполнения, количество запусков, в результате которых вы закончите, не будет превышать количество переходов между установленными и чистыми битами, которое не более 2*k. Кроме того, во многих приложениях количество переходов намного меньше, чем k, поэтому вы получите отличную среднюю производительность по времени в дополнение к линейному наихудшему варианту.
Кроме того, просто добавить структуру данных, которая позволит вам эффективно искать такие вещи, как "следующий бит набора, начинающийся с n -й позиции в массиве": просто создайте сканировать длины выполнения.