Каковы преимущества использования битовых наборов для хранения растровых изображений?
В настоящее время я оцениваю, должен ли я использовать один большой битовый набор или много 64-битных длинных без знака (uint_64) для хранения большого количества битовой информации. В этом случае растровое изображение представляет текущий статус нескольких ГБ страниц памяти (грязный / не грязный) и содержит тысячи записей.
Работа, которую я выполняю, требует, чтобы я мог запрашивать и обновлять грязные страницы, в том числе выполнять операции ИЛИ между двумя грязными растровыми изображениями страниц.
Чтобы было ясно, я буду выполнять следующее:
- Импорт растрового изображения из файла и выполнение побитовой операции ИЛИ с существующим растровым изображением
- Вычисление веса Хэмминга (считая количество битов, равное 1, которое представляет количество грязных страниц)
- Сбросить / очистить немного, чтобы пометить его как обновленный / чистый
- Проверка текущего состояния немного, чтобы определить, если он чистый
Похоже, что легко выполнять побитовые операции над набором битов C ++ и легко вычислить вес Хэмминга. Однако я полагаю, что в этом нет никакой магии — процессор может выполнять побитовые операции только с тем количеством байтов, которое он может хранить в регистре, поэтому процедура, используемая набором битов, вероятно, будет такой же, как и я сам. Это, вероятно, также верно для веса Хэмминга.
Кроме того, импорт данных растрового изображения из файла в набор битов выглядит уродливо — мне нужно выполнять битовые смещения несколько раз, как показано Вот. Я полагаю, учитывая размер наборов битов, с которыми я буду работать, это отрицательно скажется на производительности. Конечно, я полагаю, что вместо этого я мог бы просто использовать множество небольших наборов битов, но это может не дать никаких преимуществ (кроме, возможно, простоты реализации).
Любой совет ценится, как всегда. Спасибо!
Решение
Похоже, у вас есть очень специфическое одноразовое приложение. Лично я никогда не использовал набор битов, но из того, что я могу сказать, его преимущества в том, что он доступен, как если бы он был массивом bools, а также имел возможность динамически расти как вектор.
Из того, что я могу собрать, вам не нужно ни то, ни другое. Если это так, и если заполнение набора битов — это драма, я бы хотел сделать это сам, учитывая, что на самом деле довольно просто выделить целую кучу целых чисел и выполнять над ними битовые операции.
Учитывая, что у них очень специфические требования, вы, вероятно, выиграете от собственных оптимизаций. Для этого крайне важно иметь доступ к необработанным битовым данным (например, использовать предварительно рассчитанные таблицы весов Хэмминга для одного байта или даже два байта, если у вас есть свободная память).
Я обычно не рекомендую заново изобретать колесо … Но если у вас есть особые требования по оптимизации, лучше было бы адаптировать ваше решение к ним. В этом случае реализуемая вами функция довольно проста.
Другие решения
Тысячи бит не звучат так много. Но, возможно, у вас есть миллионы.
Я предлагаю вам написать свой код, как если бы у вас была идеальная реализация, абстрагируя ее (для начала используйте любую реализацию, которую проще кодировать, игнорируя любые проблемы с производительностью и требованиями к памяти), а затем попробуйте несколько альтернативных конкретных реализаций для проверки (путем их измерения) который выполняет лучше всего.
Одним из решений, которое вы даже не рассматривали, является использование массивов Judy (в частности массивов Judy1).
Я думаю, что на вашем месте, я бы просто избавил себя от хлопот любого DIY и использовал повышение :: dynamic_bitset. У них есть все базовые возможности с точки зрения функциональности, включая перегрузки потоковых операторов, которые вы можете использовать для ввода-вывода файлов (или просто читать ваши данные как unsigned intи использовать их преобразования, см. их примеры) и count метод для вашего веса Хэмминга. Повышение очень высоко ценится Саттером & Александреску, и они делают все в заголовочном файле — никаких ссылок, просто #include соответствующие файлы. Кроме того, в отличие от стандартной библиотеки bitsetВы можете подождать до времени выполнения, чтобы указать размер набора битов.
Edit: Boost, кажется, позволяет быстро читать входные данные, которые вам нужны. dynamic_bitset поставляет следующий конструктор:
template <typename BlockInputIterator>
dynamic_bitset(BlockInputIterator first, BlockInputIterator last,
const Allocator& alloc = Allocator());
Базовое хранилище является std::vector (или что-то почти идентичное этому) из Blockнапример, uint64s. Так что если вы читаете в своем растровом изображении как std::vector из uint64s, этот конструктор запишет их непосредственно в память без сдвига битов.