Когда map быстрее чем unordered
У меня даже вопроса нету. Одни эмоции. Нет, речь не о том что хеш сколлизился и мапа выродилась в лист.
Привожу пример кода, в котором простой map Быстрее(!) чем unsortered_map.
#include ctime> #include unordered_map> #include map> size_t hash_combine( size_t lhs, size_t rhs) < lhs ^= rhs + 0x9e3779b9 + ( lhs 6) + ( lhs >> 2); return lhs; > class hashme < public: size_t operator( )( const std::pairint, int> & x) const < return hash_combine( x.first, x.second); > >; int main( ) < // std::map< std::pair, int > qwe; std::unordered_map std::pairint, int>, int, hashme > qwe; for ( int i = 0; i 25; ++i) < qwe.insert( std::make_pair std::pairint, int>, int >( std::make_pair int, int >( i + 0, i + 1), i + 2)); > unsigned int start_time = clock( ); for ( int m = 0; m 20000; ++m) < for ( int i = 0; i 25; ++i) < qwe.find( std::make_pair int, int >( i + 0, i + 1)); > > printf( "-- %d --\n", clock( ) - start_time); return 0; >
Малое количество элементов в мапе наряду с вычислением hash-функции на каждый find, делают map быстрее чем unordered_map.
Такое условие — малое количество элементов в мапе и частый вызов find — отнють не сферический конь, а пример из реальной программы.
Это прекрасный пример, где мап лучше заменить на vector и делать бинарный поиск.
Но куда интересней, что разные компиляторы на разных компах дают разные результаты.
VisualStudio13 unsortered_map 10100 попугаев; map — 14800 попугаев
VisualStudio10 unsortered_map 22000 попугаев; map — 12500 попугаев
Когда я пришёл домой и опробовал это на ноутбуке — я получил противоположный результат: на vs13 Медленней чем на vs10.
Так что жопорукость vs10 отметаем, хотя vs10 — ужасен, но для данной задачи — дело не в нём.
Вариант «собрал под дебагом» тоже отметается — собирал повсякому — результат соизмеримо-одинаковый.
Так что если увидите в коде поиск по мапе или по вектору — не спешите строчить в говнокод. Unordered_map не всегда лучше.
#1
15:30, 24 мар 2015
Это просто к тому что VS очень сильно отстает по качеству stl библиотек . попробуй ещё на gcc
- Frankinshtein
- Постоялец
#2
15:35, 24 мар 2015
А если 10 и 13 сравнить еще между собой по твоим тестам что получится?
Как работает unordered map
Карта или std::map представляет контейнер, где каждое значение ассоциировано с определенным ключом. И по этому ключу можно получить элемент. Причем ключи могут иметь только уникальные значения. Примером такого контейнера может служить словарь, где каждому слову сопоставляется его перевод или объяснение. Поэтому такие структуры еще называют словарями.
Стандартная библиотека C++ предоставляет два типа словарей: std::map и std::unordered_map . Эти типы представляют шаблоны, которые типизируются двумя типами. Первый тип — Key задает тип для ключей, а второй тип — Value устанавливает тип для значений.
Тип std::map определен в заголовочном файле . Определение пустого словаря:
#include #include int main() < std::mapproducts; >
Здесь определен словарь products, который будет условно хранить цену товаров. Для ключей будет применяться тип std::string , а для значений — числа типа unsigned (условно в качестве ключа будет выступать название товара, а в качестве значения — его цена).
Обращение к элементам
Для обращения к элементам словаря — получения или изменения их значений, так же, как в массиве или векторе, применяется оператора индексирования [] . Только вместо целочисленных индексов можно использовать ключи любого типа в следующем виде:
map[ключ]=значение
#include #include int main() < std::mapproducts; // установка значений products["bread"] = 30; products["milk"] = 80; products["apple"] = 60; // получение значений std::cout
Здесь определен словарь products, в котором ключами служат строки, а значениями — числа типа unsigned. Поэтому для установки элемента в квадратные скобки передается ключ-строка, а присваивается значение-число:
products["bread"] = 30;
Будем считать, что ключ — название товара, а значение — цена товара. То есть в данном случае элементу с ключом «bread» присваивается значение 30. При этом не важно, что ранее создан пустой словарь, и в нем нет никакого элемента с ключом «bread» — если его нет, то он создается. Если же элемент с данным ключом уже есть, то меняется его значение.
Чтобы получить элемент по определенному ключу, используем тот же синтаксис. Например, поскольку значение элемента — число, то мы можем, обратившись по ключу, получить это число:
unsigned breadPrice = products["bread"];
В выше приведенной программе просто выводим значения элементов на консоль:
bread 30 milk 80 apple 60
Перебор элементов:
Для перебора элементов можно применять цикл for в стиле «for-each»:
#include #include int main() < std::mapproducts; // установка значений products["bread"] = 30; products["milk"] = 80; products["apple"] = 60; for (const auto& [product, price] : products) std::cout
Рассмотрим определение цикла. Каждый элемент словаря фактически представляет объект типа std::pair , который хранит, как ключ, так и значение. В нашем случае это объект std::pair . И с помощью полей first и second данного объекта мы могли бы получить соответственно ключ и значение элемента:
for (const auto& element : products) std::coutНо начиная со стандарта С++17 также можно использовать другой синтаксис, который позволяет сразу разложить объект на отдельные части - ключ и значение:
for (const auto& [product, price] : products) std::coutВ данном случае в product будет помещаться ключ, а в price - значение элемента словаря. В итоге при выполнении программы мы получим следующий консольный вывод:
apple 60 bread 30 milk 80Обратите внимание, что элементы располагаются в словаре и соответственно выводятся на консоль по возрастанию ключей. Поскольку ключи представляют строки, то они сортируются в алфавитном порядке.
Инициализация элементов
Тот факт, что в словаре элементы представляют тип std::pair, позволяет инициализировать словарь объектами std::pair:
#include #include int main() < std::mapproducts < std::pair, std::pair, std::pair >; >И даже можно сократить определение:
#include #include int main() < std::mapproducts < , , >; >Удаление элементов
Как было показано выше, для добавления элемента в словарь достаточно просто установить для некоторого ключа какой-нибудь значение. Для удаления же элементов применяется функция erase() , в которую передается ключ удаляемого элемента:
#include #include int main() < std::mapproducts < , , >; products.erase("milk"); // удаляем элемент с ключом "milk" for (const auto& [product, price] : products) std::coutРазмер словаря
Для получения количества элементов в словаре применяется функция size() . Также класс map имеет функцию empty() , которая возвращает true , если словарь пуст.
#include #include int main() < std::mapproducts < , , >; std::coutПроверка наличия элемента
Чтобы проверить, есть ли в словаре элемент с определенным ключом, применяются функции count() (возвращает 1, если элемент есть, и 0 - если отсутствует) и contains() (возвращает true, если элемент есть, и false - если отсутствует). В обе функции передается ключ элемента:
#include #include int main() < std::mapproducts < std::pair, std::pair, std::pair >; std::coutНеупорядоченные словари
Тип std::map определяет словарь, который упорядочиваниет все свои элементы - по умолчанию в порядке возрастания ключей. Если упорядоченность не нужна, можно применять ти std::unordered_map , который в целом предоставляет тот же самый функционал, только не упорядочивает элементы и определен в заголовочном файле
#include #include int main() < std::unordered_mapproducts < std::pair, std::pair, std::pair >; for (const auto& [product, price] : products) std::cout
apple 60 milk 80 bread 30Итераторы
Стоит отметить, что итераторы типа std::map являеются константными, что не позволяет изменять значения элементов при переборе:
#include #include int main() < std::mapphoneBook < , , >; for(auto iter; iter != phoneBook.end(); iter++) < std::cout first << "\t" second // для получения итераторов также можно использовать функции cbegin и cend for(auto iter; iter != phoneBook.cend(); iter++) < std::cout first << "\t" second >По какому принципу образуется порядок элементов в unordered_map?
Само название структуры подразумевает, что элементы в ней не отсортированы, но если перезапускать все время программу и выводить циклом элементы, то они всегда будут в одном порядке. Например вот код из этой книги
struct coord < int x; int y; >; bool operator==(const coord &l, const coord &r) < return l.x == r.x && l.y == r.y; >namespace std < template <>struct hash < using argument_type = coord; using result_type = size_t; result_type operator()(const argument_type &c) const < return static_cast(c.x) + static_cast(c.y); > >; > int main() < std::unordered_mapm , 1>, , 2>, , 3>>; for (const auto & [key, value] : m) < std::cout "; > std::coutХэш формируется из сложения x и y , поэтому я думал, что по итоговому хэшу и будет выстроен порядок, но оказалось, что это так не работает. Порядок вывода всегда такой:
Как это работает?
Отслеживать
задан 11 июл 2021 в 16:53
195 9 9 бронзовых знаковЭто не сортировка, но порядок связан с хеш-значением. Причем опять же - это не значит, что элементы отсортированы по хешу.
11 июл 2021 в 16:56
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Для того, что бы ответить на вышеуказанный вопрос, для начала нужно понять, а как собственно устроен unordered_map изнутри. Есть два способа реализации, но самый простой и легкий из них - метод цепочек. Вроде он и применяется в стандартной библиотеке.
Сами данные хранятся в векторе списков. То есть так
class my_umap < std::vector>> m_data; >;когда нужно вставить элемент, то от индекса рассчитывается хеш (в нашем случае функция хеша должна уметь преобразовывать тип ключа в некое число в диапазоне 0..m_data.size()-1 . Обычно, хеш функция просто возвращает обычный int , а потом используется деление по модулю с помощью % . По полученному числу находится элемент вектора, в который в список и добавляется необходимый элемент (да, предварительно, проверяется, а нет ли такого элемента ещё).
Функция итерации по мапе обычно делается по простому - проходимся по всем элементам массива (вектора) и выводим элементы списка (опять же, в естественном порядке).
Теперь стает понятно, что при выводе элементов порядок будет определятся хеш функцией и тем, как элементы были вставлены в пределах одного и того же значения хеш функции.
Хеш функции обычно такие, что одному и тому же значению входного значения соответствует одно и тоже выходное значение (иначе это все работать не будет). Но с другой стороны, хеш функция старается максимально равномерно "размазать" значения хеша. Поэтому, если два значения (например, два int ) упорядочены по возрастанию, то значения хеш функции (идеальной конечно) будет упорядочены с вероятностью 50 на 50 (да, они могут совпасть, поэтому, наверно на самом деле это будет 49-49-2 или что то другое, похожее).
Чем же определяется хеш? его может явно задать программист, а может использоваться реализация от компилятора. Важно то, что с большущей вероятностью (если код не менялся), она не поменяется, а значит, значения хеша, которые определяют элемент вектора, будут те же.
Рекомендую попробовать написать свою реализацию unordered_map (того, что я написал выше уже достаточно для этого) и все вопросы пропадут сами собой.
Некоторые языки (например, golang) любят рандомизировать немного хеш функцию от запуска к запуску (для мнимой безопасности), тем самым доставляя кучу приятных впечатлений для молодых программистов.
Есть ещё одна реализация unordered_map - открытая адресация, но он немного сложнее, как по мне в реализции.
Как работает unordered map
rliu4936 → how do i escape blue
remmymilkyway → USACO Not Responding
AyuAnchor → NITS Hacks 6.0 Inter College Coding Competition (Prizes worth 50k INR)
JaySharma1048576 → Codeforces Round 921 (Div. 1, Div. 2) (Partial) Editorial
Giga_Cronos → Cloudflare is screwing up contests
Duelist1234 → About EJOI 2024
awoo → Разбор Educational Codeforces Round 161
xiaowuc1 → USACO 2023-2024 Second Contest
stefdasca → Click here if you want to know your future CF rating [Part 2]
samsidx → What is a constructive algorithm??
Kolyanchick → День 51 (Эксперт за 100 дней)
spoily_frog → Using NumPyPy using PyPy2
Halym2007 → What is the difference between them?
atcoder_official → AtCoder Beginner Contest 338 Announcement
CEKPET → Для меня настали чёрные дни
Nickir → Grey Lives Matter!
Hassan_Fathi → Another cheating blog
TheEgoist → Nutella is a LGM xD
yash_daga → Codeforces Round 921 (Div. 1 , Div. 2)
brave-kid → USACO website down?
aryanc403 → India ICPC — Amritapuri 2023 Regionals Round (With live commentry)
orz → Я приступил к Project Euler
Smile_One_Smile → Which ide do you prefer?
Ansish → Путь до Специалиста-День 1
MikeMirzayanov → Polygon: Warnings for Packages — Incomplete Tests + Statement/Validator Mismatches
Блог пользователя tamir
Автор tamir, 10 лет назад ,
Привет! Объясните структуры данных unordered_map,unordered set(с примерами) и какую роль данные структуры данных играют в олимпиадном программировании. Я читал про них в сети, но большинство материала на английском языке. Я понял, что unordered_map не сортирует данные по ключу(как map) и доступ осуществляется быстрее чем в map из-за непонятных buckets (хэширования ключа?). С unorder_set тоже самое насчет доступа и неотсортированности. Спасибо за внимание!
unordered_map, unordered_set, структруры данных
Комментарии (6)
10 лет назад , # |
Я тоже такое видел, но забыл спросить
10 лет назад , # |
10 лет назад , # ^ |
Здесь я был уже — не очень понятно(
10 лет назад , # |Это хеш-таблицы. Ключи по умолчанию хешируются функтором std::hash . Можно притворяться, что каждый доступ к элементу по ключу стоит столько же, сколько один вызов хеш-функции плюс O(1). Есть unordered_map , unordered_multimap , unordered_set и unordered_multiset , и разница между ними такая же, как между map , multimap , set и multiset . Разница же между первым набором и вторым набором, как уже замечено, в том, что это — хеш-таблицы с операциями за практически константное время и отсутствием сортировки, а то — сбалансированные бинарные деревья поиска (на практике — конкретно красно-чёрные деревья) с операциями за гарантированное логарифмическое время и автоматической сортировкой.
10 лет назад , # ^ |
А можете объяснить как работает std::hash
и часто ли случаются коллизий? И как часто он используется в решений олимпиадных задач? 10 лет назад , # ^ |
← Rev. 3 →
+3
hash, в случае строк я предполагаю, использует полиномиальное хеширование. Коллизии встречаются довольно редко, но даже если и случаются, обрабатываются правильно и на асимптотику почти никак не влияют. При желании почитай в википедии (желательно английской) про хеш-таблицы, там все хорошо описано. В олимпиадных задачах, на самом деле хеши применяются редко (как правило только в задачах на строки) и обычно пишутся самостоятельно. Например, std::hash (если я ничего не путаю) не поддерживает хеши на префиксах, и соответственно на подотрезках. Так что, я бы не стал на std::hash полагаться UPD. А еще и там много коллизий, как оказалось. Я был неправ тогда
