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;
}

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

35 голосов | спросил Reid 27 MaramSun, 27 Mar 2011 03:32:47 +04002011-03-27T03:32:47+04:0003 2011, 03:32:47

5 ответов


17

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

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

  • При выполнении вышеописанной точки становится достаточным завершение как «не найденное», когда beginning > end, а затем проверьте, что вы смотрите на начальное или конечное значение. Также ваш подход может дать ложный отрицательный результат при поиске «B» в следующей ситуации.

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

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

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

I think то, что вы видите в масштабируемости, связано с тем, что код с ошибкой в ​​googled делает меньше сравнений, а parseInt делает сравнение более дорогим. Уменьшенное количество сравнений является более значительным для небольших наборов данных, но для больших наборов данных стоимость сравнения становится более значимой.

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

ответил Brian Reichle 27 MaramSun, 27 Mar 2011 09:43:23 +04002011-03-27T09:43:23+04:0009 2011, 09:43:23
16

Измените Math.floor((beginning + end) / 2) на ((beginning + end) >> 1) означает одно и то же и много быстрее:

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

ответил James Khoury 30 AM00000070000002531 2011, 07:14:25
9

Честно говоря, я никогда не был поклонником (правда). На мой взгляд, лучше всего разместить свой основной условный для читаемости и стиля. Вот версия, которую я написал некоторое время назад для ударов, если это помогает - моя цель здесь была в основном уместной в чириканье, но я украсил ее для этого примера. Заметьте, что я использую Math.floor вместо parseInt - мои тесты показали, что Math.floor был примерно в два раза быстрее, когда был 0,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;
}
ответил binarymax 27 MarpmSun, 27 Mar 2011 17:29:25 +04002011-03-27T17:29:25+04:0005 2011, 17:29:25
0

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

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

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

ответил Stephen C 23 AMpSat, 23 Apr 2011 07:31:11 +040031Saturday 2011, 07:31:11
0

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

Однако ваш код может ссылаться на элемент, находящийся за концом массива. Например. Если длина массива равна нулю, вы будете разыскивать arr [0]. В javascript это может быть приемлемым, но для программиста C это выглядит странно.

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

ответил Cesium62 12 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 12 Sep 2013 11:21:29 +0400 2013, 11:21:29

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132