为什么遍历数组比 JavaScript 的原生 `indexOf` 方法快得多？

Question

为什么循环遍历一个数组比JavaScript本身的indexOf方法快那么多？是否有错误或我没有考虑到的东西？我本来期望本地实现会更快。

                For Loop        While Loop      indexOf
Chrome 10.0     50,948,997      111,272,979     12,807,549
Firefox 3.6     9,308,421       62,184,430      2,089,243
Opera 11.10     11,756,258      49,118,462      2,335,347   

http://jsben.ch/#/xm2BV

- Lime

---

如果你尝试使用字符串，这个结果就变得更加值得怀疑了。我用一个while循环进行了一些简单的测试 http://jsperf.com/indexof-vs-while-loop ，欢迎改进测试，但在得出结论之前考虑字符串比较甚至更大的数组是值得的。 - Frug

Frug，你使用一个固定顺序的数组，然后称它为“随机”... 相关的XKCD漫画https://www.xkcd.com/221/ - Job

表格中的数字代表什么？是完成操作所需的平均时间，还是在一定时间内完成操作的次数？或者是其他什么？ - Ben Sutton

Answer 1

距离那时已经过去了5年，浏览器发生了很多变化。现在，indexOf的性能已经提高，并且肯定比任何其他自定义替代品更好。

Chrome版本49.0.2623.87（64位）

- Pierre Maoui

---

证明这个问题无效。 - a3.14_Infinity

@a3.14_Infinity 过时了，但也许并不无效。 - Lime

您能否提供您使用的测试链接？屏幕截图本身并没有显示实现方式，鉴于我从 https://jsperf.com/thor-indexof-vs-for 得到了截然不同的结果。 - agweber

@agweber，这个测试在indexOf周围创建了一个“for循环”，并将其与另一个包含break的for循环进行比较...我们在这里讨论的是indexOf本身与for/while的比较。 - Pierre Maoui

谢谢@Lime。你说得完全正确。网络上仍然有很多信息称for循环是最快的。当我发现这个帖子时，我还在犯愁并不太相信这一点。感谢上帝我找到了它！因为仍然存在错误信息，所以我差点重新设计了我的解决方案。这篇文章真是太棒了。 - Courtney Foster

Answer 2

好的，看到其他基准测试结果，我对大多数开发人员进行基准测试的方式感到困惑。

抱歉，但是这种做法会导致极其错误的结论，因此我必须进行一些元分析并对提供的答案进行评论。

这里其他基准测试的问题

测量在永远不变的数组中查找元素777的位置，始终导致索引117似乎非常不合适，我很难解释为什么。您无法从这样一个过度特定的基准测试中合理地推断任何内容！我能想到的唯一类比是对一个人进行人类学研究，然后将发现称为该人所居住国家的整个文化的概述。其他基准测试也不太好。

更糟糕的是：接受的答案是一个没有链接到使用的基准测试的图像，因此我们无法控制该基准测试的代码是否正确（我希望它是原本在问题中的jsperf链接的截图，并在新的jsben.ch链接中进行了编辑）。这甚至不是原始问题的解释：为什么一个比另一个表现更好（这本身就是一个高度可争议的陈述）。

首先，您应该知道并非所有基准测试网站都是平等的-一些网站可能会由于其自身框架干扰计时而对某些类型的测量增加显着误差。

现在，我们应该比较不同的线性搜索数组方法的性能。先思考一下算法本身：

- 查看数组中给定索引处的值。 - 将该值与另一个值进行比较。

- 如果相等，则返回索引。 - 如果不相等，则移动到下一个索引并比较下一个值。

这就是整个线性搜索算法，对吧？

因此，一些链接的基准测试比较已排序和未排序的数组（有时错误地标记为“随机”，尽管每次迭代顺序相同 - 相关XKCD）。显然，这不会以任何方式影响上述算法 - 比较运算符不会看到所有值都单调递增。

