Есть ли преимущество использования map перед unordered_map в случае тривиальных ключей?

Question

Недавний разговор о unordered_map в C ++ заставил меня понять, что я должен использовать unordered_map для большинства случаев, когда я использовал map из-за эффективности поиска ( амортизированный O (1) против O (log n) ). В большинстве случаев я использую карту, я использую int или std::strings в качестве ключей, поэтому у меня нет проблем с определением хеш-функции. Чем больше я думал об этом, тем больше осознавал, что не могу найти никакой причины использования std::map в случае простых типов над unordered_map - я посмотрел на интерфейсы и не стал Не могу найти каких-либо существенных различий, которые могли бы повлиять на мой код.

Отсюда возникает вопрос - есть ли реальная причина использовать std::map над unordered map в случае простых типов, таких как int и std::string?

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

Также я ожидаю, что один из правильных ответов может быть «он более эффективен для небольших наборов данных» из-за меньших издержек (это правда?) - поэтому я бы хотел ограничить вопрос к случаям, когда количество ключей нетривиально (> 1 024).

Редактировать: Да, я забыл очевидное (спасибо GMan!) - да, карты, конечно, упорядочены - я знаю это, и ищу другие причины.

Answer 1

Не забывайте, что map хранят свои элементы в порядке. Если вы не можете отказаться от этого, очевидно, вы не можете использовать unordered_map.

Что еще нужно помнить, это то, что unordered_map обычно использует больше памяти. У map просто есть несколько указателей на ведение домашнего хозяйства, а затем память для каждого объекта. Наоборот, unordered_map имеют большой массив (в некоторых реализациях он может быть довольно большим), а затем дополнительную память для каждого объекта. Если вам необходимо учитывать память, map должен оказаться лучше, поскольку ему не хватает большого массива.

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

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

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

Answer 2

Если вы хотите сравнить скорость ваших std::map и std::unordered_map реализаций, вы можете использовать проект Google sparsehash , в котором есть программа time_hash_map для их измерения. Например, с gcc 4.4.2 в системе x86_64 Linux

$ ./time_hash_map
TR1 UNORDERED_MAP (4 byte objects, 10000000 iterations):
map_grow              126.1 ns  (27427396 hashes, 40000000 copies)  290.9 MB
map_predict/grow       67.4 ns  (10000000 hashes, 40000000 copies)  232.8 MB
map_replace            22.3 ns  (37427396 hashes, 40000000 copies)
map_fetch              16.3 ns  (37427396 hashes, 40000000 copies)
map_fetch_empty         9.8 ns  (10000000 hashes,        0 copies)
map_remove             49.1 ns  (37427396 hashes, 40000000 copies)
map_toggle             86.1 ns  (20000000 hashes, 40000000 copies)

STANDARD MAP (4 byte objects, 10000000 iterations):
map_grow              225.3 ns  (       0 hashes, 20000000 copies)  462.4 MB
map_predict/grow      225.1 ns  (       0 hashes, 20000000 copies)  462.6 MB
map_replace           151.2 ns  (       0 hashes, 20000000 copies)
map_fetch             156.0 ns  (       0 hashes, 20000000 copies)
map_fetch_empty         1.4 ns  (       0 hashes,        0 copies)
map_remove            141.0 ns  (       0 hashes, 20000000 copies)
map_toggle             67.3 ns  (       0 hashes, 20000000 copies)

Answer 3

Я бы повторил примерно ту же мысль, которую сделал GMan: в зависимости от типа использования, std::map может быть (и часто) быстрее, чем std::tr1::unordered_map (используя реализацию, включенную в VS 2008 SP1).

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

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

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

Конечно,как я уже упоминал в комментарии к вашему предыдущему вопросу, вы также можете использовать таблицу деревьев.Это имеет как преимущества, так и недостатки.С одной стороны, он ограничивает наихудший случай деревом.Это также позволяет быстро вставлять и удалять, потому что (по крайней мере, когда я это сделал) я использовал таблицу фиксированного размера.Исключение всех размеров таблиц позволяет вам сохранять хеш-таблицу намного проще и, как правило, быстрее.

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

Answer 4

Я был заинтригован ответом @Jerry Coffin, который предположил, что упорядоченная карта будет демонстрировать увеличение производительности на длинных строках, после некоторого эксперимента (который можно загрузить из pastebin ), я обнаружил, чтокажется, что это справедливо только для коллекций случайных строк, когда карта инициализируется с помощью отсортированного словаря (который содержит слова со значительным количеством префиксов с перекрытием), это правило нарушается, предположительно из-за увеличенной глубины дерева, необходимой для извлечениязначение.Результаты показаны ниже, 1-й числовой столбец - время вставки, 2-й - время выборки.

