为什么循环数组比JavaScript的本机`indexOf`快得多？

Question

为什么循环数组比JavaScript的本机`indexOf`快得多？

为什么循环数组比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

Run Code Online (Sandbox Code Playgroud)

http://jsben.ch/#/xm2BV

Answer 1

Pie*_*oui 81

5年后,浏览器发生了很多变化.现在,indexOf性能已经提高,并且绝对优于任何其他自定义替代方案.

Chrome版本49.0.2623.87(64位)

@ a3.14_Infinity过时可能无效 (39认同)
您可以链接到用于此的测试吗？屏幕快照本身未显示实现，并且给出<https://jsperf.com/thor-indexof-vs-for>的结果，我得到的结果截然不同。 (2认同)
@agweber，这个测试在 indexOf 周围创建了一个“for 循环”，并将它与另一个包含一个 for 的其他 for 进行比较......我们在这里谈论的是 indexOf 本身与 for/while (2认同)

Answer 2

Job*_*Job 13

好的,看看其他基准测试,我对大多数开发人员似乎都在进行基准测试的方式感到头疼.

道歉,但它的完成方式会导致可怕的错误结论,因此我必须稍微进行一下,并对所提供的答案进行评论.

这里的其他基准有什么问题

测量在一个永不改变的数组中找到元素777的位置,总是导致索引117看起来是不合适的,原因很明显,我无法解释原因.你不能从这样一个过于具体的基准来合理地推断出任何东西!我能想出的唯一类比就是对一个人进行人类学研究,然后将调查结果称为对这个人所居住的国家整个文化的概括性概述.其他基准并没有好多少.

更糟糕的是:接受的答案是没有链接到所用基准测试的图像,所以我们无法控制该基准测试的代码是否正确(我希望它是最初在jsperf链接的屏幕截图)问题,后来编辑出来支持新的jsben.ch链接).它甚至不是对原始问题的解释:为什么一个人比另一个人表现更好(一个备受争议的声明开始).

首先,您应该知道并非所有基准测试站点都是相同的 - 由于其自身的框架干扰了时序,某些测量站点会对某些类型的测量添加重大错误.

现在,我们应该比较在阵列上进行线性搜索的不同方式的性能.想想算法本身一秒钟:

查看给定索引到数组的值.
将值与另一个值进行比较.
- 如果相等,则返回索引
- 如果它不相等,移动到下一个索引并比较下一个值.

这是整个线性搜索算法,对吗？

因此,一些链接的基准测试比较了排序和未排序的数组(有时不正确地标记为"随机",尽管每次迭代的顺序相同 - 相关的XKCD).很明显,这不会以任何方式影响上述算法 - 比较运算符并未看到所有值都单调增加.

是的,在将线性搜索的性能与二进制或插值搜索算法进行比较时,有序vs未排序的数组可能很重要,但这里没有人这样做!

此外,所有显示的基准测试都使用固定长度的数组,其中包含固定的索引.所有这些告诉你的是如何快速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

正如你所看到的,结果变化显着依赖于基准,所使用的浏览器,并在场景中的至少一个每个选项胜:缓存长度VS未缓存的长度,while循环,相较于循环VS indexOf.

所以这里没有通用的答案,随着浏览器和硬件的变化,这肯定会在未来发生变化.

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

应该注意的是,在继续构建基准之前,您应该确定线性搜索部分是否是开始的瓶颈!它可能不是,如果是,更好的策略可能是使用不同的数据结构来存储和检索您的数据,和/或不同的算法.

这并不是说,这个问题是不相关的-它是罕见的,但它可以发生线性搜索性能事项; 我碰巧有一个例子:建立构造/搜索通过嵌套对象(使用字典查找)或嵌套数组(需要线性搜索)构造的前缀trie的速度.

可以看出这个github评论,基准测试涉及各种浏览器和平台上的各种现实和最佳/最坏情况的有效载荷.只有在经历了所有这些之后,我才能得出关于预期绩效的结论.在我的情况下,对于大多数现实情况,通过数组的线性搜索比字典查找更快,但最坏情况的性能更糟糕到冻结脚本(并且易于构造),因此实现被标记为一种"不安全"的方法,向其他人发出信号,表明他们应该考虑使用代码的上下文.

Jon J的答案也是回过头来思考真正问题的一个很好的例子.