现代浏览器中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引擎可以进行动态优化，所以可以检查谓词函数，如果没有副作用，就可以使用它建立某种索引/缓存。除了构建这样一个适用于任意谓词的系统的困难之外，这种技术即使确实工作，也只会加快对具有相同功能的同一个数组的重复搜索，如果这种完全相同的场景不再发生，则会浪费时间和内存。一个引擎似乎不太可能有足够的信心做出这一预测，从而证明这一时间和记忆的投资是合理的。

经验法则是：在对大型数据集进行操作时，选择高效的算法和数据结构是值得的。通常比我们在这么多问题中看到的微观优化更有价值：)

经过高度优化/优化的引擎可能会使您的O(n)代码达到10%到10倍的速度。通过切换到您端的O(log )或O(1)解，您可以将其速度提高一个数量级。这通常是通过做一些引擎不可能做的事情来实现的。例如，您可以对数组进行排序，然后对其使用二进制搜索--这是引擎无法自动为您所做的事情，因为很明显，未经您的批准，不允许重新排序数组的内容。正如@myf已经在一条评论中指出的那样:如果您想通过一个惟一的键访问事物，那么使用Map可能比使用Array更好。

尽管如此，简单的解决方案往往比我们直觉中假设的更好；对于过早优化的标准警告就像其他地方一样适用于这里。在数组中进行线性搜索通常很好，您不需要(散列)映射，仅仅因为其中包含三个以上的项。当有疑问时，请分析一下你的应用程序，找出性能瓶颈所在。