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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

несколько вещей, чтобы следить за.

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

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

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

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

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

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

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

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

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

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

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

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