OurJS


OurJS-我们的JS, 我们的技术-IT文摘; 专注JS相关领域;
我们热爱编程, 我们热爱技术;我们是高大上, 有品味的码农;

欢迎您订阅我们的技术周刊


我们会向您分享我们精心收集整理的,最新的行业资讯,技术动态,外文翻译,热点文章;
我们使用第三方邮件列表向您推送,我们不保存您的任何个人资料,注重您的隐私,您可以随时退订,

欢迎分享您的观点,经验,技巧,心得

让我们一起找寻程序员的快乐,探索技术, 发现IT人生的乐趣;


本网站使用缓存技术每次加载仅需很小流量, 可在手机中流畅浏览;
如果您发现任何BUG,请即时告知我们: ourjs(at)ourjs.com

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


分享到


分类 JS学习   关键字 JavaScript   发布 1518409521  1402212268378
注意 转载须保留原文链接,译文链接,作者译者等信息。  

在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(即时解释执行),它改变了计算方式。(同时,是隐藏的数组副本。)

 

原文地址: 点此
评论 ( Beta版 )
OnceDoc 您自己的企业内容管理系统——文档、流程、知识库、报表、网盘All In One

访问404页面,寻找丢失儿童
 热门文章 - 分享最多
  1. 是什么让Node.js比Java更快?
  2. 我不想雇佣女性
  3. 现在,你为什么应该学Node.js
  4. DevOps:全能开发是如何扼杀程序员的
  5. Google正在拖互联网的后腿
  6. JavaScript中NaN的秘密
  7. 使用集群(recluster)扩展多线程Node.JS
  8. jQuery:在一个回调中处理多个请求
  9. 在JavaScript中创建命名空间的几种写法
  10. 在JavaScript中判断整型的N种方法
  11. 用 OnceAir 搭建个人Git/Svn/照片备份服务器,每年电费7块钱

 相关阅读 - JS学习
  1. 在JavaScript中创建命名空间的几种写法
  2. JavaScript中NaN的秘密
  3. jQuery:在一个回调中处理多个请求
  4. 使用集群(recluster)扩展多线程Node.JS
  5. 抛弃jQuery,深入原生的JavaScript
  6. 使用Backbone构建精美应用的7条建议
  7. 在jQuery API文档中并未提及的get用法,只有读了源码才会知道哦
  8. 如何在一个VPS上连接Node.js到一个MongoDB数据库?
  9. 用Orchestrate 5步快速创建Node.js应用
  10. iFrame的妙用

 关键字 - JavaScript
  1. node.js含有%百分号时,发送get请求时浏览器地址自动编码的问题
  2. 少年,不要滥用箭头函数啊:JS中lambda表达式的优缺点和使用场景
  3. 用JavaScript获取当月第一天和最后一天
  4. 让pre和textarea等HTML元素去掉滚动条自动换行自适应文本内容高度
  5. ES6中的Map与JSON的相互转化(序列和持久化)
  6. Facebook发布全新JavaScript引擎Hermes:越来越像Java字节码,JS要统一全端?
  7. 在嵌入式设备树莓派上编译QuickJS教程:一个C语言编写的极简JavaScript引擎
  8. 为什么我不建议你将JavaScript作为主力语言
  9. 使用JavaScript的Proxy监听对象属性变化并进行类public/private的访问控制
  10. Node.JS中UDP打洞穿透内网路由,架设内网服务器技术详解及源码

 欢迎订阅 - 技术周刊

我们热爱编程, 我们热爱技术; 我们是高端, 大气, 上档次, 有品味, 时刻需要和国际接轨的码农; 欢迎您订阅我们的技术周刊; 您只需要在右上角输入您的邮箱即可; 我们注重您的隐私,您可以随时退订.
加入我们吧! 让我们一起找寻码农的快乐,探索技术, 发现IT人生的乐趣;


 关注我们

我们的微信公众号: ourjs-com
打开微信扫一扫即可关注我们:
IT文摘-程序员(码农)技术周刊

ourjs官方微信号