在JavaScript数组中找到最小元素的位置


发布者 1518409521  发布时间 1402212268378
关键字 JS学习  JavaScript 

在JavaScript数组中找到最小元素的位置

注*  之前有篇文章介绍过数据遍历的性能比较: for in 比for loop慢至少20倍 ,这是另外一篇比较数组查找性能的例子,通过对手工/indexOf/reduce三者的比较,再次映证,内置函数不一下比手工写的函数快。


今天的小程序甚至不是一个程序。这只是一个函数。

问题陈述如下:

给定一个非空的JavaScript数字数组,找到最小值的索引。(如果最小值出现不止一次,那么任何此类索引是可以接受的。)


一个解决方案是进行简单的手动操作,模拟用纸笔如何执行操作:首先,你假设第一个元素是赢家,然后你遍历其他元素。如果你的下一个元素小于第一个元素,那么你声明这个元素是新的临时的赢家。

function indexOfSmallest(a) {
 var lowest = 0;
 for (var i = 1; i < a.length; i++) {
  if (a[i] < a[lowest]) lowest = i;
 }
 return lowest;
}

另一种解决方案是使用reduce内联函数本质来运行循环,所以你只需要提供初始猜测和if语句的业务逻辑。

function indexOfSmallest(a) {
 return a.reduce(function(lowest, next, index) {
                   return next < a[lowest] : index ? lowest; },
                 0);
}

第三个解决方案是使用JavaScript 内联函数找到最小的元素,然后将元素转换为其索引。

function indexOfSmallest(a) {
 return a.indexOf(Math.min.apply(Math, a));
}


哪一个最快呢?

好吧,首先,你确定哪一个是最快之前,您需要确保他们都是正确的。你发现的一件事是,一旦数组变得很大最小/索引技术会失败,至少它在IE浏览器和Firefox上是这样的。(在我的例子中,Internet Explorer和Firefox分别放弃了元素数量约为250000和500000的数组)。那是因为你开始触及引擎的数量限制参数,这个参数你可以传递给一个函数。调用250000个元素的数组相当于最少调用250000个函数参数。

  • 所以我们会限制自己的数组长度最多为250000。
  • 分享结果之前,我想让你猜猜哪个算法你认为将是最快和哪个是最慢的。

  

仍然在等。

 

我预计手工版本是最后一名,因为,毕竟,这是手工做的一切。我预计使用减少函数的版本稍快,因为它把一些工作交给了内联函数(尽管上面的函数调用可能否定了它的改进)。我预计min/ indexOf版本是最快的,因为几乎所有的工作在内联函数中完成,并且两次数据遍历的开销将会由内联函数的一些改进性能构成。


这里有三个版本在不同大小的数组上的计时,它是运行在随机数据上。我正常运行了好几次,所以这个结果与CPU速度是独立的。


每个数组元素相对运行时间

元素

手工

reduce

min/indexOf

Internet Explorer 9

100,000

1.000

2.155

2.739

200,000

1.014

2.324

3.099

250,000

1.023

2.200

2.330

Internet Explorer 10

100,000

1.000

4.057

4.302

200,000

1.028

4.057

4.642

250,000

1.019

4.091

4.068


你感到惊讶吗?我肯定我很惊讶!

我不仅完全向后又运算了一遍,但手工版本胜利的界限的是超出了我的想象的。

(这表明要知道程序的性能,唯一途径肯定是坐下来测量它。)

我认为正在发生的是,JavaScript优化器可以很好地优化手工代码,因为它非常简单。 循环体没有函数调用,只是一行,在外面没关系的。使用内联函数的版本以从优化器隐藏一些信息结束。(毕竟,优化器不能提前预测是否有人覆盖Array.prototype.reduce或者Math.prototype.min的默认实现,所以不能盲目的内联调用。)结果是,在IE9浏览器上运行手动版本可以快两倍,在IE10上运行速度超过四倍。

我弄错了,因为我想起了JavaScript太像一种解释型语言。在一个纯粹的解释型语言,翻译的开销大约与你让它做的事情的数量成正比,而不是与做这些事情是多么难成正比。就像一个对每一笔交易固定的服务费,不管交易是100美元50美分。你因此试图做一笔大的买卖(调用复杂的内联函数)而不是大量的小买卖(读一个数组元素,比较两个值,增加一个变量,一个变量复制到另一个)。

福利:我在Firefox上做了这个测试,因为我碰巧比较方便。


每个数组元素相对运行时间

元素

手工

reduce

min/indexOf

Firefox 16

100,000

1.000

21.598

3.958

200,000

0.848

21.701

2.515

250,000

0.839

21.788

2.090


相同的数据收集在Firefox 16(这听起来是可笑的老旧版本,因为到这篇文章到达队列头部的时候,Firefox将发行523版本)展示了一个不同的形象,尽管胜利者是相同的。数组大小增加的时候手动循环和min/ indexOf变得更高效。这表明,当你增加数据集的大小,固定的开销逐渐变得不那么重要。


一件比较突出的事是,reduce()方法表现地比其他方法差。我的猜测是,设置函数调用(为了内联函数和脚本之间的转换)开销是很大的,并且JavaScript引擎实现器没有花任何时间优化这种案例,因为reduce在实际代码中不常使用。


更新:我夸大了我构造一个好的故事叙述的天真。就像我书的序言中指出的那样,我的故事也许并不完全正确,但他们已经足够真实。我当然知道JavaScript 如今是JITTED(即时解释执行),它改变了计算方式。(同时,是隐藏的数组副本。)

 





回复 (2)
  • #
  • #1 真忐忑 1402884341000
    [/奋斗] 谢谢分享
  • #2 f2e.be 1409649644312

    翻译的好菜,机器翻译的吧

微信扫码 立即评论