问题 Javascript性能:reduce()vs for-loop


我在尝试 这个Codewars挑战 问题涉及找到一个数的除数,然后计算这些除数的平方和。我找到了解决这个问题的两种方法。

第一种方法是基于另一个Stackoverflow问题 找到所有除数的总和 起初看起来很聪明:

function divisorsSquared(n) {
  // create a numeric sequence and then reduce it
  return [...Array(n+1).keys()].slice(1)
   .reduce((sum, num)=>sum+(!(n % (num)) && Math.pow(num,2)), 0);
}

我使用的第二种方法是使用一个简单的for循环:

function divisorsSquared(n) {
  var sum = 0;
  for(var i = 1; i<= n; i++){
     if(n % i === 0) sum += Math.pow(i,2); 
  }
  return sum;
}

现在我注意到第一种方法明显慢于第二种方法,而且很快 jsperf测试 证实了这一点。

我的问题是:为什么第一种方法如此慢,哪种方法更适合生产代码?

在Codewars上我注意到,对于许多挑战,使用类似的数组方法有一些聪明的单行解决方案。作为初学者,即使性能更差,这些解决方案是否可以被认为是比for-loops更好的实践?


8227
2018-04-22 06:41


起源

如果查看代码,第一个使用构造函数,然后迭代扩展,然后迭代获取键,然后迭代切片,然后迭代以减少......第二个迭代...一次。 - adeneo
我没有想到这一点,但现在看起来很明显。谢谢! - Miguel G.


答案:


功能或命令式方法在JS中有所作为。势在必行永远胜利。 然而,真正的事情是大部分时间,更好的算法是赢家。你的代码是一种天真的方法。您可以通过检查整数直到目标值的平方根来调整它以使其更好地工作,并且每次检查将获得两个答案。如果目标是100,如果2是股息,那么100/2也必须是股息。所以检查是公平的 Math.sqrt(100) - 1 并小心处理10,以免两次考虑。

因此,现在具有减少的功能性解决方案击败了必要的天真解决方案。

function divisorsSquared(n) {
  var sn = Math.sqrt(n);
  return Array.from({length:~~sn-1},(_,i) => i+1)
              .reduce((s,m) => n%m ? s : s + m*m + (n/m)*(n/m), 0) + (n%sn ? 0 : sn*sn);
}
var result = 0;
console.time("functional and tuned");
result = divisorsSquared(1000000);
console.timeEnd("functional and tuned");
console.log("for input: 1000000 the result is:",result);


function dvssqr(n) {
  var sum = 0;
  for(var i = 1; i<= n; i++){
     if(n % i === 0) sum += Math.pow(i,2); 
  }
  return sum;
}

console.time("imperative and naive");
result = dvssqr(1000000);
console.timeEnd("imperative and naive");
console.log("for input: 1000000 the result is:",result);


2
2018-04-22 13:28





  • Array(n+1) 分配一个包含n + 1个元素的数组, Array(n+1).keys() 在创建的数组的索引上返回一个迭代器,但是扩展运算符 [...Iterator] 帮助将这个迭代器“解包”到另一个数组中,然后最终 slice(1) 从索引开始复制第二个创建的数组 1 它用数字分配另一个数组(第三个) 0 丢弃。所以这是3个分配,但有2个被分配。你的 for-loop 不分配任何数组,它是O(n)中的简单遍历,只有2个分配 i 和 sum,所以效率更高
  • sum+(!(n % (num)) && Math.pow(num,2)) 与...基本相同 if(n % i === 0) sum += Math.pow(i,2); 但是 if 方法更具可读性。如果我是法官,我会选择第二种方法,因为它更有效,但它更有利于可读性。

6
2018-04-22 07:07





查看代码,for循环显然不那么复杂,更具可读性。

考虑到您在团队中工作,您团队成员的最大数量将立即知道代码正在做什么。 有些人不得不抬头看看 reduce() 方法是,但他们也会知道发生了什么。 所以在这里,for循环更容易让其他人阅读和理解。

另一方面,本机数组函数 (filter(), map(), reduce()) 将节省您编写一些额外的代码 并且性能也较慢。

对于初学者,我认为for循环应该比原生数组函数更好。


3
2018-04-22 07:51