最快的JavaScript求和

Question

什么是在JavaScript中对数组进行求和的最快方法？ 快速搜索可以找到几种不同的方法，但如果可能的话，我想要一个本地解决方案。这将在SpiderMonkey下运行。

从非常内部的角度考虑，我一直在使用：

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

我相信有比直接迭代更好的方法。

- Josh K

---

测试！如果你想知道做某件事情最快的方法是什么，可以尝试几种方法，并测量结果。 - CaffGeek

@Chad：显然，不过我已经没有那种“跳脱传统思维”的日子了。 - Josh K

Answer 1

您应该能够使用 reduce。

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

来源

而在 ES6 中引入的 箭头函数，使得代码更加简洁：

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

- ChaosPandion

---

根据相关文档，"[reduce] 可能不适用于所有浏览器"。 - Ryan Kinal

啊，抱歉，我错过了那个。这种情况下，这就是答案。 - Tim Down

虽然reduce是本地函数，但我对此表示怀疑。在JS的性能优化代码中，尽可能避免函数调用几乎总是更快的。 - MooGoo

如果您想在IE <= 8中使用reduce，请使用Mozilla的兼容性shim：https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Array/Reduce - He Nrik

@BrunoLM这已经不再正确了！ - Cirelli94

Answer 2

改进

你的循环结构可以更快：

---

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

这样做可以避免在每次迭代中都获取 array.length，而是缓存了该值。通过缓存值进行优化。

如果你真的想加速它：

---

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

这相当于一个反向的while循环。它缓存值并与0进行比较，因此迭代速度更快。

有关更完整的比较列表，请参阅我的JSFiddle。
注意：array.reduce在那里表现很差，但在Firebug控制台中是最快的。

---

对比结构

我开始了一个用于数组求和的JSPerf。 它是快速构建的，不能保证完整或准确，但这就是编辑的作用 :)

- vol7ron

---

你的for循环几乎相同。我进行了测试，有时增量比递减快得多。而且Array.reduce非常慢。http://jsperf.com/array-reduce-vs-foreach/2 - BrunoLM

@BrunoLM：你说得对，这是三年前的旧答案。我认为不久之后，会有一些新的JS引擎可用，并且现有的引擎已经被调整，使得前向循环比反向while循环更快。这说明微观优化通常是不明智的。如果您没有本地套件，我建议继续测试和基准测试--jsperf是一个很好的网站。 - vol7ron

链接的JS Fiddle在"For Loop: Length Caching (reverse)"中有一个错误。它总是将索引0处的元素添加到总和中。应该将for (var i = 0, n = array.length; n > i; n--) { sum += array[i]; }更改为for (var i = 0, n = array.length-1; n >= i; n--) { sum += array[n]; }。这使其与其他缓存循环大致相同。 - Lukas_Skywalker

Answer 3

在寻找数组求和的最佳方法时，我编写了一个性能测试。

在Chrome中，“reduce”似乎要优于其他方法。

希望这有所帮助。

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

评估时间: 5233.000毫秒

循环时间: 255.000毫秒

减少时间: 70.000毫秒

当时间: 214.000毫秒

- Inkh Su Tesou

---

谢谢您的提问，为什么reduce函数中需要使用parseInt？我也尝试了一下，在我的代码中也需要使用它。 - Allen Wang

嗯，不确定，试着不用 parseInt.. 我是 4 年前写的 :D - Inkh Su Tesou

Answer 4

或者你可以用邪恶的方式来做。

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

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

;)

- Biereagu Sochima

---

eval() 永远不应该被使用 - Len Joseph

也被称为LISP方式 :) - sesm

Answer 5

根据这个测试，最快的循环方式是反向while循环。

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

因此，这段代码可能是您可以获得的最快速度

Array.prototype.sum = function () {
    var total = 0;
    var i = this.length; 

    while (i--) {
        total += this[i];
    }

    return total;
}

Array.prototype.sum为数组类添加了一个求和方法......你也可以将它轻松地变成一个辅助函数。

- CaffGeek

---

我的反转for循环通常情况下稍微更快。 - vol7ron

@vol7ron，非常、非常、非常微小，我们说的是在1000条记录中超过1毫秒。 - CaffGeek

是的，不是每次都这样做。不过，由于起始/停止控制结构，我更倾向于使用for(var i=0,n=a.length;i<n;i++){}。 - vol7ron

sum 方法中的 arr 是从哪里来的？arr 真的应该是 this 吗？ - Chris Farmer

看起来将while条件评估为布尔值可以使其更快http://jsperf.com/while-bool-vs-while - BrunoLM

@BrunoLM，似乎并不总是更快，每次运行时得到的结果差别很大。 - CaffGeek

Answer 6

针对您的具体情况，只需使用Arrays的reduce方法：

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

- Tim Down

Answer 7

根据这个测试（for-vs-forEach-vs-reduce）和这个（循环），我可以说：

1# 最快的：for循环

var total = 0;

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

2# 聚合

对于你的情况来说，你不需要这个功能，但它可以增加很多灵活性。

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

使用方法：

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

不确定的方法

接下来是forEach和reduce，它们的性能几乎相同并且因浏览器而异，但无论如何它们的性能都是最差的。

- BrunoLM

Answer 8

我尝试使用performance.now()来分析不同类型循环的性能。我使用了一个非常大的数组，并找到了数组中所有元素的总和。每次我都运行了三次代码，发现forEach和reduce是明显的赢家。

// For循环

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循环

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"

// 反向循环

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"

// 反向 while 循环

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"

// 减少

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"

- Ankur Singh

---

+1 但是最好有一个 jsperf 来验证一下。我相信这些数字会因为使用的 js 引擎而有所不同。 - FullStackForger

Answer 9

其中最简单、最快速、最可重用和灵活的是：

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

- espiralis

---

哈哈！这既不比reduce更简单、更快、更易重复使用、也不更灵活！ - Corey Alix

这确实是最快的方法（请参见http://jsben.ch/0Qa3G），并且可以通过另一种有趣的方式完成`class UintArray extends Uint8Array { sum () { FUNCTION_CODE_HERE } }`。 - Noah

更改数组原型会破坏for..in循环！ - NVRM

Answer 10

那么把两端加起来怎么样？这样可以把时间减半。就像这样：

1、2、3、4、5、6、7、8；总和=0

2、3、4、5、6、7；总和=10

3、4、5、6；总和=19

4、5；总和=28

总和=37

一个算法可能是：

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
}

当我使用 performance.now() 在浏览器上测试时，它的性能更快。我认为这是一种更好的方式。你们觉得呢？

- cesarvargas

---

从技术上讲，在大O符号表示法中，O(n/2)等于O(n)。为什么？因为你估计的不是给定输入的速度有多快，而是随着输入变化速度如何改变。如果将输入加倍到O(n)函数中，它需要两倍的时间。如果将输入加倍到O(n/2)函数中，它需要两倍的时间。如果将输入加倍到O(n²)中，它需要四倍的时间。 - t.animal

1到8的和是36，不是37。 - daign