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

Question

У меня есть x (миллионы) целых положительных чисел, где их значения могут быть максимально большими (+2 147 483 647).Предполагая, что они уникальны, что является лучшим способом сохранить их для интенсивной программы поиска.

До сих пор я думал об использовании двоичного дерева AVL или хеш-таблицы, где целое число - это ключ к отображаемым данным (имя).Однако я не уверен, смогу ли я реализовать такие большие ключи и в таком большом количестве с помощью хеш-таблицы (разве это не создало бы коэффициент нагрузки> 0,8 в дополнение к склонности к конфликтам?)некоторые советуют, какая структура данных может подойти для моей ситуации

Answer 1

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

Best - это, вероятно, хеш-таблица с пакетами.Помещая коллизии хешей в сегменты и сохраняя в массиве отдельные массивы для ключей и значений, вы можете уменьшить размер таблицы и воспользоваться преимуществами ускорения кэша ЦП при поиске в сегменте.Линейный поиск в сегменте может даже закончиться быстрее, чем двоичный поиск!

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

Answer 2

Битовый вектор, с индексом, установленным, если число присутствует. Вы можете настроить его, чтобы количество появлений каждого числа. В Bentley's Programming Pearls есть хорошая колонка о битовых векторах.

Answer 3

Вы смотрели в B-деревья?Эффективность колеблется между log_m(n) и log_(m/2)(n), поэтому, если вы выберете m около 8-10 или около того, вы сможете сохранить глубину поиска ниже 10.

Answer 4

Если память не проблема, карта, вероятно, является лучшим выбором.Карты имеют значение O (1), что означает, что при увеличении количества элементов, которые нужно найти, требуется время, чтобы найти одно и то же значение.

Карта, где ключом является int, а значениеэто имя.

Answer 5

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

Если вам нужно хранить только 32-разрядные целые числа, а не какую-либо связанную запись, используйте set, а не map, как hash_set в большинстве библиотек C ++. Он будет использовать только 4-байтовые записи плюс некоторые постоянные накладные расходы и небольшой провал, чтобы избежать 100%. В худшем случае для обработки «миллионов» чисел потребуется несколько десятков мегабайт. Большой, но ничего неуправляемого.

Если вам нужно, чтобы он был намного теснее, просто сохраните их отсортированными в простом массиве и используйте двоичный поиск для их извлечения. Это будет O (log n) вместо O (1), но для «миллионов» записей это всего лишь два шага, чтобы получить любую из них. В C у вас есть bsearch(), что так быстро, как может.

edit : только что увидел в своем вопросе, что вы говорите о каких-то «отображенных данных (имя)». эти имена уникальны? они тоже должны быть в памяти? если да, они определенно будут доминировать над требованиями к памяти. Тем не менее, если имена являются типичными английскими словами, большинство из них будет 10 байтов или меньше, сохраняя общий размер в «десятках мегабайт»; может быть, до ста мегабайт, все еще очень управляемым.