Существует несколько реализаций сжатых битовых векторов.Обычно они содержат кодировку длины серии вместе с операциями и / или / xor / not, которые работают в сжатой форме.
Таким образом, преимущества заключаются в следующем:
- меньшее использование пространства (для разреженныхбитовые наборы, как в вашем случае использования)
- очень быстрые битовые операции (потому что они работают со словами и намного более дружественны к кэш-памяти процессора)
и ниже:
- более медленный доступ к битам (требуется итерация, чтобы найти бит в определенной позиции)
Некоторые реализации, о которых я знаю (есть и другие, я уверен):
Fastbit Фактически это база данных, использующая индекс битового вектора.Сжатый класс битового вектора можно использовать напрямую (без индексации)
Lemur bitmapindex Еще одна реализация кодирования EWAH, представленная Fastbit
Сжатый битовый вектор от koen.vandamme Никогда не пробовал ... только два заголовка и файл cpp.Поэтому не нужно много усилий, чтобы попробовать.
Bitmagic Полноценный пакет, реализующий несколько сжатых битовых векторов, включая аппаратную поддержку (sse2, ...)
Hopeэто помогает,
Роланд