Бинарные деревья против связанных списков против хэш-таблиц

Question

Я строю таблицу символов для проекта, над которым я работаю. Мне было интересно, что люди думают о преимуществах и недостатках различных методов хранения и создания таблицы символов.

Я провел немало поисков, и чаще всего рекомендуются двоичные деревья или связанные списки или хеш-таблицы. Каковы преимущества и недостатки всего вышеперечисленного? (работает на с ++)

Answer 1

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

Поэтому вам нужно использовать быстрый алгоритм поиска нужной вам информации.

Поэтому я думаю, что HashTable был наиболее подходящим алгоритмом для использования, поскольку он просто генерирует хеш вашего ключевого объекта и использует его для доступа к целевым данным - это O(1). Другими являются O(N) (связанные списки размером N - вам нужно перебирать список по одному, в среднем N/2 раза) и O(log N) (двоичное дерево - вы вдвое сокращаете пространство поиска с помощью каждая итерация - только если дерево сбалансировано, так что это зависит от вашей реализации, несбалансированное дерево может иметь значительно худшую производительность).

Просто убедитесь, что в HashTable достаточно места (сегментов) для ваших данных (Re, комментарий Сораза к этой записи). Большинство реализаций фреймворка (Java, .NET и т. Д.) Будут иметь качество, которое вам не нужно беспокоиться о реализации.

Вы проходили курс по структурам данных и алгоритмам в университете?

Answer 2

Применяются стандартные компромиссы между этими структурами данных.

• Двоичные Деревья
  • средняя сложность для реализации (при условии, что вы не можете получить их из библиотеки)
  • вставки O (логн)
  • поиски O(logN)
• Связанные списки (не отсортированные)
  • низкая сложность в реализации
  • вставки O(1)
  • поиски O(N)
• Хеш-таблицы
  • высокая сложность реализации
  • вставки в среднем O(1)
  • поиски O(1) в среднем

Answer 3

Кажется, что все забывают, что для небольших N, т. Е. Для небольшого количества символов в вашей таблице, связанный список может быть намного быстрее, чем хеш-таблица, хотя теоретически его асимптотическая сложность действительно выше.

Есть известная цитата из заметок Пайка о программировании на C: "Правило 3. Необычные алгоритмы медленны, когда n мало, а n обычно мало. Необычные алгоритмы имеют большие константы. Пока вы не знаете, что n часто будет большим, не увлекайся. " http://www.lysator.liu.se/c/pikestyle.html

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

Answer 4

Похоже, что все может быть правдой:

• Ваши ключи являются строками.
• Вставки делаются один раз.
• Поиск выполняется часто.
• Количество пар ключ-значение относительно мало (скажем, меньше, чем K или около того).

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

Почему поиск может быть быстрее с отсортированным списком? Что ж, ясно, что это быстрее, чем связанный список, со временем поиска O(N) последнего. В двоичном дереве поиски остаются только O (log ₂ N), если дерево остается идеально сбалансированным. Сохранение сбалансированного дерева (например, красно-черного) увеличивает сложность и время вставки. Кроме того, как со связанными списками, так и с двоичными деревьями, каждый элемент представляет собой отдельно выделенный ¹ узел, что означает, что вам придется разыменовывать указатели и, вероятно, переходить к потенциально сильно изменяющимся адресам памяти, что увеличивает шансы на пропуск кеша.

Что касается хеш-таблиц, вам, вероятно, следует прочитать еще пару вопросов здесь, в Stackru, но основные моменты, которые здесь интересны:

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

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

1. _{Для реализации возможно предварительно выделить массив узлов, что поможет решить проблему с отсутствием кэша. Я не видел этого ни в одной реальной реализации связанных списков или бинарных деревьев (конечно, я видел не все), хотя вы, конечно, могли бы сделать свой собственный. У вас все равно будет чуть более высокая вероятность пропадания кэша, поскольку объекты узла обязательно будут больше, чем пары ключ / значение.}

Answer 5

Мне нравится ответ Билла, но он на самом деле не синтезирует вещи.

Из трех вариантов:

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

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

Это оставляет деревья. Здесь у вас есть возможность: балансировать или не балансировать. Что я обнаружил, изучая эту проблему на C и коде Фортрана, которые мы здесь имеем, так это то, что вход таблицы символов имеет тенденцию быть достаточно случайным, и вы теряете только один или два уровня дерева, не уравновешивая дерево. Учитывая, что сбалансированные деревья медленнее вставляют элементы и их сложнее реализовать, я бы не стал их беспокоить. Однако, если у вас уже есть доступ к хорошим библиотекам отлаженных компонентов (например, STL в C++), вы можете использовать сбалансированное дерево.

Answer 6

Пара вещей, на которые стоит обратить внимание.

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

• Хеш-таблицы дают O(1) усредненную сложность вставки и поиска, но и здесь есть один нюанс. Если ваша хеш-функция плохая (а я имею в виду очень плохая), вы можете также создать связанный список здесь. Любая разумная строковая хеш-функция должна, однако, так что это предупреждение действительно только для того, чтобы вы знали, что это может произойти. Вы должны быть в состоянии просто проверить, что ваша хеш-функция не имеет много коллизий в ожидаемом диапазоне входных данных, и все будет в порядке. Еще один незначительный недостаток - использование хеш-таблицы фиксированного размера. Большинство реализаций хеш-таблицы растут, когда достигают определенного размера (точнее, коэффициента загрузки, подробности см. Здесь). Это сделано для того, чтобы избежать проблемы, возникающей при вставке миллиона символов в десять сегментов. Это просто приводит к десяти связанным спискам со средним размером 100 000.

• Я использовал бы только связанный список, если бы у меня была действительно короткая таблица символов. Его проще всего реализовать, но лучшая производительность для связанного списка - это худшая производительность для двух других вариантов.

Answer 7

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

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

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

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

Answer 8

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

Answer 9

Если вы не ожидаете, что ваша таблица символов будет маленькой, я должен держаться подальше от связанных списков. Список из 1000 элементов в среднем займет 500 итераций, чтобы найти любой элемент в нем.

Бинарное дерево может быть намного быстрее, если оно сбалансировано. Если вы сохраняете содержимое, сериализованная форма, скорее всего, будет отсортирована, и при повторной загрузке результирующее дерево будет, как следствие, полностью несбалансированным и будет вести себя так же, как связанный список - потому что это в основном то, что стало. Алгоритмы сбалансированного дерева решают эту проблему, но делают весь Шебанг более сложным.

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

Answer 10

Этот вопрос проходит через различные контейнеры в C#, но они похожи на любом языке, который вы используете.