База 3 или более поиска? [Дубликат]

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

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

Что заставляет вас думать, что поиск по 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).

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

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

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

Ничего себе. Я думаю, что верхние голосовые ответы пропускают лодку.

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

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

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

:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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