现代浏览器中 Javascript Array.find() 的时间复杂度

Question

由于 array.find() 迭代数组，如果我处理（可能）大型数组，我总是确保有一个索引对象，如下所示：

{ [id:string]: Item }

如果我需要在这些数组中按 id 查找项目。

然而，生活在 V8 时代（以及 Safari 和 Firefox 的类似引擎优化），我想知道是否在幕后，一个简单的 array.find() 已经针对它进行了优化？或者一旦必须执行此操作一次，就会在运行时对其进行优化（创建这样的索引对象）？

现代浏览器是否已经对 O(N) 类型的算法进行了某种优化，通过正确的实现可以将其变为 O(1)？或者我是否过多地考虑了这些浏览器实际上可以/将在幕后做什么？

Answer 1

V8 开发者在这里。的时间复杂度Array.prototype.find是 O(n)（n 是数组的长度），并且可以公平地假设它将保持这种状态。

一般来说，引擎通常不可能提高操作的复杂性等级。在 的情况下Array.prototype.find，您传递的谓词函数可能很关心它被调用的频率：

[1, 2, 3].find((value, index, object) => {
  console.log(`Checking ${value}...`);  // Or any other side effect.
  return value === 42;
});

在这种情况下，引擎别无选择，只能以完全正确的顺序迭代整个数组，因为任何其他操作都会明显破坏程序的行为。

理论上，由于 JS 引擎可以进行动态优化，因此它们可以检查谓词函数，如果它没有副作用，它们可以使用它来构建某种索引/缓存。除了构建这样一个适用于任意谓词的系统的困难之外，这种技术即使确实有效，也只会加速具有相同函数的同一数组的重复搜索速度，如果这种情况完全相同，则会浪费时间和内存。不会再发生。引擎似乎不太可能有足够的信心做出这种预测，以证明投入这些时间和内存是合理的。

经验法则：在处理大型数据集时，选择高效的算法和数据结构是值得的。通常比我们在 SO 问题中看到的微观优化更值得:-)

高度优化/优化的引擎可能能够使您的 O(n) 代码速度提高 10% 到 10 倍。通过切换到 O(log n) 或 O(1) 解决方案，您可以将速度提高几个数量级。这通常是通过做一些引擎不可能做的事情来实现的。例如，您可以保持数组排序，然后对其使用二分搜索——这是引擎无法自动为您做的事情，因为显然未经您的批准，不允许对数组的内容重新排序。正如 @myf 已经在评论中指出的那样：如果您想通过唯一键访问事物，那么使用 aMap可能比使用Array.

也就是说，简单的解决方案往往比我们直观地假设的更容易扩展。与其他地方一样，针对过早优化的标准警告也适用于此。通过数组进行线性搜索通常就可以了，您不需要仅仅因为其中包含三个以上的项目就需要（哈希）映射。如有疑问，请分析您的应用程序以找出性能瓶颈所在。