Fastest JavaScript summation

JavascriptArraysFunction

Javascript Problem Overview

What is the fastest way to sum up an array in JavaScript? A quick search turns over a few different methods, but I would like a native solution if possible. This will run under SpiderMonkey.

Thinking very inside-the-box I have been using:

var count = 0;
for(var i = 0; i < array.length; i++)
{
    count = count + array[i];
}

I'm sure there is a better way then straight iteration.

Javascript Solutions

Solution 1 - Javascript

You should be able to use reduce.

var sum = array.reduce(function(pv, cv) { return pv + cv; }, 0);

Source

And with arrow functions introduced in ES6, it's even simpler:

sum = array.reduce((pv, cv) => pv + cv, 0);

Solution 2 - Javascript

#Improvements
###Your looping structure could be made faster: 

   var count = 0;
   for(var i=0, n=array.length; i < n; i++) 
   { 
      count += array[i]; 
   }

This retrieves array.length once, rather than with each iteration. The optimization is made by caching the value.


###If you really want to speed it up: 

   var count=0;
   for (var i=array.length; i--;) {
     count+=array[i];
   }

This is equivalent to a while reverse loop. It caches the value and is compared to 0, thus faster iteration.

For a more complete comparison list, see my JSFiddle.
Note: array.reduce is horrible there, but in Firebug Console it is fastest.

#Compare Structures I started a JSPerf for array summations. It was quickly constructed and not guaranteed to be complete or accurate, but that's what edit is for :)

Solution 3 - Javascript

While searching for the best method to sum an array, I wrote a performance test.

In Chrome, "reduce" seems to be vastly superior

I hope this helps

// Performance test, sum of an array
  var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
  var result = 0;
// Eval
  console.time("eval");
  for(var i = 0; i < 10000; i++) eval("result = (" + array.join("+") + ")");
  console.timeEnd("eval");
// Loop
  console.time("loop");
  for(var i = 0; i < 10000; i++){
    result = 0;
    for(var j = 0; j < array.length; j++){
      result += parseInt(array[j]);
    }
  }
  console.timeEnd("loop");
// Reduce
  console.time("reduce");
  for(var i = 0; i < 10000; i++) result = array.reduce(function(pv, cv) { return pv + parseInt(cv); }, 0);
  console.timeEnd("reduce");
// While
  console.time("while");
  for(var i = 0; i < 10000; i++){
    j = array.length;
    result = 0;
    while(j--) result += array[i];
  }
  console.timeEnd("while");

eval: 5233.000ms

loop: 255.000ms

reduce: 70.000ms

while: 214.000ms

Solution 4 - Javascript

Or you could do it the evil way.

var a = [1,2,3,4,5,6,7,8,9];

sum = eval(a.join("+"));

;)

Solution 5 - Javascript

The fastest loop, according to this test is a while loop in reverse

var i = arr.length; while (i--) { }

So, this code might be the fastest you can get

Array.prototype.sum = function () {
    var total = 0;
    var i = this.length; 
    
    while (i--) {
        total += this[i];
    }

    return total;
}

Array.prototype.sum adds a sum method to the array class... you could easily make it a helper function instead.

Solution 6 - Javascript

For your specific case, just use the reduce method of Arrays:

var sumArray = function() {
    // Use one adding function rather than create a new one each
    // time sumArray is called
    function add(a, b) {
        return a + b;
    }

    return function(arr) {
        return arr.reduce(add);
    };
}();

alert( sumArray([2, 3, 4]) );

Solution 7 - Javascript

Based on this test (for-vs-forEach-vs-reduce) and this (loops)

I can say that:

1# Fastest: for loop

var total = 0;

for (var i = 0, n = array.length; i < n; ++i)
{
    total += array[i];
}

2# Aggregate

For you case you won't need this, but it adds a lot of flexibility.

