Двоичный поиск без равномерного распределения

Ответ 1

Существует глубокая связь между бинарным поиском и бинарными деревьями. Бинарное дерево в основном представляет собой "предварительно рассчитанный" двоичный поиск, где точки резания определяются структурой дерева, а не выбираются по мере запуска поиска. И, как выясняется, обработка вероятности "весов" для каждого ключа иногда выполняется с бинарными деревьями.

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

Никлаус Вирт описал это в своей книге "Алгоритмы и структуры данных" в нескольких вариантах (один для Pascal, один для Modula 2, один для Oberon), по крайней мере один из которых доступен для скачивания с его веб-сайт.

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

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

Двоичное дерево, построенное однажды, а затем никогда не изменяемое, может иметь несколько применений, но тот, который может быть эффективно обновлен, еще более полезен. Есть несколько сбалансированных по весу двоичных древовидных структур данных, но я не знаком с ними. Остерегайтесь - термин "сбалансированный вес" обычно используется там, где каждый node всегда имеет вес 1, но весы поддерева приблизительно сбалансированы. Некоторые из них могут быть адаптированы для различных весов node, но я не знаю наверняка.

В любом случае, для двоичного поиска в массиве проблема заключается в том, что можно использовать произвольное распределение вероятности, но неэффективно. Например, у вас может быть массив running-total-of-weight. Для каждой итерации вашего бинарного поиска вы хотите определить точку распространения по принципу "половина пути к вероятности", поэтому вы определяете значение для этого, а затем выполняете поиск в массиве running-total-of-weight. Вы получаете сбалансированный баланс веса для вашего основного бинарного поиска, но вам нужно было выполнить полный бинарный поиск в вашем текущем массиве, чтобы сделать это.

Принцип работает, однако, если вы можете определить эту взвешенную среднюю точку без поиска известного распределения вероятности. Принцип один и тот же - вам нужен интеграл распределения вероятности (заменяющий текущий массив), а когда вам нужна средняя точка, вы выбираете его для получения точного значения центра для интеграла. Это больше проблема алгебры, чем проблема программирования.

Одна проблема с взвешенным бинарным поиском, подобным этому, заключается в том, что худшая производительность хуже - обычно постоянными факторами, но, если распределение искажено достаточно, вы можете в конечном итоге эффективно использовать линейный поиск. Если ваш предполагаемый дистрибутив верен, производительность в среднем случае улучшается, несмотря на случайный медленный поиск, но если ваше предполагаемое распространение ошибочно, вы можете заплатить за это, когда многие поисковые запросы предназначены для элементов, которые вряд ли будут соответствовать этому распределению. В двоичной форме дерева "маловероятные" узлы находятся дальше от корня, чем они были бы в просто сбалансированном (предполагаемое распределение вероятности) двоичного дерева.

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

Ответ 2

Позвольте мне уточнить это. Для двоичного поиска вы хотите:

 Given array A which is sorted, but have non-uniform distribution
 Given left & right index L & R of search range
 Want to search for a value X in A

 To apply binary search, we want to find the index M in [L,R] 
 as the next position to look at.

 Where the value X should have equal chances to be in either range [L,M-1] or [M+1,R]

В общем, вы, конечно, хотите выбрать M, где, по вашему мнению, значение X должно быть в A. Потому что, даже если вы пропустите, половина всего "шанса" будет устранена.

Итак, мне кажется, что у вас есть ожидание распространения. Если бы вы могли сказать нам, что именно вы подразумеваете под "1/x distribution", то может быть, кто-то здесь может помочь вам построить мое предложение.

Позвольте мне привести обработанный пример.

Я буду использовать аналогичную интерпретацию '1/x distribution' как @Leonid Volnitsky

Вот код Python, который генерирует входной массив A

from random import uniform

# Generating input
a,b = 10,20
A = [ 1.0/uniform(a,b) for i in range(10) ]
A.sort()

# example input (rounded)
# A = [0.0513, 0.0552, 0.0562, 0.0574, 0.0576, 0.0602, 0.0616, 0.0721, 0.0728, 0.0880]

Предположим, что значение для поиска:

X = 0.0553

Тогда оцененный индекс X равен:

= total number of items * cummulative probability distribution up to X
= length(A) * P(x <= X)

Итак, как рассчитать P(x <= X)? Это в этом случае просто. Мы возвращаем X обратно к значению между [a, b], которое будем называть

X' = 1/X ~ 18

Следовательно

