Я хотел создать алгоритм бинарного поиска с некоторыми модификациями. Поэтому я взял код из библиотеки закрытия Google и начал делать эти модификации. Моя модифицированная версия казалась медленнее, чем должна быть, поэтому я медленно удалил все, что, по моему мнению, могло повлиять на скорость. То, что у меня осталось, это УПРОЩЕННАЯ версия алгоритма бинарного поиска, и он все еще был в несколько раз медленнее как в Chrome, так и в Firefox. Что может быть причиной этого? Взгляните на эту тестовую страницу. Проверьте источник, чтобы понять, о чем я говорю.
https://dl.dropboxusercontent.com/s/4hhuq4biznv1jfd/SortedArrayTest.html
Это версия гугла.
goog.array.binarySearch_ = function(arr, compareFn, isEvaluator, opt_target,
opt_selfObj) {
var left = 0; // inclusive
var right = arr.length; // exclusive
var found;
while (left < right) {
var middle = (left + right) >> 1;
var compareResult;
if (isEvaluator) {
compareResult = compareFn.call(opt_selfObj, arr[middle], middle, arr);
} else {
compareResult = compareFn(opt_target, arr[middle]);
}
if (compareResult > 0) {
left = middle + 1;
} else {
right = middle;
// We are looking for the lowest index so we can't return immediately.
found = !compareResult;
}
}
// left is the index if found, or the insertion point otherwise.
// ~left is a shorthand for -left - 1.
return found ? left : ~left;
};
Это моя версия:
var search = function(array, num){
var left = 0; // inclusive
var right = array.length; // exclusive
while (left < right) {
var middle = (left + right) >> 1;
var midValue = array[midValue];
if (num > midValue) {
left = middle + 1;
} else {
right = middle;
}
}
return left;
};
Поскольку люди, кажется, думают, что это что-то с функцией comparefn... когда вы не предоставляете функцию сравнения для метода binarySearch, он использует следующую функцию сравнения по умолчанию:
goog.array.defaultCompare = function(a, b) {
return a > b ? 1 : a < b ? -1 : 0;
};
goog.array.binarySearch = function(arr, target, opt_compareFn) {
return goog.array.binarySearch_(arr,
opt_compareFn || goog.array.defaultCompare, false /* isEvaluator */,
target);
};
Пожалуйста, не отвечайте, не глядя на код. Догадки не очень помогают.
compareFn
, которые он использует для установки либо влево, либо вправо, ваш код получает данные из массива, и что-то подсказывает мне, что ваш код выполняет гораздо больше итераций в цикле while. Поместите счетчик внутри цикла, чтобы увидеть, сколько раз он выполняется в каждом цикле while. - person adeneo   schedule 17.11.2014