Array.prototype.Aggregate = function(fn) {
    var current
        , length = this.length;

    if (length == 0) throw "Reduce of empty array with no initial value";

    current = this[0];

    for (var i = 1; i < length; ++i)
    {
        current = fn(current, this[i]);
    }

    return current;
};

Usage:

var total = array.Aggregate(function(a,b){ return a + b });

Inconclusive methods

Then comes forEach and reduce which have almost the same performance and varies from browser to browser, but they have the worst performance anyway.

Solution 8 - Javascript

I tried using performance.now() to analyze the performance of the different types of loops. I took a very large array and found the sum of all elements of the array. I ran the code three times every time and found forEach and reduce to be a clear winner.

// For loop

let arr = [...Array(100000).keys()]
function addUsingForLoop(ar){
  let sum = 0;
  for(let i = 0; i < ar.length; i++){
    sum += ar[i];
  }
   console.log(`Sum: ${sum}`);
   return sum;
}
let t1 = performance.now();
addUsingForLoop(arr);
let t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 42.17500000959262 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 44.41999999107793 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 49.845000030472875 milliseconds"

// While loop

let arr = [...Array(100000).keys()]
function addUsingWhileLoop(ar){
let sum = 0;
let index = 0;
while (index < ar.length) {
  sum += ar[index];
  index++;
}
  console.log(`Sum: ${sum}`)
  return sum;
}
let t1 = performance.now();
addUsingWhileLoop(arr);
let t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 44.2499999771826 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 44.01999997207895 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 41.71000001952052 milliseconds"

// do-while

let arr = [...Array(100000).keys()]
function addUsingDoWhileLoop(ar){
let sum = 0;
let index = 0;
do {
   sum += index;
   index++;
} while (index < ar.length);
   console.log(`Sum: ${sum}`);
   return sum;
}
let t1 = performance.now();
addUsingDoWhileLoop(arr);
let t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 43.79500000504777 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 43.47500001313165 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 47.535000019706786 milliseconds"

// Reverse loop

let arr = [...Array(100000).keys()]
function addUsingReverseLoop(ar){
   var sum=0;
   for (var i=ar.length; i--;) {
     sum+=arr[i];
   }
   console.log(`Sum: ${sum}`);
   return sum;
}
let t1 = performance.now();
addUsingReverseLoop(arr);
let t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 46.199999982491136 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 44.96500000823289 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 43.880000011995435 milliseconds"

// Reverse while loop

let arr = [...Array(100000).keys()]
function addUsingReverseWhileLoop(ar){
    var sum = 0;
    var i = ar.length; 
    while (i--) {
        sum += ar[i];
    }
    console.log(`Sum: ${sum}`);
    return sum;
}
var t1 = performance.now();
addUsingReverseWhileLoop(arr);
var t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 46.26999999163672 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 42.97000000951812 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 44.31500000646338 milliseconds"

// reduce

let arr = [...Array(100000).keys()]
let t1 = performance.now();
sum = arr.reduce((pv, cv) => pv + cv, 0);
console.log(`Sum: ${sum}`)
let t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 4.654999997001141 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 5.040000018198043 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 4.835000028833747 milliseconds"

// forEach

let arr = [...Array(100000).keys()]
function addUsingForEach(ar){
  let sum = 0;
  ar.forEach(item => {
    sum += item;
  })
    console.log(`Sum: ${sum}`);
    return sum
}
let t1 = performance.now();
addUsingForEach(arr)
let t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 5.315000016707927 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 5.869999993592501 mienter code herelliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 5.405000003520399 milliseconds"

Solution 9 - Javascript

one of the simplest, fastest, more reusable and flexible is:

Array.prototype.sum = function () {
    for(var total = 0,l=this.length;l--;total+=this[l]); return total;
}

// usage
var array = [1,2,3,4,5,6,7,8,9,10];
array.sum()

Solution 10 - Javascript

What about summing both extremities? It would cut time in half. Like so:

1, 2, 3, 4, 5, 6, 7, 8; sum = 0