P(x <= X) = (b-X')/(b-a)
          = (20-18)/(20-10)
          = 2/10

Таким образом, ожидаемая позиция X:

10*(2/10) = 2

Хорошо, и это довольно чертовски точно!

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

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

Ответ 3

Цель двоичного поиска состоит в том, что для отсортированного массива каждый раз, когда вы половину массива вы минимизируете наихудший случай, например. худшее количество проверок, которое вы можете сделать, это log2 (записи). Если вы делаете какой-то "неравномерный" бинарный поиск, где вы делите массив на меньшую и большую половину, если элемент всегда находится в большей половине, вы можете иметь худшее поведение в худшем случае. Итак, я думаю, что бинарный поиск по-прежнему будет лучшим алгоритмом для использования независимо от ожидаемого распределения, просто потому, что он имеет худшее поведение.

Ответ 4

У вас есть вектор записей, скажем [x1, x2, ..., xN], и вам известно о том, что распределение запросов задано с вероятностью 1/x по вектору, который у вас есть. Это означает, что ваши запросы будут проходить с этим дистрибутивом, то есть при каждом совете вы с большей вероятностью возьмете элемент xN.

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

Обратите внимание: это не двоичное дерево поиска, так как вы не делите пространство поиска на два на каждом шаге, а скорее ребалансированное дерево по отношению к вашему шаблону шаблона поиска. Это означает, что в худшем случае поиск может достигнуть O(N). Например, имея v = [10, 20, 30, 40, 50, 60]:

        30
      /    \
    20      50
   /       /  \
 10       40   60

Что можно изменить, или перебалансировать, используя вашу функцию f(x) = 1 / x:

f([10, 20, 30, 40, 50, 60]) = [0.100, 0.050, 0.033, 0.025, 0.020, 0.016]
sort(v, f(v)) = [10, 20, 30, 40, 50, 60]

В новое дерево поиска выглядит следующее:

        10  -------------> the most probable of being taken
      /    \               leaving v = [[20, 30], [40, 50, 60]]
    20      30  ---------> the most probable of being taken
           /  \            leaving v = [[40, 50], [60]]
          40   50 -------> the most probable of being taken
              /            leaving v = [[60]]
             60

Если вы ищете 10, вам нужно только одно сравнение, но если вы ищете 60, вы будете выполнять сравнения O(N), которые не квалифицируют это как двоичный поиск. Как указано @Steve314, самым дальним из полностью сбалансированного дерева, тем хуже будет ваш худший случай поиска.

Ответ 5

Предположим из вашего описания:

• X равномерно распределен
• Y=1/X - это ваши данные, которые вы хотите искать, и хранится в отсортированной таблице
• заданное значение y, вам необходимо выполнить двоичный поиск в приведенной выше таблице.

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

Например, если мы имеем равномерно распределенные значения в диапазоне [0,1], а запрос - 0.25, лучше смотреть не в центр диапазона, а в 1-й квартал диапазона.

Чтобы использовать тот же метод для данных 1/X, сохраните в таблице не Y, а инвертируйте 1/Y. Поиск не для y, а для обратного значения 1/y.

Ответ 6

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

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

В этом обсуждении я буду считать, что данные равномерно выбраны из 1..N и в массиве размером N, индексированном на 1..N. Если он имеет другое решение, например, распределение Zipfian, где значение пропорционально 1/index, вы можете применить обратную функцию для сглаживания распределения, или Fisher Transform часто помогает (см. Википедию).

Изначально у вас есть 1..N как границы, но на самом деле вы можете узнать фактическое значение Min..Max. В любом случае мы будем предполагать, что мы всегда имеем закрытый интервал [Min, Max] для диапазона индексов [L..R], который мы сейчас ищем, и изначально это O (N). Мы ищем ключ K и хотим индекс I, чтобы

[I-R]/[K-Max] = [L-I]/[Min-K] = [L-R]/[Min-Max], например. я = [R-L]/[Max-Min] * [Max-K] + L.

Раунд, чтобы меньший раздел стал больше, а не меньше (чтобы помочь в худшем случае). Ожидаемая абсолютная и среднеквадратичная ошибка равна < √ [R-L] (на основе модели Пуассона/Скеллама или случайной ходьбы - см. Википедию). Таким образом, ожидаемым количеством шагов является O (loglogN).

Наихудший случай может быть ограничен O (logN) несколькими способами. Сначала мы можем решить, какую константу мы считаем приемлемой, возможно, требуя шагов 1. Выполняя шаги loglogN, как описано выше, а затем используя половину, вы достигнете этого для любого такого c.

В качестве альтернативы мы можем изменить стандартную базу b = B = 2 логарифма, так что b > 2. Предположим, что мы берем b = 8, а затем эффективно c ~ b/B. мы можем затем изменить округление выше, так что на этапе k наибольший раздел должен быть не более N * b ^ -k. Viz следит за ожидаемым размером, если мы исключим 1/b из рассмотрения каждого шага, который приводит к худшему случаю b/2 lgN. Это, однако, вернет наш ожидаемый случай в O (log N), так как нам разрешено каждый раз уменьшать небольшой раздел на 1/b. Мы можем восстановить ожидание O (loglog N), используя простой подход к небольшому разделу для шагов loglogN, прежде чем применять ограниченное округление. Это уместно, потому что в пределах ожидаемой локальности для определенного значения распределение равномерно (то есть для любой гладкой функции распределения, например, в этом случае Скеллама, любой достаточно малый отрезок приблизительно линейный с наклоном, заданным его производной при центр отрезка).

Что касается сортированного хэша, я думал, что читал об этом в Кнуте несколько десятилетий назад, но не могу найти ссылку. Метод включает в себя толкание, а не зондирование - (возможно, взвешенный двоичный) поиск, чтобы найти нужное место или промежуток, а затем отталкивать, чтобы освободить место по мере необходимости, а хеш-функция должна уважать порядок. Это нажатие может обернуться, и поэтому нужно пройти второй проход по таблице, чтобы выбрать их все - полезно отслеживать Min и Max и их индексы (чтобы получить вперед или назад упорядоченное начало списка на одном и циклически перевести на другой; они могут также использоваться вместо 1 и N в качестве начальных скобок для поиска, как указано выше, в противном случае 1 и N могут использоваться как суррогаты).

Если коэффициент загрузки alpha близок к 1, то ожидается ожидаемая O (√N) для ожидаемых O (√N) позиций, которая по-прежнему амортизируется до O (1) в среднем. Ожидается, что эта стоимость будет экспоненциально уменьшаться с альфа-I (по предположениям Пуассона), что μ ~ σ ~ √ [Nexp (α)].

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