некоторые вопросы по хэш-таблице / неупорядоченной карте

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

Мне нужно найти какой-то индекс, основанный на строке, поэтому я использую c ++ unordered_map.
Ограничения:
-Только вставки и поиски, без удалений
ключ — строка, значение — int
Ожидается, что не более 1 миллиона записей будут добавлены в unordered_map

  • Я устанавливаю резерв unordered_map в 1 миллион. Это хорошо, или я должен резервировать на несколько процентов больше ожидаемых записей, чтобы избежать перефразирования?
    Могу ли я установить его в 1 миллион, или я должен установить большое простое число, близкое к 1 миллиону или около 2 степени.

  • Я использую строковую хэш-функцию по умолчанию в c ++ std lib, которая называется murmur2.
    Мои ключи имеют длину от 25 до 50 символов, и все они являются уникальными ключами, содержащими цифры, прописные буквы английского алфавита и символы _. Достаточно ли этой хеш-функции для равномерного распределения ключей или мне нужно предоставить лучшую хеш-функцию для unordered_map?

  • Будет ли unordered_map выделять пространство для 1 миллиона пар ключей, значений, а также для массива размером 1 миллион, когда я вызываю резерв, или в резерве создается только массив такого размера, а пары ключей и значений выделяются динамически при вставке?

  • Сколько сопротивления будет динамическое распределение пар ключ-значение в куче при вставке? Тем более, что это большая хеш-таблица со множеством записей.

  • По соображениям производительности, было бы хорошей идеей реализовать мою собственную хеш-таблицу с памятью, предварительно выделенной для 1 миллиона записей в стеке или во время инициализации, или вышеупомянутые оптимизации unordered_map достаточно близки?

  • Есть ли способ заранее выделить память для ожидаемого количества записей в unorderd_map, чтобы избежать динамического выделения при вставке?

3

Решение

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

Map without reserve

size: 0
bucket_count: 23
load_factor: 0

Allocation count: 0

...
about 15 reallocations deleted
...

Allocation count: 1000015

size: 1000000
bucket_count: 1236397
load_factor: 0.808802

0: 550454
1: 445645
2: 180174
3: 48593
4: 9708
5: 1568
6: 231
7: 22
8: 2

Map with reserve

size: 0
bucket_count: 23
load_factor: 0

Allocation count: 1

size: 0
bucket_count: 2144977
load_factor: 0

Allocation count: 1000000

size: 1000000
bucket_count: 2144977
load_factor: 0.466205

0: 1346008
1: 626748
2: 146625
3: 22663
4: 2669
5: 248
6: 15
7: 1
  • Как видите, когда вы резервируете место для 1 м элементов, происходит только одно выделение. Это для ведер, я думаю.
  • Количество зарезервированных ведер намного больше 1м.
  • Количество выделений точно такое же, как количество вставленных элементов.
  • Распределение хешей вы можете увидеть для каждого случая: здесь довольно много коллизий. Иногда до 8 элементов в каждой корзине, хотя полмиллиона корзин пустые.
  • Без начального reserve по пути примерно 15 перераспределений, но полученная карта имеет меньше сегментов.
  • С достаточно большим reserve перераспределений нет вообще.
  • Конечно, вы можете свернуть свой собственный хэш-стол. Например, вы можете зарезервировать один непрерывный блок пространства для всех ключей, так как они имеют длину не более 50 байтов каждый, и один блок для значений. Но я уверен, что это будет довольно трудоемко, возможно, без хороших выгод. Профилируйте и регистрируйте ваши выделения памяти, прежде чем начинать переопределять то, что может и не быть.
1

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

Других решений пока нет …

По вопросам рекламы [email protected]