我用一些 TypeScript 写了二分查找算法,并想测试其与 array.indexOf 的性能。我的结果表明 TypeScript 版本较慢。我尝试在网上可用的基准测试中测量性能,结果显示二分查找要快得多(应该是这样的)。这段代码 / TypeScript / 我尝试获取函数性能的方式有什么问题吗?
我尝试过基准测试,结果看起来完全不同。http://jsben.ch/VBjt0 以下是我的代码。
我还尝试使用这个实用函数和
但结果甚至更糟。使用相同的测试数组,使用
我尝试过基准测试,结果看起来完全不同。http://jsben.ch/VBjt0 以下是我的代码。
function binarySearch(
sortedArray: number[],
seekElement: number,
): number {
let startIndex = 0;
let endIndex: number = sortedArray.length - 1;
while (startIndex <= endIndex) {
const mid = startIndex + Math.floor((endIndex - startIndex) / 2);
const guess = sortedArray[mid];
if (guess === seekElement) {
return mid;
} else if (guess > seekElement) {
endIndex = mid - 1;
} else {
startIndex = mid + 1;
}
}
return -1;
}
const indexOfSearch = function(arr, element) {
return arr.indexOf(element);
};
const testArray = [...Array(100000).keys()].map(x => x + 1);
console.time('binarySearch');
binarySearch(testArray, 4400) // binarySearch: 0.134ms
console.timeEnd('binarySearch');
console.time('indexOfSearch');
indexOfSearch(testArray, 4400) // indexOfSearch: 0.029ms
console.timeEnd('indexOfSearch');
我还尝试使用这个实用函数和
performance.now
:import { performance } from 'perf_hooks';
export const getPerformance = (func: Function, ...params) => {
const start = performance.now();
func(params);
const end = performance.now();
console.log(`${func.name} took ${end - start} milliseconds to execute`);
}
但结果甚至更糟。使用相同的测试数组,使用
getPerformance
函数进行二分搜索需要 11 毫秒,而使用 indexOf 只需要 0.003 毫秒。这很奇怪,我不知道自己做错了什么。感谢任何帮助。
Math.floor()
的调用替换为((endIndex - startIndex) / 2) | 0
或者(endIndex - startIndex) >> 1
。 - undefined.indexOf()
方法的速度之快感到困惑,与你有同样的感受。我个人觉得这真是令人惊讶。 - undefined4400
作为目标?这接近于包含100000
个元素的数组的开头,所以函数调用Math.floor
和其他二分搜索的开销可能总是被优化的线性搜索所掩盖。在数组中选择一个随机数。即便如此,当我运行你的基准测试时,二分搜索比预期更快。如果我使用最坏情况,indexOf
需要979毫秒,而binarySearch
只需要32毫秒。 - undefinedindexOf
函数有一个非常优化的本地实现。你可以尝试多次运行测试来进行预热,正如Pointy所提到的。 - undefined