是的，在将线性搜索与二进制或插值搜索算法的性能进行比较时，有序与无序的数组可能会有所影响，但这里没有人这样做！

此外，所有显示的基准测试都使用固定长度的数组，并且具有固定的索引。这只告诉您indexOf在该确切长度的确切索引中找到的速度有多快 - 如上所述，您不能从中概括任何内容。

以下是将问题中链接的基准测试复制到perf.zone（比jsben.ch更可靠）的结果，但进行了以下修改：

• 每次运行时，我们随机选择数组的一个值，这意味着我们假设每个元素被选中的概率相等
• 我们对100个和1000个元素进行基准测试
• 我们比较整数和短字符串。

https://run.perf.zone/view/for-vs-while-vs-indexof-100-integers-1516292563568

https://run.perf.zone/view/for-vs-while-vs-indexof-1000-integers-1516292665740

https://run.perf.zone/view/for-vs-while-vs-indexof-100-strings-1516297821385

https://run.perf.zone/view/for-vs-while-vs-indexof-1000-strings-1516293164213

这是我机器上的结果：

https://imgur.com/a/fBWD9

正如您所看到的，结果会根据使用的基准和浏览器而发生 drastical 变化，并且每个选项在至少一个方案中都获胜：缓存长度 vs 未缓存长度，while 循环 vs for 循环 vs indexOf。

因此，在这里没有通用答案，并且随着浏览器和硬件的更改，这肯定会在将来发生变化。

你甚至应该对此进行基准测试吗？

应该注意的是，在您继续构建基准测试之前，您应确定线性搜索部分是否首先成为瓶颈！它可能并不是，如果是，更好的策略可能是使用不同的数据结构来存储和检索数据，或者使用不同的算法。

这并不是说这个问题是不相关的 - 这很少见，但线性搜索性能很重要；我碰巧有一个例子：通过嵌套对象（使用字典查找）或嵌套数组（需要线性搜索）建立速度 prefix trie 的构造/搜索。

如可以在此Github评论中看到, 基准测试涉及各种浏览器和平台上的各种现实和最佳/最坏情况的负载。只有经过所有这些才能得出关于预期性能的结论。在我看来，对于大多数现实情况，通过数组进行线性搜索比查找字典更快，但最坏情况的性能更差，甚至会导致脚本冻结（并且易于构建），因此将其标记为“不安全”方法以向其他人发出信号，让他们考虑代码将被使用的上下文。

Jon J's answer也是一个很好的例子，可以退一步思考真正的问题。

当您必须进行微基准测试时该怎么办

所以让我们假设我们知道我们已经做好了功课，并确定我们需要优化我们的线性搜索。

那么重要的是我们期望找到元素的最终索引（如果有的话），正在搜索的数据类型以及支持哪些浏览器。

换句话说：任何索引都同样可能被找到（均匀分布），还是更有可能集中在中间（正态分布）？我们会在开头或接近结尾处找到数据吗？我们的值是否保证在数组中，还是只有一定百分比的时间？百分之几？

我正在搜索一个字符串数组吗？对象数字？如果它们是数字，它们是浮点值还是整数？我们正在尝试优化较旧的智能手机、最新的笔记本电脑还是卡在IE10的学校台式机？

这是另一个重要的事情：不要优化最佳性能，而是优化现实中的最坏性能。如果您正在构建一个Web应用程序，其中10％的客户使用非常老旧的智能手机，请针对此进行优化；他们的体验将是无法忍受的糟糕性能，而微小的优化则浪费在最新一代旗舰手机上。

针对您应用线性搜索的数据以及您所处的上下文，自问以下问题。然后制定符合这些标准的测试用例，并在代表您支持的目标的浏览器/硬件上进行测试。

- Job

Answer 3

可能是因为实际的indexOf实现不仅仅是通过数组循环。您可以在此处查看Firefox的内部实现：

https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/indexOf

有几件事情可能会减慢循环速度，这些都是为了保证代码的健壮性：

