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 是数组的长度），并且可以公平地假设它会保持这种状态。

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

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

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

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

根据经验：在处理大型数据集时，选择高效的算法和数据结构是值得的。 通常比 micro-optimizations 更值得我们在 SO 问题中看到了很多 :-)

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

更好

也就是说，简单的解决方案往往比我们直觉上假设的更容易扩展；对过早优化的标准警告在这里和其他地方一样适用。线性搜索数组通常很好，您不需要（散列）映射只是因为其中包含三个以上的项目。如有疑问，请分析您的应用以找出性能瓶颈所在。

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

Time complexity of Javascript Array.find() in modern browsers

javascript

browser

arrays

v8

javascript-engine