Компактная структура данных для хранения большого набора интегральных значений

Question

Я работаю над приложением, которое должно передавать большие наборы значений Int32.Ожидается, что наборы будут содержать ~1,000,000-50,000,000 элементов, где каждый элемент является ключом базы данных в диапазоне 0-50,000,000.Я ожидаю, что распределение идентификаторов в любом данном наборе будет эффективно случайным в этом диапазоне.Операции, которые мне нужны на съемочной площадке, очень просты:

• Добавить новое значение
• Итерация по всем значениям.

СерьезныйОбеспокоенность по поводу использования памяти этими наборами, поэтому я ищу структуру данных, которая может хранить идентификаторы более эффективно, чем простые List<int> или HashSet<int>.Я посмотрел на BitArray, но это может быть расточительным в зависимости от того, насколько редкими являются идентификаторы.Я также рассмотрел побитовую trie, но я не уверен, как рассчитать эффективность использования пространства этим решением для ожидаемых данных.Фильтр Блума был бы хорош, если бы я мог терпеть ложные негативы.

Буду признателен за любые предложения структур данных, подходящих для этой цели.Меня интересуют как готовые, так и нестандартные решения.

РЕДАКТИРОВАТЬ : Чтобы ответить на ваши вопросы:

• Нет, элементы неНе нужно сортировать
• Под "обходом" я подразумеваю, что оба метода между сериалами и проходят сериализацию и отправку по проводам.Я явно должен был упомянуть об этом.
• В памяти может быть приличное количество этих наборов одновременно (~ 100).

Answer 1

Используйте BitArray. Он использует только около 6 МБ памяти; единственная реальная проблема заключается в том, что итерация - это тэта ( N ), т. е. вы должны пройти весь диапазон. Справочная информация хороша, и вы можете выделить всю структуру за одну операцию.

Что касается траты пространства: в худшем случае вы тратите 6 МБ.

РЕДАКТИРОВАТЬ : хорошо, у вас много наборов, и вы сериализуете. Для сериализации на диске я предлагаю 6 МБ файлов:)

Для отправки по проводам просто выполните итерацию и рассмотрите отправку диапазонов вместо отдельных элементов. Для этого требуется структура сортировки.

Вам нужно много этих наборов. Рассмотрим, если у вас есть 600 МБ, чтобы сэкономить. В противном случае проверьте:

• Побайтные попытки: O (1) вставка, O ( n ) итерация, намного более низкие постоянные коэффициенты, чем битовые попытки
• Настраиваемая хеш-таблица, возможно Google sparsehash через C ++ / CLI
• диапазоны / интервалы хранения BST
• Supernode BSTs

Answer 2

Это будет зависеть от распределения размеров ваших наборов.Если только вы не ожидаете, что большинство наборов будет (близко к) указанному вами минимуму, я бы, вероятно, использовал битовый набор.Чтобы охватить диапазон до 50 000 000, битовый набор заканчивается ~ 6 мегабайтами.

По сравнению с непосредственным хранением чисел это незначительно больше для указанного вами минимального размера (~ 6 мегабайт вместо ~ 4), но значительно меньше для максимального установленного размера (1/32 ^и размер).

Вторая возможность - использование дельта-кодирования.Например, вместо того, чтобы хранить каждый номер напрямую, сохраните разницу между этим номером и предыдущим номером, который был включен.Учитывая максимальную величину 50 000 000 и минимальный размер 1 000 000 единиц, средняя разница между одним числом и следующим составляет ~ 50.Это означает, что теоретически вы можете хранить разницу в <6 бит в среднем.Вероятно, я бы использовал 7 младших значащих битов напрямую, и если вам нужно кодировать больший разрыв, установите msb и (например) сохраните размер промежутка в младших 7 битах плюс следующие три байта.Этого не может случиться <em>очень часто, поэтому в большинстве случаев вы используете только один байт на число для сжатия примерно 4: 1 по сравнению с непосредственным сохранением чисел.В лучшем случае это будет использовать ~ 1 мегабайт для набора, а в худшем - около 50 мегабайт - сжатие 4: 1 по сравнению с непосредственным хранением чисел.

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

Answer 3

Я думаю, что ответ зависит от того, что вы имеете в виду, говоря «прохождение» и чего вы пытаетесь достичь. Вы говорите, что только добавляете в список: как часто вы добавляете? Как быстро будет расти список? Каковы допустимые накладные расходы на использование памяти по сравнению со временем на перераспределение памяти?

В вашем худшем случае 50 000 000 32-разрядных чисел = 200 мегабайт с использованием наиболее эффективного механизма хранения данных. Предполагая, что вы можете в конечном итоге использовать это в худшем случае, нормально ли использовать такое количество памяти все время? Это лучше, чем часто перераспределять память? Как распределяются типичные модели использования? Вы всегда можете просто использовать int[], который предварительно выделен на все 50 миллионов.

Что касается скорости доступа к вашим операциям, нет ничего быстрее, чем итерация и добавление к заранее выделенному фрагменту памяти.

Из OP edit: В памяти может быть приличное количество этих наборов одновременно (~ 100).

Привет. Вам нужно хранить 100 наборов от 1 до 50 миллионов номеров одновременно? Я думаю, что метод bitset - единственный возможный способ, которым это могло бы работать.

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

Теперь, если вы не используете наборы битов, а используете конструкции с динамическим размером, и они могут как-то занимать меньше места для начала, вы говорите о сценарии реального уродливого выделения / освобождения памяти / сборки мусора. 1018 *

Предположим, вам действительно нужно это сделать, хотя я могу только представить, почему. Итак, у вашего сервера есть тонна памяти, просто выделите столько этих 6-мегабайтных битовых наборов, сколько вам нужно, и переработайте их. Распределение и сборка мусора больше не являются проблемой. Да, вы используете тонну памяти, но это кажется неизбежным.