Зачем использовать двоичный поиск, если есть тройной поиск?

Ответ 1

Собственно, люди используют k-арные деревья для произвольного k.

Это, однако, компромисс.

Чтобы найти элемент в k-арном дереве, вам понадобятся операции k * ln (N)/ln (k) (помните формулу изменения базы). Чем больше ваш k, тем больше операций вам нужно.

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

Ответ 2

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

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

Ответ 3

Поиск 1-го миллиарда (US миллиардов - 1 000 000 000) отсортированных предметов займет в среднем около 15 сравнений с бинарным поиском и около 9 сравнений с тройным поиском - не огромное преимущество. И обратите внимание, что каждое "тройное сравнение" может включать в себя 2 фактических сравнения.

Ответ 4

Ого. Полагаю, что лучшие голосовые ответы пропускают лодку на этом.

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

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

B-Trees, однако, довольно распространены. Если вы предположите, что каждый node в дереве будет храниться где-то отдельно на диске, вы будете тратить большую часть своего времени на чтение с диска... и процессор не будет узким местом, но диск будет, Таким образом, вы берете B-дерево со 100 000 детей на node, или что-то еще не вписывается в один блок памяти. B-деревья с таким фактором ветвления редко бывают более трех узлов, и у вас будет только три чтения диска - три остановки на узком месте - для поиска огромного огромного набора данных.

Рецензирование:

• Тернарные деревья не поддерживаются аппаратными средствами, поэтому они работают менее быстро.
• B-tress с заказами намного, намного, намного выше, чем 3, являются общими для дисковой оптимизации больших наборов данных; как только вы пройдете мимо 2, перейдите выше 3.

Ответ 5

Что заставляет вас думать, что поиск по Ternary должен быть быстрее?

Среднее количество сравнений:

in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search  =                   1 * ln(n)/ln(2) ~ 1.443*ln(n).

Наихудшее количество сравнений:

in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search  = 1 * ln(n)/ln(2) ~ 1.443*ln(n).

Итак, похоже, что тройной поиск хуже.

Ответ 6

Единственный способ, которым тройной поиск может быть быстрее, чем двоичный поиск, заключается в том, что определение трехстороннего раздела может быть выполнено менее чем в 1,55 раза по сравнению с ценой двухстороннего сравнения. Если элементы хранятся в отсортированном массиве, трехпозиционное определение в среднем будет в 1,66 раза дороже, чем определение в 2 направлениях. Однако, если информация хранится в дереве, стоимость получения информации высока относительно стоимости фактического сравнения, а местность кэш-памяти означает, что стоимость случайной выборки пары связанных данных не намного хуже, чем затраты на получение одного datum, тройное или n-образное дерево может значительно повысить эффективность.

Ответ 7

Также обратите внимание, что эта последовательность обобщается на линейный поиск, если мы идем на

Binary search
Ternary search
...
...
n-ary search ≡ linear search

Таким образом, при n-арном поиске у нас будет "только один СРАВНИТЬ", который может принимать до n фактических сравнений.

Ответ 8

"Терины" (тройной?) поиск более эффективен в лучшем случае, который предполагает поиск первого элемента (или, возможно, последнего, в зависимости от того, какое сравнение вы делаете в первую очередь). Для элементов, расположенных дальше от конца, вы проверяете сначала, в то время как два сравнения будут сужать массив по 2/3 каждый раз, те же самые два сравнения с бинарным поиском будут сузить пространство поиска на 3/4.

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

Ответ 9

Тернарный поиск может эффективно использоваться на параллельных архитектурах - ПЛИС и ASIC. Например, если внутренняя память ПЛИС, необходимая для поиска, составляет менее половины ресурса ПЛИС, вы можете сделать дубликат блока памяти. Это позволит одновременно обращаться к двум различным адресам памяти и выполнять все сравнения за один такт. Это одна из причин, по которой 100 МГц FPGA может иногда превосходить процессор 4 ГГц:)

Ответ 10

Здесь некоторые случайные экспериментальные данные, которые я вообще не проверял, показывая, что он медленнее, чем двоичный поиск.

Ответ 11

Практически все учебники и веб-сайты на деревьях двоичного поиска действительно не говорят о бинарных деревьях! Они показывают вам троянные деревья поиска! Истинные двоичные деревья хранят данные в своих листьях, а не внутренние узлы (кроме ключей для навигации). Некоторые называют эти листовые деревья и делают различие между деревьями node, показанными в учебниках:

J. Nievergelt, C.-K. Вонг: верхние границы для общей длины пути двоичных деревьев, Журнал ACM 20 (1973) 1-6.

Ниже приведено описание книги Питера Брасса о структурах данных.

2.1 Две модели деревьев поиска

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

Если мы сравниваем в каждом node ключ запроса с ключом, содержащимся в node и следуйте левой ветке, если ключ запроса меньше, а правая ветвь если ключ запроса больше, то что произойдет, если они равны? Две модели деревьев поиска:

