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

https://stackoverflow.com/questions/3498382

29-09-2019
|

Вопрос

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

Решение

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

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

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

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

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

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

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

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

Ух ты. Топ проголосовал ответы пропустить лодку на этом, думаю.

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

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

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

Обзор:

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

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

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

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

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

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

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

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

Итак, в N-ARY поиска у нас будет «только сравнить», что может принять фактические сравнения.

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

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

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

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

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

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

Следующее об этом происходит из книги Питера Ласстра о структурах данных.

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

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

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

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

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

{В модели 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 ответа: слева зажигалка, оба одинаковы, или осталось тяжелее. Так что в тройном поиске это требуется только 1 сравнение. Однако компьютеры используют логическую логику, которая имеет только 2 ответа. Чтобы сделать тройной поиск, вам действительно нужно сделать 2 сравнения вместо 1. Я думаю, что есть некоторые случаи, когда это все еще быстрее, как более ранние плакаты, но вы можете видеть, что тройной поиск не всегда лучше, и это Более запутанные и менее естественные для реализации на компьютере.

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

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

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

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

Не связан с StackOverflow