эффективно инициализировать unordered_map с большим набором целочисленных пар

Question

эффективно инициализировать unordered_map с большим набором целочисленных пар

У меня есть огромный массив (скажем, ParticleId[]) из уникальный целые числа (представляющие идентификаторы частиц) хранятся в случайном порядке в памяти. Мне нужно создать хеш-таблицу, чтобы сопоставить каждый идентификатор с его местоположением внутри массива, то есть с идентификатором в индекс. Идентификаторы не обязательно являются непрерывными целыми числами, поэтому простой поисковый массив не является хорошим решением.

Я в настоящее время использую unordered_map контейнер с ++ 11 для достижения этой цели. Карта инициализируется циклом:

unordered_map <ParticleId_t, ParticleIndex_t> ParticleHash;
ParticleHash.rehash(NumberOfParticles);
ParticleHash.reserve(NumberOfParticles);
for(ParticleIndex_t i=0;i<NumberOfParticles;i++)
ParticleHash[ParticleId[i]]=i;

ParticleId_t а также ParticleIndex_t являются просто целочисленными типами.
NumberOfParticles может быть огромным (например, 1e9). ParticleId[] массив и NumberOfParticles являются const что касается хеш-таблицы.

В настоящее время на создание unordered_map как указано выше. Мои вопросы:

Является unordered_map оптимальный выбор для этой проблемы?
- было бы map Быстрее инициализировать, хотя это может быть не так эффективно при поиске?
Можно ли ускорить инициализацию?
- Это намного быстрее, чтобы использовать ParticleHash.insert() чем ParticleHash[]=? или любые другие функции?
- Учитывая, что мои ключи, как известно, уникальный целые числа, есть ли способ оптимизировать карту, а также вставку?

Я рассматриваю информацию concurrent_unordered_map распараллелить это. Однако это привело бы к зависимости от библиотеки intel TBB, которой я бы хотел избежать, если это возможно. Есть ли простое решение с использованием собственных контейнеров STL?

Обновить:

Теперь я вернулся к простой отсортированной индексной таблице и полагаюсь на bsearch для поиска. По крайней мере, инициализация таблицы теперь в 20 раз быстрее и может быть легко распараллелена.

1

c++hashmap performance scientific-computing unordered-map

Решение

Другие решения

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

Во-первых, так как вы звоните realloc тебе не нужно звонить rehash,

insert потенциально быстрее, чем operator[] поскольку operator[] позвоню insert добавить элемент на карту со значением по умолчанию, а затем назначить свое значение новому вставленному элементу, но оптимизатор может устранить лишнюю работу.

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

‘map’, вероятно, будет медленнее инициализироваться, так как она будет продолжать балансировать дерево, когда вы вставляете вещи, и поиск будет медленнее. Одна альтернатива map Вы могли бы использовать, если ваш ParticleID вектор может быть переставлен будет сортировать ваш вектор, а затем сделать binary_search чтобы найти, где находится идентификатор и рассчитать индекс. Но это будет иметь аналогичную производительность map и требуют перестановки вектора.

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

1

Учитывая «огромный массив уникальных целых чисел, хранящихся в случайном порядке» — есть ли что-нибудь уже зависящее от этого случайного порядка? Если нет, просто отсортируйте массив уникальных целых чисел на месте, и чтобы отобразить уникальное целое число в индекс, выполните std::lower_bound в массиве.

Если необходимо сохранить предварительный порядок огромного массива, но вы строите индекс как единичный шаг после заполнения этого массива (как это делает ваш иллюстративный код), вы можете создать такой же огромный массив из ParticleId* а также std::sort они основаны на указанных элементах (вам понадобится < сравнение указанных значений); после этого вы можете использовать std::lower_bound с тем же < Сравнение, чтобы быстро найти индекс в огромном массиве конкретного ParticleId,

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

Только если у вас есть большое количество новых ParticleIdвходящие или удаляемые в то время, когда вам нужно иметь возможность искать, нужно ли вам рассмотреть std::unordered_map,

0

Источник

Accepted Answer

Кажется, что приложение, создающее таблицу поиска, связано с памятью, а не с процессором. Вероятно, это можно проверить, профилировав прототип приложения. Остальная часть этого ответа предполагает, что это правда.

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

Если это так, решение представляет собой альтернативный алгоритм, который обрабатывает меньшие порции памяти одновременно.
Предположим, есть 1 миллион целых чисел. Текущий процесс может быть вставлен в нижний конец хэш-таблицы ближе к 1 в этот момент, а в следующий момент он может быть вставлен в верхний конец ближе к 1 миллиону. Это приводит к большому обмену.

Альтернативный подход позволил бы избежать обмена, имея дело с меньшими порциями набора данных за раз. Мы могли бы позаимствовать идеи из сортировки ведро / основание. При таком подходе этап создания справочной таблицы будет заменен этапом сортировки. Сортировка Bucket / Radix должна выполняться за линейное время. Тот факт, что все целые числа в наборе данных являются уникальными, является еще одной причиной для использования этих алгоритмов сортировки.
Если линейная сортировка по времени и сведение к минимуму могут быть объединены, это может улучшить производительность.

2