Вставка занимает долгое долгое время в Unordered_map (C++) с ULONG как ключ и неизвестный счет ведра

Question

У меня есть unordered_map с ключом как ULONG.

Я знаю, что может быть огромное количество записей, но не уверены, сколько. Таким образом, нельзя указывать количество ведра перед рукой. Я ожидал, что временная сложность для вставок будет O (1), поскольку ключи уникальны. Но похоже, что вставки занимают очень много времени.

Я читал, что это возможно, если было много повторного хэширования, так как количество ведра неуказано, которое принимает неопределенное время.

Есть ли что-нибудь, что я могу сделать, чтобы улучшить временную сложность вставки здесь. Или я чего-то не хватает?

Answer 1

Между max_load_factor и упреждающим вызовом reserve вы должны иметь возможность как свести к минимуму перезагрузку, так и минимизировать столкновения ковша. Правильный баланс - это, в основном, вопрос тестирования производительности.

Answer 2

Пара вещей, которые могли бы помочь:

1. Вы можете фактически вычислить, когда пересказ будет иметь место и работать, если это вопрос. От cplusplus.com:

«перепев принудительно, если новый размер контейнера после операции вставки приведет к увеличению выше его порога мощности (в пересчете на bucket_count контейнера, умноженная на его max_load_factor).»

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

Answer 3

Для начала многие стандартные хеш-реализации стандартной библиотеки с функцией идентификации, то есть hash(x) == x. Обычно это нормально, особенно если реализация гарантирует, что подсчет ведра является простым (например, GCC), но в некоторых реализациях используются значения мощности из двух ведро (например, Visual C++). Вы можете запустить некоторые цифры через вашу хеш-функцию и посмотреть, является ли она функцией идентификации: если да, подумайте, достаточно ли ваши входы случайным образом, чтобы это не имело значения. Например, если ваши номера все кратные 4, то подсчет количества секунд из двух единиц означает, что вы используете только четверть ваших ковшей. Если они имеют тенденцию отличаться большей частью в старших битах, это также является проблемой, потому что побитовое-И с количеством из двух ведро ковша эффективно выбрасывает некоторое количество бит старшего порядка (например, с 1024 ведрами только 10 наименее значимых бит хэш-значения повлияет на выбор ковша).

Хороший способ проверить, для этого типа проблемы перебрать ваших ведер и создать гистограмму числа сталкивающихся элементов, например - с учетом unordered_mapm:

std::map<int, int> histogram; 
for (size_t i = 0; i < m.bucket_count(); ++i) 
    ++histogram[m.bucket_size(i)]; 
for (auto& kv : histogram) 
    std::cout << ".bucket_size() " << kv.first << " seen " 
       << kv.second << " times\n"; 

(Вы можете увидеть такие код запуска here).

Вы ожидаете, что частота больших значений bucket_size() быстро проскользнет: если нет, работайте с хэш-функцией.

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

Переключение к закрытому адресации/открытой хеширования реализации хэш-таблицы (вы могли бы Google для одного), весьма вероятно, будет значительно быстрее, если у вас нет много «маслобойки»: удаление хеш-таблицы элементов почти в так же, как вы вставляете новые, с чередованием запросов. Закрытая адресация означает, что ключи хеш-таблицы хранятся непосредственно в ведрах, и вы получаете гораздо лучшие хиты кеша и намного быстрее перезаписываете по мере увеличения размера таблицы. Если значения, которыми располагаются ваши целые ключи, являются большими (с учетом размера памяти, как и в sizeof(My_Map::value_type)), то убедитесь, что в нем хранятся только указатели на реализацию в самой таблице, поэтому во время изменения размера не нужно копировать все объекты.

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