Здравствуйте!
Решил попробовать использовать сервис
jsperf.app для проверки скорости выполнения алгоритма. Алгоритм заключается в поиске количества вхождения элемента в массив. Есть две версии для проверки..
Исходные данные :
function randomArr(len){
const arr = [];
for(let k=0; k<len; k++){
arr.push( Math.floor( Math.random()*10 ) );
};
return arr;
};
const arr = randomArr(1000000).sort((a,b)=>{return a-b});
Медленная версия :
function countOccurrences2(arr, el){
let result = 0;
for(let k=0; k<arr.length; k++){
if(arr[k]===el){
result++;
};
};
return result;
};
Быстрая версия ( использующая алгоритм бинарного поиска ) :
function binarySearch(arr,searchedItem){
// debugger;
let leftPointer = 0,
rightPointer = arr.length;
for(let k=0; k<arr.length;k++){
let mid = Math.floor((rightPointer+leftPointer)/2);
if(searchedItem>arr[mid]){
leftPointer = mid;
continue;
};
if(searchedItem<arr[mid]){
rightPointer = mid;
continue;
};
return mid;
};
return -1;
};
function countOccurrences1(arr, el){
let elPosition = binarySearch(arr, el);
if(elPosition===-1){
return 0;
};
// let counter = 1;
let leftPointer = elPosition;
rightPointer = elPosition;
while(arr[leftPointer]===el){
leftPointer--;
};
while(arr[rightPointer]===el){
rightPointer++;
};
return rightPointer - leftPointer - 1 ;
};
Собственно не понятные результаты , они противоположенные в браузере при использовании
console.time() и на сайте
jsperf
browser test :
jsperf test :
Не могу найти причину такого поведения, я пользуюсь сервисом
jsperf не долго, но тем не менее уже проверял там алгоритмы, и работало всё вроде бы корректно.
