Есть ли какое-либо преимущество использования карты по unordered_map в случае тривиальных ключей?
Недавний разговор о unordered_map в C++ заставил меня понять, что я должен использовать unordered_map для большинства случаев, где я использовал map прежде, из-за эффективности поиска (амортизировал O (1) по сравнению с O (регистрируют n)). Большинство раз я использую карту, я использую также int или std::string как ключевой тип; следовательно, у меня нет проблем с определением хеш-функции. Чем больше я думал об этом, тем больше я пришел к пониманию, что не могу найти причину использования a std::map по a std::unordered_map в случае ключей с простыми типами - я смотрел на интерфейсы и не нашел существенных различий, которые повлияют на мой код.
Следовательно вопрос: есть ли любая настоящая причина для использования std::map std::unordered map в случае простых типов как int и std::string?
Я спрашиваю со строго точки зрения программирования - я знаю, что она не полностью рассмотрела стандарт, и что она может создать проблемы с портированием.
Кроме того, я ожидаю, что один из корректных ответов мог бы быть, "это более эффективно для меньших наборов данных" из-за меньших издержек (который верен?) - следовательно я хотел бы ограничить вопрос случаям, где сумма ключей нетривиальна (> 1 024).
Править: понятное дело я забыл очевидное (благодарит GMan!) - да, карты заказаны, конечно - я знаю, что, и ищу другие причины.
4 ответа
Не забывайте, что map сохраняет порядок своих элементов. Если вы не можете отказаться от этого, очевидно, вы не можете использовать unordered_map .
Также следует иметь в виду, что unordered_map обычно использует больше памяти. map просто имеет несколько служебных указателей и память для каждого объекта. Напротив, unordered_map имеет большой массив (в некоторых реализациях он может стать довольно большим), а затем дополнительную память для каждого объекта. Если вам нужно учитывать память, лучше использовать map , потому что в ней отсутствует большой массив.
Итак, если вам нужен чистый поиск-поиск, я бы сказал, что unordered_map - это то, что вам нужно. Но всегда есть компромиссы, и если вы не можете их себе позволить, вы не можете им воспользоваться.
На собственном опыте я обнаружил огромное улучшение производительности (измеренное, конечно) при использовании unordered_map вместо map в поисковой таблице основной сущности.
С другой стороны, я обнаружил, что он намного медленнее многократно вставлял и удалял элементы. Это отлично подходит для относительно статической коллекции элементов, но если вы выполняете множество вставок и удалений, хеширование + ведение, похоже, складываются. (Обратите внимание, это было несколько итераций.)
Я просто хочу отметить, что ... существует много видов unordered_map s.
Найдите статью в Википедии на хэш-карте. В зависимости от того, какая реализация использовалась, характеристики поиска, вставки и удаления могут значительно различаться.
И это то, что меня больше всего беспокоит с добавлением unordered_map в STL: им придется выбрать конкретную реализацию, поскольку я сомневаюсь, что они пойдут по пути Policy , и поэтому мы застрянем с реализацией для среднего использования и ничего для других случаев ...
Например, некоторые хэш-карты имеют линейное повторное хеширование, где вместо повторного хеширования всей хеш-карты за раз, повторно хешируется часть при каждой вставке, что помогает амортизировать стоимость.
Другой пример: некоторые хэш-карты используют простой список узлов для корзины, другие используют карту, третьи не используют узлы, но находят ближайший слот, и, наконец, некоторые будут использовать список узлов, но переупорядочить его так, чтобы последний доступный элемент находится впереди (как кеширующий элемент).
Поэтому на данный момент я предпочитаю std :: map или, возможно, loki :: AssocVector (для замороженных наборов данных).
Не поймите меня неправильно, я бы хотел использовать std :: unordered_map и могу в будущем, но трудно «доверять» переносимости такого контейнера, когда вы думаете обо всех способах его реализации и различных действиях, которые в результате этого.
Я бы повторил примерно то же самое, что сделал GMan: в зависимости от типа использования std :: map может быть (и часто) быстрее, чем std :: tr1 :: unordered_map (с использованием реализации, включенной в VS 2008 SP1).
Следует иметь в виду несколько осложняющих факторов. Например, в std :: map вы сравниваете ключи, что означает, что вы всегда смотрите только на начало ключа, достаточное для того, чтобы различать правую и левую подветвь дерева. По моему опыту, почти единственный раз, когда вы смотрите на весь ключ, вы используете что-то вроде int, которое вы можете сравнить в одной инструкции. С более типичным типом ключа, таким как std :: string, вы часто сравниваете всего несколько символов или около того.
Приличная хеш-функция, напротив, всегда смотрит на весь ключ . IOW, даже если поиск в таблице имеет постоянную сложность, сам хеш имеет примерно линейную сложность (хотя по длине ключа, а не по количеству элементов).С длинными строками в качестве ключей std :: map может завершить поиск до того, как unordered_map даже начнет свой поиск.
Во-вторых, хотя существует несколько методов изменения размера хеш-таблиц, большинство из них довольно медленные - до такой степени, что, если поиск значительно не выполняется чаще, чем вставки и удаления, std :: map часто будет быть быстрее, чем std :: unordered_map .
Конечно, как я уже упоминал в комментарии к вашему предыдущему вопросу, вы также можете использовать таблицу деревьев. В этом есть как преимущества, так и недостатки. С одной стороны, он ограничивает худший случай деревом. Он также позволяет быстро вставлять и удалять, потому что (по крайней мере, когда я это сделал) я использовал таблицу фиксированного размера. Устранение всего изменения размеров таблиц позволяет сделать вашу хеш-таблицу намного проще и, как правило, быстрее.
Еще один момент: требования к хешированию и древовидным картам различаются. Очевидно, что для хеширования требуется хеш-функция и сравнение на равенство, тогда как для упорядоченных карт требуется меньшее, чем сравнение. Конечно, упомянутый мной гибрид требует и того, и другого. Конечно, для обычного случая использования строки в качестве ключа это не проблема, но некоторые типы ключей подходят для упорядочивания лучше, чем хеширование (или наоборот).
Хеш-таблицы имеют более высокие константы, чем обычные реализации карт, что становится важным для небольших контейнеров. Максимальный размер - 10, 100, а может быть, даже 1000 или больше? Константы такие же, как всегда, но O (log n) близко к O (k). (Помните, что логарифмическая сложность по-прежнему действительно хороша.)
Что делает хорошую хеш-функцию, зависит от характеристик ваших данных; поэтому, если я не планирую смотреть на пользовательскую хэш-функцию (но, безусловно, могу передумать позже, и это легко, так как я набираю чертовски почти все), и хотя значения по умолчанию выбраны для приличной работы для многих источников данных, я нахожу упорядоченный характер карты, чтобы быть достаточным помощником на начальном этапе, поэтому я все еще по умолчанию использую карту, а не хеш-таблицу в этом случае.
Кроме того, вам не нужно даже думать о написании хеш-функции для других (обычно UDT) типов, а просто писать op <(что вы все равно хотите).