• 数组被重新转换为对象
• fromIndex 被转换为数字
• 他们使用 Math.max 而不是三元运算符
• 他们使用 Math.abs

- user578895

---

那里发布的代码是一个 polyfill，不是实现中的实际代码。 - Barmar

@Barmar -- 说得对，但是polyfill试图有一个非常类似于原始实现的实现方式，而且在确定性能方面通常是一个不错的参考。 - user578895

Polyfill试图产生类似的结果，但我怀疑它与实现非常相似。特别是，实现可以利用JavaScript实现内部的高效机制。 - Barmar

@Barmar -- 我的意思不是这个。无论具体机制如何，polyfill都需要执行与内部实现相同的健全性检查。出于这个目的，它回答了最初的问题“为什么本地速度较慢”。 - user578895

@Barmar - jsperf 显然已经崩溃了，所以我无法检查这个问题，但考虑到已经进行了每秒100M次的基准测试，我猜测原始问题是在一个非常小的数组上运行的。不过你说得对，这最终会变得微不足道。 - user578895

Answer 4

indexOf函数进行了许多类型检查和验证，而for循环和while循环则忽略了这些检查。

下面是indexOf算法：

https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/indexOf

编辑：我猜想indexOf在处理大数组时更快，因为它在循环之前缓存了数组的长度。

- shelman

---

是的，我也想到了同样的事情，但它似乎没有更快的表现。http://jsperf.com/js-for-loop-vs-array-indexof/10 即使这是一个不在数组中的值。 - Lime

Answer 5

请再运行一次测试，使用我所做的编辑。我已经增加了数组的大小，并使你要查找的索引也更大了。在大型数组中，indexOf可能是更快的选择。 http://jsben.ch/#/xm2BV 根据更多的测试，基于我正在使用的Safari版本（5.0.3），indexOf似乎比for循环更快，但在其他几乎所有情况下都比较慢。

- Tyler Biscoe

---

for循环在Chrome浏览器中仍然更快。我很好奇你使用while循环会得到什么结果。我已经将这两种循环合并在这里：http://jsperf.com/js-for-loop-vs-array-indexof/10 - Lime

Answer 6

值得注意的是，如果你只是想保持一份项目清单并检查是否存在（例如避免将重复的ID添加到数组中），那么使用一个带有反映每个ID的键的对象会更快。如果你认为我错了，请与数组+ indexOf进行比较。对于对象方法，我们谈论的是181ms，而数组indexOf方法需要1分钟。

var objs = []
var i_uid = {} // method 1
var a_uid = [] // method 2
var total_count = 100000, idLen = 5
var ts, te, cObj = 0

// method 1
ts = new Date()
while (cObj < total_count) {
    var u = uid(idLen),
        o = {
            uid: u,
            text: 'something',
            created: new Date()
        }
    if (!i_uid[u]) { // ensure unique uids only
        objs.push(o)
        i_uid[u] = cObj // current array position as placeholder
        cObj++
    }
    else {
        console.log('unique violation [duplicate uid', u, ']')
    }
}
te = new Date()
console.log('loaded ' + total_count + ' with object method in', (te - ts), 'ms')

i_uid = {} // free-up
cObj = 0 // reset
objs = [] // reset

// method 2
ts = new Date()
while (cObj < total_count) {
    var u = uid(idLen),
        o = {
            uid: u,
            text: 'something',
            created: new Date()
        }
    if (a_uid.indexOf(u) == -1) { // ensure unique uids only
        objs.push(o)
        a_uid.push(u)
        cObj++
    }
    else {
        console.log('unique violation [duplicate uid', u, ']')
    }
}
te = new Date()
console.log('loaded ' + total_count + ' with array + indexOf method in', (te - ts), 'ms')

function uid(l) {
    var t = '',
        p = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789',
        pl = p.length
    for (var i = 0; i < l; i++)
        t += p.charAt(Math.floor(Math.random() * pl))
    return t
}

- Jon J