Я работаю над приложением с низкой задержкой, которое должно быть высокоэффективным все время.
Мне нужно найти какой-то индекс, основанный на строке, поэтому я использую 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, чтобы избежать динамического выделения при вставке?
Давайте попробуем ответить на некоторые из этих вопросов с помощью кода. Я не вставляю все это, так как это немного долго. Пожалуйста, найдите весь код Вот. Я вставляю часть вывода здесь, хотя:
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
reserve
по пути примерно 15 перераспределений, но полученная карта имеет меньше сегментов.reserve
перераспределений нет вообще.Других решений пока нет …