JavaScript-код бинарного поиска


Я написал реализацию бинарного поиска в JavaScript раньше ради удовольствия, но я заметил, что моя версия была существенно отличаются от тех, кто нашел на Google. Вот пример бинарного поиска я нашел на Google (скопировано здесь для борьбы ссылке сгниет):

Array.prototype.binarySearch = function(find, comparator) {
    var low = 0, high = this.length - 1,
        i, comparison;

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

Большинство других реализаций на Google очень похожи. Но в моей, я не вычитаем одно из низкого/высокого и продолжать оттуда. Вместо этого, я разделить массив пополам и продолжить деление в соответствующую сторону пополам, пока не достигнет правильного значения. Код:

function binary_search_iterative(arr, ele) {
    var beginning = 0, end = arr.length,
        target;
    while (true) {
        target = Math.floor((beginning + end) / 2);
        if ((target === end || target === beginning) && arr[target] !== ele) {
            return -1;
        }
        if (arr[target] > ele) {
            end = target;
        } else if (arr[target] < ele) {
            beginning = target;
        } else {
            return target;
        }
    }
}

Я написал рекурсивный стиле, но в тестировании я нашел этот итеративный версия была быстрее.

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

Мое правильное мышление? Может ли это быть сделано в лучшую сторону?

Мне тоже не нравится это:

if ((target === end || target === beginning) && arr[target] !== ele) {
    return -1;
}

И мне было интересно, если есть хороший способ, чтобы устранить его или рефакторинг функции, где она чище в целом.



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

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


  • При сопоставлении между Арр[цель] и Эле, если они не совпадают, то вы не должны включать цели в рамках следующей итерации (отсюда и +/- 1). Это может уменьшить количество сравнений, хотя эффект является более значительным на небольших наборов данных.

  • Когда после предыдущего пункта, это будет достаточно завершить как "не нашли", когда начало > конца , а затем проверить, что вы ищете в начале или в конце стоимость. Также ваш подход может дать ложноотрицательный, когда ищу "Б" В следующей ситуации.

        target
    |
    v
    ... A B
    ^ ^
    | |
    | end
    beginning

    В этой ситуации, потому что цель === начало и arr[цель] !== Б, она возвращает -1.


  • В гугле код использует parseInt, я не уверен, как это влияет на правильность, но я подозреваю, что это отрицательно сказывается на производительности.

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

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

17
ответ дан 27 марта 2011 в 05:03 Источник Поделиться

Изменения По Математике.пол((начало + конец) / 2) к ((Начало + Конец) >> 1) означает то же самое и намного быстрее:

http://jsperf.com/code-review-1480

16
ответ дан 30 августа 2011 в 03:08 Источник Поделиться

Честно говоря, я никогда не был фанатом в то время как(правда). На мой взгляд его лучше положить ваши основные условные там читабельность и стиль. Вот версия, которую я написал некоторое время назад для пинков, если это поможет - моя цель здесь была в основном сторона в твиттере - но я предоставил ее на этом примере. Заметьте, я использую математику.пол вместо parseInt - мои тесты показали, математике.пол был примерно вдвое быстрее, когда есть .5, и немного быстрее, когда сделано целое число. Эта версия может выглядеть странно (троичной верхним присваивается -2, когда игра найдена), но опять же это был байт эксперимент бритья.

Array.prototype.binarysearch = function (o) {
var l = 0, u = this.length, m;
while ( l <= u ) {
if ( o > this[( m = Math.floor((l+u)/2) )] ) l = m+1;
else u = (o == this[m]) ? -2 : m - 1;
}
return (u == -2) ? m : -1;
}

9
ответ дан 27 марта 2011 в 01:03 Источник Поделиться

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


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

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

0
ответ дан 23 апреля 2011 в 03:04 Источник Поделиться

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

Ваш код может ссылаться на элемент за концом массива, однако. Е. Г. Если длина массива равна нулю, вы разыменования модуль arr[0]. В JavaScript, это может быть приемлемо, но для программистов, это выглядит странно.

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

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