Использование Hash Maps для представления чрезвычайно большого источника данных

Question

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

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

У меня есть 1: 1 сопоставление идентификаторов данных (строки из 9 символов) с текущими идентификаторами (длинные целые числа). Проблема в том, что идентификаторов много, а поступающие данные не в определенном порядке.

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

У кого-нибудь есть какие-либо предложения и / или алгоритмы хеширования, которые я могу использовать для этого?

Answer 1

Если вы имеете дело только с сотнями тысяч точек данных, то, скорее всего, не составит труда пойти по наивному пути и просто придерживаться хэш-карты.

Даже если у вас есть 500 000 9-символьных строк и равное количество long с, это по-прежнему только 16 байт на элемент, или всего 8 000 000 байт. Даже если вы удвоите это из-за накладных расходов, 16 МБ вряд ли будет слишком большим, чтобы иметь в памяти одновременно.

По сути, сначала попробуйте легкий путь, и беспокойтесь об этом только тогда, когда ваше профилирование говорит вам, что это занимает слишком много времени.

Answer 2

Поскольку комментарии к вопросу указывают на то, что основной проблемой может быть использование памяти:

• Использовать пул или другой оптимизатор для небольших объектов ; предполагая, что у вас есть доступ к boost , вы, вероятно, найдете замену в Pool . Использование лучшего распределителя мелких объектов - это, вероятно, самый большой выигрыш памяти, который вы найдете.
• Если вы знаете, что ваши строки имеют фиксированную ширину, вы можете убедиться, что вы выделяете только достаточно места для их хранения. Например, структура, обернутая вокруг char [] фиксированной длины с пользовательским оператором сравнения, может работать лучше, чем std :: string. std :: string поставляется с дополнительным динамическим распределением (и использует пространство для соответствующего указателя) и дополнительными издержками на отслеживание размера и емкости. (Как правило, попробуйте уменьшить количество распределений , которые задерживаются; это уменьшает накладные расходы.)
• (Предполагая STL) Посмотрите на служебную разницу между std :: map и std :: unordered_map (последняя может или не может быть доступна вам в данный момент); основанный на RBtree std :: map может быть достаточно близок к характеристикам производительности поиска вашего "hashmap" и может (или может не быть) эффективнее использовать память в зависимости от реализации вашей стандартной библиотеки.

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

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

Answer 3

Массивы Джуди предназначены для такого рода вещей: «Ключевые преимущества Джуди - это масштабируемость, высокая производительность и эффективность памяти. [...] Джуди может заменить многие общие структуры данных, такие как массивы, разреженные массивы, хеш-таблицы, B-деревья, двоичные деревья, линейные списки, скиплисты, другие алгоритмы сортировки и поиска и функции подсчета. "

Answer 4

Несмотря на то, что 166 тыс. Записей данных довольно малы, вы можете взглянуть на google-sparsehash

Answer 5

Поскольку ваши строки известны заранее и имеют фиксированную длину, теоретически и практически наилучшим решением является хэш perfect . Вы можете использовать cmph для его генерации.

Согласно Википедии, ваши ключи должны занимать 2,5 бита / ключ или около 50 КБ. Это незначительно по сравнению с 664 КБ для значений.