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

https://stackoverflow.com/questions/371136

21-08-2019
|

Вопрос

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

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

Решение

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

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

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

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

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

Другие советы

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

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

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

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

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

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

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

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

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

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

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

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

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

Мне нравится ответ Билла, но на самом деле он ничего не обобщает.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow