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

Question

Я недавно слышал о троичном поиске, в котором мы делим массив на 3 части и сравниваем. Здесь будет два сравнения, но это уменьшит массив до n / 3. Почему люди не используют это так много?

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

Answer 4

Ничего себе.Думаю, что ответы с наибольшим количеством голосов на этом не сочтут нужным.

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

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

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

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

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

Answer 5

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

Answer 6

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

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

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).

Так выглядитвроде троичный поиск хуже.

Answer 7

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

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

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

Answer 8

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

Answer 9

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

Answer 10

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

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 имеет как левое, так и правое поддеревья a дерево высотой не более h - 1 каждое, а в модели 2 один дополнительный объект между им.

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

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

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