Лучшая структура данных для хранения лотов однобитных данных

Question

Я хочу хранить много данных, чтобы

1. они могут быть доступны по индексу,
2. каждый данные просто да и нет (так что, вероятно, для каждого достаточно одного бита)

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

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

У кого-нибудь есть идея?

Answer 1

Что не так с использованием одного блока памяти и хранением 1 бита на байт (простое индексирование, но тратит 7 бит на байт) или упаковкой данных ( немного более сложное индексирование, но более эффективное использование памяти)

Answer 2

Ну, в Java BitSet может быть хорошим выбором http://download.oracle.com/javase/6/docs/api/java/util/BitSet.html

Answer 3

Посмотрите на фильтр Блума: http://en.wikipedia.org/wiki/Bloom_filter

Очень хорошо работает и экономит место. Но обязательно прочитайте мелкий шрифт ниже ;-): Цитата с вышеупомянутой вики-страницы.

Пустой фильтр Блума - это битовый массив из m битов, все установлены в 0. Там должны также будет к различным хеш-функциям определены, каждая из которых отображает или хеширует некоторый элемент набора к одному из массива м позиции с равномерным случайным распределение. Чтобы добавить элемент, канал это к каждой из k хеш-функций для получить k позиций массива. Установите биты в все эти позиции до 1. Для запроса элемент (проверить, находится ли он в установить), передать его каждому хешу функции для получения k позиций массива. Если любой из битов в этих позициях 0, элемент отсутствует в наборе - если было бы, тогда все биты были бы был установлен в 1, когда он был вставлен. Если все 1, тогда либо элемент в наборе, или биты были установлены до 1 во время вставки другого элементы. Требование проектирования k различных независимых хеш-функций может быть слишком большим для больших k. Для хорошая хеш-функция с широким выходом, там должно быть мало, если таковые имеются корреляция между разными битовые поля такого хэша, так что это тип хеша может быть использован для генерации несколько "разных" хеш-функций нарезать свой вывод на несколько бит поля. Кроме того, можно передать к разные начальные значения (например, 0, 1, ..., k - 1) к хеш-функции, которая принимает начальное значение; или добавить (или добавить) эти значения к ключу. За больше м и / или к, независимость среди хэш-функции могут быть ослаблены с незначительное увеличение ложных срабатываний ставка (Dillinger & Manolios (2004a), Кирш и Митценмахер (2006). В частности, Диллинджер и Манолиос (2004b) показать эффективность используя улучшенное двойное хеширование или тройное хеширование, варианты двойного хеширование, для получения индексов k, используя простая арифметика на два или три индексы вычисляются с независимым хешем функции. Удаление элемента из этот простой фильтр Блума невозможно. Элемент отображается на k биты, и хотя установка любого из этих k бит до нуля достаточно для удалить его, это имеет побочный эффект удаление любых других элементов, которые отображаются на этот бит, и у нас нет никакого способа определить, есть ли такие элементы были добавлены. Такое удаление будет ввести возможность для ложного негативы, которые не допускаются. Однократное удаление элемента из Фильтр Блума может быть смоделирован имея второй фильтр Блума, который содержит элементы, которые были удалены Тем не менее, ложные срабатывания во втором фильтр становятся ложными негативами в составной фильтр, который не разрешенный. В этом подходе повторное добавление ранее удаленный элемент не возможно, так как придется удалить это из "убранного" фильтра. Тем не мение, часто бывает так, что все ключи доступны, но дороги перечислять (например, требуя много диск читает). Когда ложный положительный скорость становится слишком высокой, фильтр может быть регенерируется; это должно быть относительно редкое событие.

Answer 4

Зависит от языка и от того, как вы определяете «индекс». Если вы имеете в виду, что оператор индекса должен работать, то ваш язык должен быть в состоянии перегрузить оператор индекса. Если вы не возражаете против использования макроса или функции индекса, вы можете получить доступ к n-му элементу, разделив данный индекс на количество битов в вашем типе (скажем, 8 для символа, 32 для uint32_t и вариантов), а затем верните результат arr[n / n_bits] & (1 << (n % n_bits))

Answer 5

Если я правильно понимаю ваш вопрос, вы должны хранить их в целом числе без знака, где вы присваиваете каждое значение биту целого числа (флага).

Допустим, вы представляете 3 значения, и они могут быть включены или выключены.,Затем вы присваиваете первое значение 1, второе - 2, а третье - 4. Тогда ваш unsigned int может быть 0,1,2,3,4,5,6 или 7 в зависимости от того, какие значения включены или выключены, и вы проверяетезначения с использованием побитового сравнения.