Эффективный Двоичный Поиск


Моя реализация:

Array.prototype.binarySearchFast = function(search) {

  var size = this.length,
      high = size -1,
      low = 0;

  while (high > low) {

    if (this[low] === search) return low;
    else if (this[high] === search) return high;

    target = (((search - this[low]) / (this[high] - this[low])) * (high - low)) >>> 0;

    if (this[target] === search) return target;
    else if (search > this[target]) low = target + 1, high--;
    else high = target - 1, low++;
  }

  return -1;
};

Нормальной Реализации:

Array.prototype.binarySearch = function(find) {
  var low = 0, high = this.length - 1,
      i, comparison;
  while (low <= high) {
    i = Math.floor((low + high) / 2);
    if (this[i] < find) { low = i + 1; continue; };
    if (this[i] > find) { high = i - 1; continue; };
    return i;
  }
  return null;
};

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

Я удивлялся, если кто-то может думать ни о каких сценариях, где это будет медленнее, чем первоначальная.

Обновление: Извините за плохие примеры. Я уже сделал их немного проще для понимания и настройки некоторые тесты на см. Этот тест jsperf. Смотрите здесь:

http://jsperf.com/binary-search-2

Я вижу около 75% улучшение, используя мой метод.



Комментарии
7 ответов

Мой совет: не возись с чем-то, что это было хорошо и действительно проверили :-)

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

Власть бинарный поиск, и другие o(зарегистрируйте N) тип алгоритмов, заключается в том, что вы распоряжаться половиной оставшегося пространства поиска с каждой итерацией. Другими словами, если исходное пространство поиска (размер массива) был 1000, первая итерация удаляет 500 из них.

Каких-либо изменений "медиана" (разделитель между тем, что ты держишь в поисках места и то, что вы утилизации), которые вы выбираете во время итерации имеет потенциал , чтобы улучшить или ухудшить производительность. Например, поставив точку в 25% имеет потенциал, чтобы уменьшить пространство поиска еще быстрей (если вы правы) или медленнее (если вы правы).

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

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

[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 500, 1000]

чтобы увидеть это в действии.

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

Аналогично, если вы искали 14, вы можете сначала проверить элементы примерно на 1,4%, Марка (14/1000), который, вероятно, будет первым элементом, несмотря на то, что это прямо на другом конце.

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

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

16
ответ дан 14 октября 2011 в 11:10 Источник Поделиться

Зацените
http://en.wikipedia.org/wiki/Interpolation_search

Особенно пункт, в котором сказано:

Каждая итерация приведенный выше код требует от пяти до шести сравнения (экстренно из-за повторений необходимо различать три состояния < > и = с помощью парных сравнений при отсутствии трехстороннего сравнения) плюс какая-то лажа арифметике, в то время как двоичный поиск алгоритм может быть записан с одного сравнения в каждой итерации и использует только тривиальные арифметические операции с целыми числами. Тем самым поиск массив из миллиона элементов не более двадцати сравнений (в отношении обращений к медленной памяти, где элементы массива хранятся);
* чтобы победить эту интерполяцию поиск как написано выше, будет разрешено не более трех итераций. *

6
ответ дан 13 февраля 2014 в 01:02 Источник Поделиться

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

Во всяком случае, "быстрое" внедрение будет происходить медленнее, если у вас нет равномерного распределения в массиве. Например, глядя на 5 в [1,2,3,4,5,6,7,10000] бы сделать что-то вроде четырех итераций вместо одного.

5
ответ дан 14 октября 2011 в 06:10 Источник Поделиться

Если вы хотите ускорить бинарный поиск, "развернуть" цикл. Для 1000 элементов цикла в 10 раз. 10 незаметные фрагменты кода удалить "зацикливание накладные". Если у вас есть конкретный поиск, а чем вообще можно заменить все вычисления диапазона с литеральными значениями (иначе их замена переменной).

Set the mid-point "low"

if key less than value at ( mid-point + largest-mid-point )
add largest-mid-point to mid-point
if key less than value at ( mid-point + 2nd-largest-mid-point )
add 2nd-largest-mid-point to mid-point
if key less than value at ( mid-point + 3rd-largest-mid-point )
add 3rd-largest-mid-point to mid-point
etc

Разработана 31 год назад с Кобол, обнаружен позже в книге Жемчужины программирования Джон Бентли (и это, наверное, ответ на упражнение 24 в Кнут сортировка и поиск по бинарным поиском).

До сих пор работает, в COBOL, сегодня :-)

Из-за "силы два" он работает даже с очень большими таблицами без огромного количества дополнительного кода.

Редактировать: я всегда использовал "двоичный" ряд записей в моей таблицами для поиска. Бентли показывает 1000 записей, "завязав" со средней точкой поправки к правой границе, чтобы не выйти "за пределы" стола. Это дает "внахлест" с помощью двоичного средние точки, но последствия этого против реальных середины у меня не было возможности посмотреть.

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

Редактировать: после "раскручивания" не современный язык, а учитывая то, что я не знаю, как "дорого" это может быть для вас, и применяются ли они в JavaScript и крошечные инструкции по схронам, но:

if (this[target] === search) return target;
else if (search > this[target]) low = target + 1, high--;
else high = target - 1, low++;


  1. Сначала проверить на равенство. Равенство-это наименее вероятный исход, так это должно быть переупорядочены (вы изменили свой заказ от "нормальной" реализации).

  2. "низкая = цель" я предполагаю, что будет быстрее ", чем низкий = цели + 1", похожие на "минус". "высокое" идет медленнее, чем оставить "высокое" один совсем, похожие на "высокой++". Вы опираетесь на "кроссовер" эти причины для завершения поиска с отказом. Если вы работаете на другой, более простой, способ завершения поиска, вы можете сэкономить несколько инструкций из драгоценных кэш.

    (((search - this[low]) / (this[high] - this[low])) * (high - low))

  3. \$\фрац{В}{С - Б} = \фрац{В}{С} - \Б$

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

  5. Если вы позволите завершить цикл "естественно" (то есть вы узнайте, как упоминалось выше), вы можете удалить остальные проверки на равенство внутри цикла.

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

ОК, Есть много иронии здесь. Вот некоторые вещи, которые вы можете исследовать, чтобы увидеть, где они могут привести вас. Все они могут оказаться бесполезными для вас, но вы никогда не знаете, пока вы попробовать. Или ты? Опять эта ирония.

2
ответ дан 28 января 2013 в 02:01 Источник Поделиться

Нормальной реализации короче и легче следовать.

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

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

1
ответ дан 14 октября 2011 в 09:10 Источник Поделиться

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

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

0
ответ дан 14 октября 2011 в 06:10 Источник Поделиться

А вы попробуйте выполнить алгоритм с массивом, который имеет только 1 элемент (например, А=[1])? Если вы ищите значение 1, это даст ложное, или в данном случае -1, потому что низкая == высокая и тело цикла никогда не входил, несмотря на значение 1 является частью массива. Это может быть быстрее, но не сможет доставить правильный ответ по крайней мере в одном случае.

0
ответ дан 3 декабря 2013 в 02:12 Источник Поделиться