Зачем использовать бинарный поиск, если есть троичный поиск?
Недавно я слышал о троичном поиске, в котором мы делим массив на 3 части и сравниваем. Здесь будет два сравнения, но это уменьшит массив до n/3. Почему люди не используют это так много?
15 ответов
На самом деле, люди используют k-арные деревья для произвольного k.
Это, однако, компромисс.
Чтобы найти элемент в k-арном дереве, вам нужно выполнить около k*ln(N)/ln(k) операций (помните формулу изменения базы). Чем больше ваше k, тем больше общих операций вам нужно.
Логическое продолжение того, что вы говорите: "Почему люди не используют N-арное дерево для N элементов данных?". Который, конечно, был бы массивом.
Тройной поиск все равно даст вам то же время поиска асимптотической сложности O(log N) и увеличит сложность реализации.
Тот же аргумент можно сказать о том, почему вы не хотите, чтобы поиск квадрацикла или любой другой более высокий порядок.
Поиск по 1 млрд. (От 1 млрд. До 1 000 000 000) отсортированных товаров займет в среднем около 15 сравнений с бинарным поиском и около 9 сравнений с троичным поиском - не большое преимущество. И обратите внимание, что каждое "троичное сравнение" может включать 2 фактических сравнения.
Вот это да. Думаю, ответы с наибольшим количеством голосов скучают по лодке.
Ваш процессор не поддерживает троичную логику как одну операцию; он разбивает троичную логику на несколько шагов двоичной логики. Самый оптимальный код для процессора - это двоичная логика. Если бы были обычные чипы, которые поддерживали троичную логику как одну операцию, вы были бы правы.
B-деревья могут иметь несколько ветвей в каждом узле; B-дерево порядка 3 является троичной логикой. Каждый шаг вниз по дереву будет проводить два сравнения вместо одного, и это, вероятно, приведет к замедлению времени процессора.
B-деревья, однако, довольно распространены. Если вы предполагаете, что каждый узел в дереве будет храниться где-то отдельно на диске, вы будете проводить большую часть своего времени, читая с диска... и ЦП не будет узким местом, но диск будет. Таким образом, вы берете B-дерево со 100000 дочерних элементов на узел, или что-то еще, что едва умещается в одном блоке памяти. B-деревья с таким типом фактора ветвления редко бывают более трех узлов в высоту, и вам потребуется всего три чтения с диска - три остановки в узком месте - для поиска в огромном, огромном наборе данных.
Обзор:
- Тройные деревья не поддерживаются оборудованием, поэтому они работают не так быстро.
- B-tress с порядками намного, намного, намного выше 3 являются общими для оптимизации дисков больших наборов данных; как только вы прошли 2, поднимитесь выше 3.
Что заставляет вас думать, что троичный поиск должен быть быстрее?
Среднее количество сравнений:
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).
Похоже, троичный поиск хуже.
Единственный способ, которым троичный поиск может быть быстрее, чем двоичный поиск, состоит в том, что определение трехстороннего раздела может быть выполнено менее чем в 1,55 раза дороже двухстороннего сравнения. Если элементы хранятся в отсортированном массиве, трехстороннее определение в среднем будет в 1,66 раза дороже двухстороннего определения. Однако, если информация хранится в дереве, стоимость выборки информации высока по сравнению со стоимостью фактического сравнения, а локальность кэша означает, что стоимость случайного выбора пары связанных данных не намного хуже, чем стоимость выборки одного базовые данные, тройное или n-way дерево может значительно повысить эффективность.
Также обратите внимание, что эта последовательность обобщает линейный поиск, если мы продолжим
Binary search
Ternary search
...
...
n-ary search ≡ linear search
Таким образом, в n-арном поиске у нас будет "только одно СРАВНЕНИЕ", которое может принимать до n фактических сравнений.
Тройной поиск может быть эффективно использован на параллельных архитектурах - FPGA и ASIC. Например, если внутренняя память FPGA, необходимая для поиска, составляет менее половины ресурса FPGA, вы можете создать дублированный блок памяти. Это позволило бы одновременно получить доступ к двум разным адресам памяти и выполнить все сравнения за один такт. Это одна из причин, по которой 100 МГц FPGA иногда может опережать 4 ГГц процессор:)
"Тинарный" (троичный?) Поиск более эффективен в лучшем случае, что предполагает поиск первого элемента (или, возможно, последнего, в зависимости от того, какое сравнение вы выполняете первым). Для элементов дальше от конца, который вы проверяете первым, в то время как два сравнения будут сужать массив на 2/3 каждый раз, те же самые два сравнения с двоичным поиском сузят пространство поиска на 3/4.
Добавьте к этому, бинарный поиск проще. Вы просто сравниваете и получаете половину или другую, а не сравниваете, если меньше, чем получаете первую треть, иначе сравниваете, если меньше, чем получаете вторую треть, иначе получаете последнюю треть.
Почти все учебники и веб-сайты о бинарных деревьях поиска на самом деле не говорят о бинарных деревьях! Они показывают вам троичные поисковые деревья! Истинные двоичные деревья хранят данные в своих листьях, а не во внутренних узлах (за исключением ключей для навигации). Некоторые называют эти листовые деревья и делают различие между деревьями узлов, показанными в учебниках:
J. Nievergelt, C.-K. Вонг: верхние границы для общей длины пути двоичных деревьев, журнал 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 стала предпочтительной версией учебника, потому что в большинстве учебников различие между объектом и его ключом не проводится: ключ - это объект. Тогда становится неестественным дублировать ключ в древовидной структуре. Но во всех реальных приложениях различие между ключом и объектом довольно важно. Почти никогда не хочется отслеживать только набор чисел; числа обычно связаны с некоторой дополнительной информацией, которая часто намного больше, чем сам ключ.
Вот некоторые случайные экспериментальные доказательства, которые я вообще не проверял, показывающие, что это медленнее, чем бинарный поиск.
Теоретически минимум k/ln(k) достигается при e, а поскольку 3 ближе к e, чем 2, это требует меньше сравнений. Вы можете проверить это 3/ln(3) = 2.73.. а также 2/ln(2) = 2.88.. Причина, по которой бинарный поиск может быть быстрее, состоит в том, что код для него будет иметь меньше ветвей и будет работать быстрее на современных процессорах.
Хотя вы получаете одинаковую сложность big-O (ln n) в обоих деревьях поиска, различие заключается в константах. Вы должны сделать больше сравнений для троичного дерева поиска на каждом уровне. Таким образом, разница сводится к k/ln(k) для k-арного дерева поиска. Это имеет минимальное значение при e=2,7, а k=2 обеспечивает оптимальный результат.
Я только что опубликовал блог о троичном поиске и показал некоторые результаты. Я также предоставил некоторые реализации начального уровня в своем git-репо. Я полностью согласен со всеми в теоретической части троичного поиска, но почему бы не попробовать? В соответствии с реализацией, эта часть достаточно проста, если у вас есть три года опыта кодирования. Я обнаружил, что если у вас есть огромный набор данных, и вам нужно много раз искать его, у троичного поиска есть преимущество. Если вы думаете, что можете добиться большего успеха с троичным поиском, сделайте это.
Возможно, вы слышали, что троичные поиски используются в тех загадках, которые включают взвешивание вещей на весах. Эти шкалы могут возвращать 3 ответа: левый светлее, оба одинаковы или левый тяжелее. Таким образом, в троичном поиске требуется только 1 сравнение. Однако компьютеры используют булеву логику, которая имеет только 2 ответа. Чтобы выполнить троичный поиск, вам фактически нужно сделать 2 сравнения вместо 1. Я предполагаю, что в некоторых случаях это все еще быстрее, как упоминалось в предыдущих постерах, но вы можете видеть, что троичный поиск не всегда лучше, и это более запутанным и менее естественным для реализации на компьютере.