Стоит ли использовать битовый вектор / массив вместо простого массива bools?

Question

Когда мне нужен массив флагов, обычно мне больно использовать целый байт (или слово) для хранения каждого из них, как это было бы в результате, если бы я создал массив bool s или какой-либо другой числовой тип, который может быть установлено в 0 или 1. Но теперь мне интересно, стоит ли использовать более компактную структуру, учитывая (хотя, надеюсь, очень незначительные) дополнительные накладные расходы на сдвиг и битовое тестирование.

В моей компании мы используем инструменты Rogue Wave (хотя, надеюсь, ненадолго), и именно их RWBitVec я использовал для этой цели до сих пор.

Answer 1

В основном речь идет об экономии памяти. Если ваш массив bools достаточно велик, чтобы увеличить объем памяти в 8 раз, тогда обязательно используйте bitarray.

Обратите внимание, что доступ к памяти довольно дорогой по сравнению с shift / и, поэтому подход с битарными массивами немного быстрее, чем с массивом символов. В основном это сводится к памяти против времени программиста. Помните, что преждевременная оптимизация - пустая трата времени. Я бы использовал тот подход, который проще всего разработать, а затем рефакторинг только после того, как он покажет, что это основное узкое место производительности.

Answer 2

Не используйте вектор , на самом деле это не контейнер:

http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=98

Используйте std :: bitset (для битовых наборов фиксированного размера) и boost :: dynamic_bitset (для изменяемых размеров), где это уместно. Они также не являются контейнерами, но выглядят не так, как должны, поэтому с меньшей вероятностью могут вызвать путаницу.

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

Преимущество

битовых наборов состоит в том, что они делают именно то, что говорят на жестяных банках - ни один из них «не объявляет массив символов / целых, но единственными допустимыми значениями являются ноль и ноль». Ваш код будет выглядеть примерно так же, как если бы вы использовали массив.

Answer 3

Я использовал битовый массив для индексации ОГРОМНОГО дерева. Алгоритм был:

    Check bitarray if entry exists
    if entry doesn't exists 
      return null
    else do binary search in tree
      return value

Преимущество состоит в том, что дерево достаточно велико, чтобы поиск несуществующей записи мог привести к нескольким ошибкам кэша перед завершением. Таким образом, алгоритм занимал больше времени или нет в зависимости от наличия значения.

Однако добавление этого начального поиска в битовом массиве означало, что я уменьшил бы ошибки в кеше и вообще избегал бы поиска по дереву, если бы ответа не было. Благодаря добавлению этого дополнительного шага алгоритм стал намного более устойчивым (фактическое время работы на компьютере стало почти линейным, хотя Big-O сказал бы иначе), и общая производительность увеличилась на порядок.

Как говорят, иногда учет аппаратных средств важнее «идеального» математического алгоритма.

Answer 4

Современные компьютеры имеют бочкообразные смены , поэтому сдвиг любого числа битов до 31 занимает несколько циклов (меньше, чем во многих других инструкциях). Компиляторы используют это преимущество, и битовые операции не только экономят место, но и в большинстве случаев экономят время.

Но это действительно зависит от того, как вы используете и тестируете биты - есть некоторые неэффективные методы, которые позволили бы быстрее использовать целое число.

-Adam

Answer 5

Я написал один код, чтобы распаковать строку растрового изображения в отдельные байты на пиксель, а затем упаковать обратно после обработки. Для кода, который я тестировал, на самом деле это было быстрее, чем на битовом уровне.

Answer 6

Стоит ли это того? Только если вы знаете, что у вас есть проблемы с использованием памяти.

Но если вы не либо:

1. Работа на встроенном процессоре с очень ограниченными ресурсами или
2. Хранение астрономического числа bool с

тогда ответ - нет. Вам придется работать несколько усерднее, чтобы достичь того же уровня читаемости в вашем источнике с помощью растрового изображения, чем при использовании bools, и, если вы не используете ни одно из двух предыдущих условий, вы, вероятно, обнаружите, что не имеет никакого значения для вашей памяти.