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

Question

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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

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), если дерево остается идеально сбалансированным. Сохранение сбалансированного дерева (например, красно-черного) увеличивает сложность и время вставки. Кроме того, как со связанными списками, так и с двоичными деревьями, каждый элемент представляет собой отдельно выделенный ¹ узел , что означает, что вам придется разыменовывать указатели и, вероятно, переходить к потенциально сильно меняющимся адресам памяти , увеличивая шансы на промах кеша.

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

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

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

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

Answer 5

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

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

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

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

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

Answer 6

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

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

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

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

Answer 7

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

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

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

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

Answer 8

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

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

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

Answer 9

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

Answer 10

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