Javascript performance: reduce() vs for-loop

Question

I was attempting this Codewars challenge and the problem involves finding the divisors of a number and then calculating the sum of these divisors squared. I found two approaches to this problem.

The first approach is based on another Stackoverflow questions about finding the sum of all divisors and seems clever at first:

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);
}

The second approach I used was using a simple for-loop:

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

Now I noticed that the first approach is significantly slower than the second and a quick jsperf test confirms this.

My questions are: Why is the first approach so much slower and what approach is preferable in production code?

On Codewars I notice that for many challenges there are clever one-line solutions using similar array methods. As a beginner, may such solutions be considered better practice than for-loops, even if performance is worse?

Answer 1

• Array(n+1) allocates an array with n + 1 elements, Array(n+1).keys() returns an iterator over the created array's indices, but the spread operator [...Iterator] helps "unwrap" this iterator into yet another array, then finally slice(1) comes along to copy the secondly created array starting at index 1 which allocates yet another array (third one) with the number 0 discarded. So that were 3 allocations but 2 were dicarded. Your for-loop does not allocate any arrays, it is a simple traversal in O(n) with only 2 allocations for i and sum, so it is more efficient
• sum+(!(n % (num)) && Math.pow(num,2)) is essentially the same as if(n % i === 0) sum += Math.pow(i,2); but the if approach is way more readable. If I were the judge, I would pick the second approach because it is more memory efficient, yet it favors readability.

Answer 2

Looking into the code, for loop is obviously less complex and more readable.

Consider you are working within a team, maximum number of your team members will know what the code is doing right away. Some will have to look up what the reduce() method is, but then they'll also know what's going on. So here, a for loop is easier for others to read and understand.

On the other side, native array functions (filter(), map(), reduce()) will save you from writing some extra code and also slower in performance.

For a beginner, I think for-loops should be better over native array functions.

Answer 3

Functional or imperative approaches makes a difference in JS. Imperative always wins. Yet, the real thing is most of time a better algorithm is the winner. Your code is a naive approach. You can tune it to work much better just by checking the integers up until the square root of the target value and you will get two answers per check. If target is 100 if 2 is a dividend then 100/2 must be a dividend too.. So it's fair to check up to Math.sqrt(100) - 1 and handle 10 with care in order to not consider it twice.

Accordingly now the functional solution with reduce beats the imperative naive solution.

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);