Самый быстрый способ ускорить карту <string, int> .find () в c ++. Где ключи в алфавитном порядке

Question

У меня есть карта с примерно 100 000 пар.Есть ли способ ускорить поиск при использовании find (), учитывая, что ключи расположены в алфавитном порядке.И как мне это сделать?Я знаю, что вы можете указать новый компаратор при создании карты.Но ускорит ли это вообще функцию find ()?

Заранее спасибо.

[решено] Спасибо, ребята, я решил использовать вектор и использовать нижнюю и верхнюю границы для«обрезать» некоторые поиски.

Также я новичок, есть ли способ пометить этот вопрос как ответивший или выбрать лучший ответ?

Answer 1

Другой компаратор ускорит поиск, только если ему удастся выполнить сравнение быстрее (что для строк обычно довольно сложно).

Если вы в основном вставляете все данные по порядку, товыполняя поиск, может быть быстрее использовать std::vector с std::lower_bound или std::upper_bound.

, если вы на самом деле не заботитесь о заказе и просто хотите найти данные как можно быстрееВозможно, вы обнаружите, что std::unordered_map лучше работает для вас.

Редактировать: Просто для записи: способ, которым вы «можете найти» или «можете найти» эти вещи, обычно выполняется с помощью профилирования.В зависимости от ситуации, это может быть достаточно быстрым, что довольно очевидно даже при простом тестировании, поэтому профилирование на самом деле не нужно, но если есть (много) сомнений или вы хотите количественно оценить эффект, профилировщик, вероятно, является правильным способомсделать это.

Answer 2

Если вы используете std::find для поиска элементов, вам следует переключиться на использование map::find (вы на самом деле не говорите об этом.) map::find использует тот факт, что карта упорядочена для поиска намного быстрее .

Если это все еще недостаточно хорошо, вы можете посмотреть в хеш-контейнер, например unordered_map, а не map.

Answer 3

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

Рассматривали ли вы возможность использования unordered_map (он же hash_map в различных реализациях до C ++ 11?) Он должен иметь возможность поиска в O (1) вместо O (log (n)) для std::map.

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

Answer 4

Я проголосовал за unordered_map, но я также хотел высказать еще одно замечание.

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

На недавней конференции Going Native 2012 Бьярн Страуструп выступил с интересным докладом , который затрагивал эту тему. Он сравнил производительность vector и list в задаче, включающей много случайных вставок и удалений, где могло бы показаться, что list должен был доминировать, но из-за проблемы с размером и размещением памяти vector был на самом деле самый быстрый на сегодняшний день. Взгляните на его слайды , начиная с слайда 43.

unordered_map дает вам прямой доступ к элементу, и, вероятно, это означает, что в памяти даже меньше, чем попытка вставить ваши данные в vector (и, следовательно, лучшую производительность, чем vector), поэтому мой комментарий просто предостережение, чтобы всегда помнить ваш образец доступа к памяти для производительности