std :: unordered_map, как оптимизировать массовую вставку, если известен размер ввода

Question

Если я знаю, что собираюсь вставить большой объем данных (около миллиона записей) в std::unordered_map, могу ли я что-нибудь сделать заранее, чтобы повысить производительность? (точно так же, как std::vector::reserve может зарезервировать достаточно места в памяти, чтобы избежать перераспределения, когда я примерно знаю размер данных перед массовой вставкой)

Точнее говоря, ключ в hashmap - это координата в 2D-плоскости с настроенным ha sh функция, как показано ниже

using CellIndex = std::pair<int32_t, int32_t>;

struct IdxHash {
  std::size_t operator()(const std::pair<int32_t, int32_t> &idx) const { return ((size_t)idx.second << 31) ^ idx.first; }
};

std::unordered_map<CellIndex, double, IdxHash> my_map;

// bluk insert into my_map
...

Answer 1

std::unordered_map обычно реализуется в виде таблицы ha sh со связанными списками . Таким образом, вставка в std::unordered_map занимает в среднем постоянное время и линейное время в размере контейнера в худшем случае. Этот сценарий наихудшего случая для вставки соответствует случаю, когда элементы таблицы ha sh должны быть перефразированы , поскольку текущее количество сегментов в таблице недостаточно для удовлетворения коэффициента загрузки , и, следовательно, необходимо перераспределение массива сегментов.

Имея это в виду, если вы заранее знаете количество элементов, которые нужно вставить в std::unordered_map, вам следует подумать о std::unordered_map::reserve(), чтобы предотвратить повторное перемешивание при вставке. Таким образом, вы избежите как перераспределения массива сегментов, так и перефразирования.

std::unordered_map::insert() с подсказкой

Как и с std::map есть некоторые перегрузки функции-члена insert(), которые принимают так называемую подсказку :

iterator insert(const_iterator hint, const value_type& value);

Этот итератор подсказки может использоваться для дополнительная информация, которая может быть использована для ускорения вставки. Тем не менее, наличие этих функций-членов в std::unordered_map подсказке только для совместимости интерфейса, чтобы сделать его интерфейс более подходящим для общего c программирования. Таким образом, они не улучшают время вставки.

О функции ha sh

Насколько совершенной является ваша функция ha sh, не должно иметь большого значения, когда дело доходит до времени вставки - только как быстро он вычисляет га sh ключа. Однако это становится актуальным при поиске элементов в таблице ha sh по их ключам.

Answer 2

reserve(x) готовит неупорядоченный контейнер для x количества элементов. Для сравнения rehash(x) готовит неупорядоченный контейнер для x/max_load_factor() количества элементов.

Также касается вашей функции ha sh, если вы хотите, чтобы она возвращала уникальное значение для пары координат, тогда он должен вернуть ((size_t)idx.second << 32) ^ idx.first. ((size_t)idx.second << 31) ^ idx.first вернет одинаковое значение для (1, -1) и (0, 2^31-1).