2, 3, 4, 5, 6, 7; sum = 10

3, 4, 5, 6; sum = 19

4, 5; sum = 28

sum = 37

One algorithm could be:

function sum_array(arr){
	let sum = 0,
		length = arr.length,
		half = Math.floor(length/2)

    for (i = 0; i < half; i++) {
		sum += arr[i] + arr[length - 1 - i]
    }
	if (length%2){
		sum += arr[half]
    }
	return sum
}

It performs faster when I test it on the browser with performance.now(). I think this is a better way. What do you guys think?

Solution 11 - Javascript

Here is a jsPerf for all variations from @Ankur´s answer with some minor modifications:

https://jsben.ch/J6ywV

Changes:

  1. There is performance difference between summing up an array of [1,2,3,..,n] or [n,n-1,n-2,..,1].

    > Tests labeled with (reversed array) run the same test-fn with a reversed test array. They always outperform their counterpart.

  2. console.log(`Sum: ${sum}`) has a negativ impact for the measurement and were removed (it takes time to render the output).

  3. I added bench for reduceRight().

enter image description here

For more relyable results you might want to run each test several times, with different arrays to get an average runtime.

// Test functions
let fn_reduce = a => a.reduce((pv, cv) => pv + cv, 0);
let fn_reduceRight = a => a.reduceRight((pv, cv) => pv + cv, 0);
let tests = [fn_reduce, fn_reduceRight];

// Test config
let runs = 8;     // test runs
let length = 100000; // array length
// .. test with "array" and "reversed array"
let arr1 = Array.from({length}, (_, i) => i);
let arr2 = Array.from({length}, (_, i) => length - i - 1);

let out = [];
let outGrouped = {};
for(let i = 0; i < runs; i++){
  tests.forEach(fn => {
    (i % 2 ? [arr1, arr2] : [arr2, arr1]).forEach(arr => {
        let isArrayReverse = arr !== arr1;
        let sum = 0;
        let t1 = performance.now();

        sum = fn(arr);

        let t2 = performance.now();
        let duration = t2 - t1;
        out.push({run: i, fn: fn.name, isArrayReverse, duration});

        let group = `${fn.name}_${isArrayReverse}`;
        outGrouped[group] ??= {fn: fn.name, isArrayReverse, duration: 0, runs: 0};
        outGrouped[group].duration += duration;
        outGrouped[group].runs++;
    });
  });
}

//console.log('out'); // detailed output

console.log('OPEN DEV-TOOLS for console.table()!');
console.log('Sort by "avg" column.');

console.table(Object.fromEntries(Array.from(Object.entries(outGrouped), ([group, {duration, runs, ...rest}]) => [group, {...rest, avg: duration / runs, duration, runs}])));

enter image description here

Categories
Recommended Javascript Solutions
Recommended Arrays Solutions
Recommended Function Solutions

Previous Solution:

How to animate the background color of a UILabel?

IosIphoneCore Animation

Next Solution:

What do the return values of Comparable.compareTo mean in Java?

JavaComparable

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionJosh KView Question on Stackoverflow
Solution 1 - JavascriptChaosPandionView Answer on Stackoverflow
Solution 2 - Javascriptvol7ronView Answer on Stackoverflow
Solution 3 - JavascriptInkh Su TesouView Answer on Stackoverflow
Solution 4 - JavascriptBiereagu SochimaView Answer on Stackoverflow
Solution 5 - JavascriptCaffGeekView Answer on Stackoverflow
Solution 6 - JavascriptTim DownView Answer on Stackoverflow
Solution 7 - JavascriptBrunoLMView Answer on Stackoverflow
Solution 8 - JavascriptAnkur SinghView Answer on Stackoverflow
Solution 9 - JavascriptespiralisView Answer on Stackoverflow
Solution 10 - JavascriptcesarvargasView Answer on Stackoverflow
Solution 11 - JavascriptExodus 4DView Answer on Stackoverflow