g++ -g -O3 --std=c++0x   -c -o stdtests.o stdtests.cpp
g++ -o stdtests stdtests.o
gmurphy@interloper:HashTests$ ./stdtests
# 1st number column is insert time, 2nd is fetch time
 ** Integer Keys ** 
 unordered:      137      15
   ordered:      168      81
 ** Random String Keys ** 
 unordered:       55      50
   ordered:       33      31
 ** Real Words Keys ** 
 unordered:      278      76
   ordered:      516     298

Answer 5

Я бы просто отметил, что ... существует множество видов unordered_map s.

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

И вот что меня больше всего беспокоит с добавлением unordered_map к STL: они будутЯ должен выбрать конкретную реализацию, так как я сомневаюсь, что они пойдут по пути Policy, и поэтому мы застрянем с реализацией для среднего использования и ничего для других случаев ...

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

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

Так что на данный момент я предпочитаю std::map или, возможно, loki::AssocVector (для фиксированных наборов данных).

Не поймите меня неправильно, я хотел бы использовать std::unordered_map, и я могу в будущем, но трудно "доверять" переносимости такого контейнера, когда вы думаете обо всех способахреализации и различных результатов, которые в результате этого.

Answer 6

Существенные различия, которые не были должным образом упомянуты здесь:

• map сохраняет итераторы для всех элементов стабильными, в C ++ 17 вы даже можете перемещать элементы из одного map в другой, не делая для них итераторы недействительными (и при правильной реализации без какого-либо потенциального размещения).
• map тайминги для отдельных операций, как правило, более согласованы, так как им никогда не требуются большие выделения.
• unordered_map использование std::hash, как это реализовано в libstdc ++, уязвимо для DoS, если подается с ненадежным вводом (он использует MurmurHash2 с постоянным начальным числом - не то, что начальное заполнение действительно поможет, см. https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/).
• При заказе возможен эффективный поиск по дальности, например, переберите все элементы с ключом & ge; 42.

Answer 7

Хеш-таблицы имеют более высокие константы, чем обычные реализации карт, что становится значимым для небольших контейнеров. Максимальный размер 10, 100, а может, даже 1000 или больше? Константы такие же, как и всегда, но O (log n) близко к O (k). (Помните, что логарифмическая сложность все еще действительно хороша.)

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

Кроме того, вам не нужно даже думать о написании хеш-функции для других (обычно UDT) типов, а просто написать op <(что вы в любом случае хотите). </p>

Answer 8

Причины были даны в других ответах; вот еще один.

Операции std :: map (сбалансированное двоичное дерево) амортизируются O (log n) и наихудшим O (log n). Операции std :: unordered_map (hash table) амортизируются O (1) и наихудшим O (n).

На практике это проявляется в том, что хеш-таблица «икает» время от времени с помощью операции O (n), что может или не может быть тем, что ваше приложение может терпеть. Если он не может это терпеть, вы бы предпочли std :: map вместо std :: unordered_map.

Answer 9

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

Для реализации map требуется 200 мс для завершения работы.Для unordered_map + map требуется 70 мс для вставки unordered_map и 80 мс для вставки map.Таким образом, гибридная реализация на 50 мс быстрее.

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

Answer 10

Резюме

Предполагается, что заказ не важен:

• Если вы собираетесь создать большую таблицу один раз и выполнять много запросов, используйте std::unordered_map
• Если вы собираетесь построить небольшую таблицу (может содержать менее 100 элементов) и выполнять много запросов, используйте std::map. Это потому, что на нем написано O(log n).
• Если вы собираетесь много менять стол, то может быть std::map - хороший вариант.
• Если вы сомневаетесь, просто используйте std::unordered_map.

Исторический контекст

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

Широко распространено мнение о том, что в C ++ по умолчанию используется упорядоченная карта, поскольку параметров их реализации не так уж много. С другой стороны, реализациям на основе хешей есть о чем поговорить. Таким образом, чтобы избежать блокировок при стандартизации, они просто ладили с упорядоченной картой. Приблизительно в 2005 году многие языки уже имели хорошие реализации реализации, основанной на хэше, и поэтому комитету было легче принять новый std::unordered_map. В идеальном мире std::map был бы неупорядоченным, и у нас было бы std::ordered_map как отдельный тип.

Производительность

Ниже два графика должны говорить сами за себя ( источник ):