在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速度是独立的。

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

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

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

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

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

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

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

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

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

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

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