现代浏览器中 JavaScript Array.find() 的时间复杂度是多少？

Question

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

{ [id:string]: Item }

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

然而，在V8（以及Safari和Firefox的可比引擎优化）时代，我想知道，也许在底层，简单的array.find()已经为此进行了优化？或者将在运行时进行优化（创建这样的索引对象），一旦它只需执行此操作一次？

现代浏览器是否已经具有一些O(N)类型算法的优化，可以通过正确实施变成O(1)？或者我对这些浏览器实际上能够/会在底层做什么想得太多了？

- Sventies

---

现代JS引擎所做的优化并不能“减少复杂性”，因为这几乎是不可能的。拿电话簿举例，把所有页面都弄乱。然后找到一个特定的号码。如何优化这个任务以便立即找到目标，而不是一页一页地查找？这几乎是不可能的。V8可能会优化重复搜索-例如，它可能不会彻底检查前10页以寻找以“B”开头的名称，因为这些页面在后面。如果您想查看某个东西是否对于您的用例而言很慢，请阅读https://ericlippert.com/2012/12/17/performance-rant/。 - VLAZ

你想得太多浏览器在底层会做什么了。如果你知道你将要通过id查找东西，那就使用一个以id为索引的对象。保证O(1)，而不是依赖于特定的find实现... - Heretic Monkey

规范指出该方法应循环遍历所有元素，直到找到一个元素。https://tc39.es/ecma262/multipage/indexed-collections.html#sec-array.prototype.find - Luca Kiebel

如果您保留指向数组项的（假定为）唯一（？）键的“索引”（以便更快地查找），那么使用Map是否更有意义呢？ - myf

@luca 是的，但是除非指定了没有可观察的副作用，只要结果正确，引擎可能仍然会在幕后执行一些未指定的操作（例如，加法不一定是加法，中间值不一定被计算...）。 - Jonas Wilms

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引擎可以进行动态优化，它们可以检查谓词函数，并且如果它没有副作用，它们可以使用它来构建某种索引/缓存。除了构建适用于任意谓词的系统的难度之外，即使这种技术起作用，它也只会加速对相同数组和相同函数进行重复搜索时的搜索，以代价浪费时间和内存，如果这完全相同的情况不会再次发生，那么显然是不划算的。似乎很难让引擎以足够的信心做出这种预测，以证明投资这些时间和内存是有价值的。

一条经验法则是：在操作大型数据集时，选择高效的算法和数据结构是值得的。通常比我们在Stack Overflow问题中看到的微观优化要更具价值 :-)

高度优化的引擎可能能够使您的O(n)代码的速度快10%至10倍不等。通过转换为O(log n)或O(1)解决方案，您可以将其加速数倍。通常通过做一些引擎无法自动完成的操作来实现。例如，您可以保持数组已排序，然后在其上使用二分搜索--这是引擎无法自动为您完成的，因为显然它不允许重新排序您的数组内容而没有经过您的批准。正如@myf在评论中指出的那样：如果您想通过唯一键访问某些内容，则使用Map可能比使用Array更好。

也就是说，简单的解决方案往往比我们直觉所认为的更具可扩展性；我们对过早优化的标准警告也适用于这里以及其他任何地方。通过数组进行线性搜索通常就足够了，只有在有三个或更多项时才需要（散列）图。当存在疑虑时，请分析您的应用程序以找出性能瓶颈所在。

- jmrk