Вставка в unordered_map занимает слишком много времени

Question

Я написал программу, которая считывает числа из файла (около 500 000 из них) и вставляет их в структуру данных. числа различны. Я вставив цифры к unordered_map с другой структурой (с использованием std::make_pair(myNumber, emptyStruct)).

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

После профилирования я заметил, что операция вставки занимает около 50% времени выполнения. (Существует также и другой код, который выполняется столько же раз, сколько и вставка, но он не работает,

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

Насколько мне известно, эти DS должны быть вставкой и поиском O (1), а торговля - большой памятью, поэтому я не понимаю, почему требуется столько времени на вставку. Как я могу улучшить свои результаты?

Answer 1

Поскольку вы специально не используете значение и просто ищете существование, перейдите к std :: unordered_set. Он делает то, что вы хотели, когда вы делали фиктивное значение для каждого ключа на карте.

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

Все, что сказал, я был в состоянии получить некоторое улучшение по сравнению с введением 500000 элементов в тестовом приложении, принимая во внимание характер хэш-таблиц:

Рецензирование http://en.cppreference.com/w/cpp/container/unordered_map, я нашел эти:

[Вставка] Сложность: Средний случай: O (1), в худшем случае O (размер())

По умолчанию unordered_map контейнеры имеют max_load_factor 1,0.

Когда вы зарезервируете место на 500000 единиц, вы получите 500000 ковшей. Если вы поместите 500000 единиц данных в 500000 ведер, вы получите много столкновений. Я зарезервировал дополнительное пространство, и это было быстрее.

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

Answer 2

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

Это означает, что вы могли бы побрить некоторое время, но это будет только незначительно. Например, вставка в вектор немного быстрее, но это также амортизированное постоянное время. Таким образом, вы будете бреять несколько секунд при вставке за счет поиска.

Здесь база данных помогает. Скажем, у вас есть данные в базе данных sqlite. Вы создаете базу данных, создаете таблицу со значением поиска в качестве ее первичного ключа, а значение данных в качестве другого атрибута вставляете значения в таблицу один раз. Теперь программа просто запускает и запрашивает базу данных. Он читает только минимальный размер. В этом случае база данных sqlite выполняет роль неупорядоченной карты, которую вы используете.