Разница в производительности для итерации по всем элементам std :: unordered_map vs std :: map? - PullRequest
Новая
       15

Разница в производительности для итерации по всем элементам std :: unordered_map vs std :: map?

4 голосов
/ 30 июня 2019

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

std::map<classKey* , classData*> myMap;
std::unordered_map<classKey* , classData*> myUnorderedMap;

for (auto & iter : myMap) { //loop1
    display(iter.second);
}

for (auto & iter : myUnorderedMap) { //loop2
    display(iter.second);
}

loop1 против loop2, что повышает производительность. Bench Mark Предоставлено @ RetiredNinja

Для размера = 10 000 000 Мы получаем следующие результаты тестов:

enter image description here

1 Ответ

5 голосов
/ 30 июня 2019

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

A std::map использует сбалансированное двоичное дерево под обложками.Вот почему он имеет O (log (n)) для вставки, удаления и поиска.Итерации по нему должны быть линейными, потому что вам просто нужно выполнить обход в глубину (что потребует O (log (n)) памяти в виде стекового пространства).Преимущество использования std::map для итерации состоит в том, что вы будете перебирать ключи в отсортированном порядке, и вы получите это преимущество "бесплатно".

A std::unordered_map использует хеш-таблицу под обложками.Это позволяет вставлять, удалять и искать амортизированные данные с постоянным временем.Если реализация не оптимизирована для итерации, наивным подходом будет итерация по каждому сегменту в хэш-таблице.Поскольку хорошая хеш-таблица (в теории) имеет ровно один элемент в 50% сегментов и ноль в остальных, эта операция также будет линейной.Однако это займет больше «времени настенных часов», чем та же линейная операция для std::map.Чтобы обойти это, некоторые реализации хеш-таблиц содержат боковой список всех элементов для быстрых итераций.Если это так, итерация на std::unordered_map будет быстрее, потому что вы не можете получить намного лучше, чем итерации по непрерывной памяти (хотя все еще линейное время, очевидно).

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

Все это игнорирует странность отключения указателязначение, но это ни здесь, ни там.

Источники для дальнейшего чтения:

GCC std :: реализация карты

GCC std :: unordered_map реализация

Как GCC std :: unordered_map достигает быстрой итерации

...