동일 코드가 JS 클로저 라이브러리보다 느립니다.

Question

일부 수정 사항으로 이진 검색 알고리즘을 만들고 싶습니다. 그래서 Google의 폐쇄 라이브러리에서 코드를 가져 와서 이러한 수정 작업을 시작했습니다. 수정 된 버전은 속도가 느려졌을 때 속도가 느려질 수 있다고 생각되는 부분을 천천히 꺼 냈습니다. 내가 남긴 것은 SIMPLER 버전의 이진 검색 알고리즘이며 Chrome이나 Firefox에서 여전히 몇 배 더 느립니다. 무엇이 이것을 일으킬 수 있습니까? 이 테스트 페이지를 살펴보십시오. 내가 말하는 것을보기 위해 출처를 조사하십시오.

https://dl.dropboxusercontent.com/s/4hhuq4biznv1jfd/SortedArrayTest.html

이

구글의 버전입니다. 사람들이 당신이 binarySearch 방법에 비교 자 기능을 제공하지 않는 경우 ... comparefn 기능과의 일을 생각하는 것 때문에

이

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

는 다음을 사용

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

이

내 버전 기본 비교 기능 :

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

코드를 보지 않고 응답하지 마십시오. 추측은별로 도움이되지 않습니다.

Answer 1

구현에 버그가 있습니다. 그것은 포함

var midValue = array[midValue] 

이있는 대신

var midValue = array[middle] 

해야한다.

분명히 잘못된 결과로 버그를 드러내지 않도록 데이터 세트에 불충분했지만 성능 문제 만있었습니다.