• Возьмите левую ветвь, если ключ запроса меньше, чем node; в противном случае правой ветки, пока не достигнете листа дерева. Клавиши в интерьере node дерева только для сравнения; все объекты находятся в листьях.

• Возьмите левую ветвь, если ключ запроса меньше, чем node; взять правильную ветвь если ключ запроса больше, чем ключ node; и взять объект, содержащийся в node, если они равны.

Эта незначительная точка имеет ряд следствий:

{В модели 1 базовое дерево представляет собой двоичное дерево, тогда как в модели 2 каждый дерево node действительно является тройным node со специальным средним соседом.

{В модели 1 каждая внутренняя часть node имеет левое и правое поддерево (каждая, возможно, лист node дерева), тогда как в модели 2 мы должны допускать неполное узлы, где может отсутствовать левое или правое поддерево, и только объект сравнения и ключ гарантированно существуют.

Таким образом, структура дерева поиска модели 1 является более регулярной, чем структура дерева модели 2; это, по крайней мере, для реализации, явное преимущество.

{В модели 1 пересечение внутренней части node требует только одного сравнения, тогда как в модели 2 нам нужны два сравнения, чтобы проверить три возможности.

Действительно, деревья одинаковой высоты в моделях 1 и 2 содержат не более приблизительно такое же количество объектов, но нужно вдвое больше сравнений в модели 2, чтобы достичь самых глубоких объектов дерева. Конечно, в модели 2 есть также некоторые объекты, которые достигнуты намного раньше; объект в корне найден с двумя сравнениями, но почти все объекты находятся на глубине уровень.

теоремы. Дерево высоты h и модель 1 содержат не более 2 ^ h объектов. Дерево высоты h и модель 2 содержат не более 2 ^ h + 1 - 1 объектов.

Это легко увидеть, потому что дерево высоты h имеет как левое, так и правое поддеревья a дерево высоты не более h - 1 каждый, а в модели 2 - один дополнительный объект между их.

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

В модели 1 возможно даже, что для сравнения используются клавиши, которые не принадлежат ни одному объекту, например, если объект был удален. От концептуально разделяя эти функции сравнения и идентификации, это не удивительно, и в более поздних структурах нам может потребоваться определить тесты не соответствуют ни одному объекту, просто чтобы получить хорошее разделение поиска пространство. Все ключи, используемые для сравнения, обязательно различны, поскольку в модели 1 дерево, каждый интерьер node имеет непустые левое и правое поддеревья. Таким образом, каждый ключ происходит не чаще двух раз, один раз в качестве ключа сравнения и один раз в качестве идентификационного ключа в лист.

Модель 2 стала предпочтительной версией учебника, потому что в большинстве учебников различие между объектом и его ключом не производится: ключ является объектом. Тогда становится неестественным дублировать ключ в древовидной структуре. Но в все реальные приложения, различие между ключом и объектом очень важно. Один почти никогда не хочет отслеживать только набор чисел; цифры обычно связаны с некоторой дополнительной информацией, которая часто больше самого ключа.

Ответ 12

Возможно, вы слышали, что в этих загадках используется тройной поиск, который включает взвешивание вещей в масштабах. Эти шкалы могут возвращать 3 ответа: слева легче, оба одинаковы или слева тяжелее. Таким образом, в тройном поиске это занимает всего одно сравнение. Однако компьютеры используют логическую логику, в которой есть только 2 ответа. Чтобы выполнить тройной поиск, вам действительно нужно сделать 2 сравнения вместо 1. Я предполагаю, что есть случаи, когда это все еще быстрее, как упоминалось ранее в плакатах, но вы можете видеть, что тройной поиск не всегда лучше, и он более запутан и менее естественен для реализации на компьютере.

Ответ 13

Теоретически минимум k/ln(k) достигается при e, и поскольку 3 ближе к e, чем 2, он требует меньших сравнений. Вы можете проверить, что 3/ln(3) = 2.73.. и 2/ln(2) = 2.88.. Причина, по которой бинарный поиск может быть быстрее, заключается в том, что код для него будет иметь меньше ветвей и будет работать быстрее на современных процессорах.

Ответ 14

Я только что разместил blog об тройном поиске, и я показал некоторые результаты. Я также предоставил некоторые исходные реализации уровня на git repo. Я полностью согласен с каждым из теории в части тройного поиска, но почему бы не попробовать? В соответствии с реализацией эта часть достаточно проста, если у вас есть три года опыта кодирования. Я обнаружил, что если у вас огромный набор данных, и вам нужно искать его много раз, тройной поиск имеет преимущество. Если вы думаете, что можете сделать лучше с тройным поиском, пойдите для этого.

Ответ 15

Несмотря на то, что в обеих деревьях поиска вы получаете ту же самую большую сложность (ln n), разница в константах. Вы должны сделать больше сравнений для тройного дерева поиска на каждом уровне. Таким образом, различие сводится к k/ln (k) для k-арного дерева поиска. Это минимальное значение при e = 2.7, а k = 2 обеспечивает оптимальный результат.