Еще одна упорядоченная карта против неупорядоченного (хэш) вопроса карты

Question

Это очень наивный вопрос, но я не могу найти его в явном виде.Все согласны с тем, что использование хеша для контейнера карты, содержащего только 10 элементов, является излишним ... заказанная карта будет намного быстрее.С сотней;тысяча и т. д. карта должна масштабироваться по logN, где N = количество пар на карте.Так, на тысячу человек это занимает в три раза больше времени;миллион, в шесть раз больше;10 миллиардов, в девять раз длиннее.

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

Что происходит?

Answer 1

Как вы уже сказали, карта на основе хеша может быть асимптотически быстрее, чем двоичное дерево поиска, с запросами за O(1) против O(log(N)) времени - но это полностью зависит от производительности хеша функция, используемая над допустимым распределением входных данных.

Есть две важные наихудшие ситуации, о которых следует подумать с помощью хеш-таблицы:

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

С другой стороны, двоичное дерево поиска (по крайней мере красно-черное дерево, используемое в большинстве реализаций стандартных библиотек) имеет наихудший случай O(log(N)) времени и O(N) сложности пространства.

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

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

Точная точка, в которой один становится лучше другого, полностью зависит от проблемы / машины.

Надеюсь, это поможет.

Answer 2

Точная точка, в которой карты хеширования быстрее, будет зависеть от машины.

Это правда, что для прохождения карты требуется всего лишь O (log n) «шагов».Но, посмотрев на постоянный фактор на мгновение, обратите внимание, что основание для этого журнала - 2, а не 10;и бинарное дерево, вероятно, реализовано как красно-черное дерево, которое в целом не идеально сбалансировано.(Если память служит, она может быть в 2 раза глубже, чем log2 (n).)

Однако на самом деле разница заключается в плохом расположении упорядоченной карты.Каждый из этих шагов O (log n) включает ветвь, которую невозможно предсказать, что плохо для конвейера команд.Хуже того, это связано с погоней случайного указателя на память.Основное правило современных процессоров: «Математика - это быстро, память - медленно».Это хорошее правило, чтобы помнить, потому что оно становится более верным с каждым поколением.Скорости ядра процессора обычно улучшаются быстрее, чем скорости памяти.

Так что, если ваша карта не достаточно мала, чтобы поместиться в кэш, эти случайные разыменования указателей очень плохи для общей производительности.Вычисление хэша - это просто математика (и, следовательно, быстрая), и погоня за O (1) указателями лучше, чем погоня за O (log n);обычно гораздо лучше для больших n.

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

Answer 3

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

Хешбудет быстрее, если это действительно O (1) (т.е. функция has действительно хороша), а вычисление хеш-функции относительно быстрое (для начала - не зависит от размера ввода).

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

Опять же, волшебное слово - benchmark .