在 TypeScript 中的二分查找与 indexOf 相比如何正确提高性能

Question

我用一些 TypeScript 写了二分查找算法，并想测试其与 array.indexOf 的性能。我的结果表明 TypeScript 版本较慢。我尝试在网上可用的基准测试中测量性能，结果显示二分查找要快得多（应该是这样的）。这段代码 / TypeScript / 我尝试获取函数性能的方式有什么问题吗？

我尝试过基准测试，结果看起来完全不同。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 毫秒。这很奇怪，我不知道自己做错了什么。感谢任何帮助。

- Kamil Staszewski

---

你可以尝试将 Math.floor() 的调用替换为 ((endIndex - startIndex) / 2) | 0 或者 (endIndex - startIndex) >> 1。 - undefined

此外，JavaScript 运行时（大多数现代运行时）最终会编译您的搜索函数，因此最好多次尝试性能测试。 - undefined

我对.indexOf()方法的速度之快感到困惑，与你有同样的感受。我个人觉得这真是令人惊讶。 - undefined

为什么你选择4400作为目标？这接近于包含100000个元素的数组的开头，所以函数调用Math.floor和其他二分搜索的开销可能总是被优化的线性搜索所掩盖。在数组中选择一个随机数。即便如此，当我运行你的基准测试时，二分搜索比预期更快。如果我使用最坏情况，indexOf需要979毫秒，而binarySearch只需要32毫秒。 - undefined

0.133毫秒与0.147毫秒之间仍然没有太大的差异。在这种情况下，线性扫描只比二分查找慢大约10%。我猜indexOf函数有一个非常优化的本地实现。你可以尝试多次运行测试来进行预热，正如Pointy所提到的。 - undefined

Answer 1

对于长度为的数组，二分搜索在最坏情况下需要检查₂个条目，而线性扫描在最坏情况下需要检查个条目。对于= 100,000，就像您的示例一样，在最坏情况下，您预计在线性扫描中要检查的条目数量是二分搜索的6000倍左右。显然，实现细节可以通过某些数字因素改变，但如果您不看到两者之间有很大差异，我会感到非常惊讶。

正如评论中提到的那样，您应该在获得平均性能的感觉之前多次运行搜索。任何小代码的单次运行都可能具有一堆开销，这可能会使任何差异变得微不足道。这里是一种可能的方法:

const N = 10000;
const seekElements = [...Array(N)].map(k => Math.floor(Math.random() * len * 1.1));

console.time('binarySearch');
for (let el of seekElements) {
    binarySearch(testArray, el)
}
console.timeEnd('binarySearch'); // 6 ms / N = 0.6 microseconds per search

console.time('indexOfSearch');
for (let el of seekElements) {
    indexOfSearch(testArray, el)
}
console.timeEnd('indexOfSearch'); // 3215 ms / N = 320 microseconds per search

我已经设置了一个由10,000个随机元素组成的数组进行查找，其中约10%的元素不在数组中。要查找的特定元素分布将对搜索时间产生影响，因为在两种搜索策略中，不存在于数组中的值将是最坏情况的性能。通过测试10,000次搜索而不是1次，我们可以将计时器的结果除以10,000以获得每次搜索的平均时间。

无论如何，在我的浏览器上进行测试，我发现indexOf()平均搜索时间为320微秒，而二进制搜索时间为0.5微秒。二进制搜索至少提高了500倍。您可以尝试通过使用x>>1而不是Math.floor(x/2)来加速实现，但我不确定这对您有多重要。

好的，希望这有所帮助。

游乐场链接到代码

- jcalz

---

感谢您提供的精彩见解！ - undefined

Answer 2

indexOf()

是用二进制编写的，它被称为“硬编码”函数，具有 JavaScript 的软接口。

probably it's also binary search

JavaScript的开发者并不傻。通过操作码、令牌和虚拟沙盒来访问变量，你永远无法达到光速（C）。

如果你在纯JavaScript中进行了良好的基准测试，你应该在真实的浏览器或节点程序中实现，而不仅仅是在沙盒中。

JavaScript关注的是性能，当平均笔记本电脑还没有配备8GB内存时。它更多关注的是简单地完成任务，让计算机代劳。如今，计算机比人类便宜。

如果你想要真正好的基准测试结果，可以使用WebAssembly编写代码，或者用C编译成WebAssembly。或者编写Node.js扩展。但在花费时间的同时，请考虑以下事项：能够完成任务的能力远比几毫秒更重要。

- MniNi

---

这个回答不够连贯。indexOf绝不是二分查找（binary search），详见此链接：https://github.com/v8/v8/blob/0445fa297127d1b22cbfc39bc48a0b7b4e42031e/src/runtime/runtime-array.cc#L318。 - undefined

如果数组没有排序，如何使用二分查找来完成呢？ - undefined