给定一个数组[1,2,3,4],如何求其元素的和?(在这种情况下,总数为10。)
我认为每个美元可能有用,但我不确定如何实现它。
给定一个数组[1,2,3,4],如何求其元素的和?(在这种情况下,总数为10。)
我认为每个美元可能有用,但我不确定如何实现它。
当前回答
TL;博士
如果您关心性能,请定义一个使用for循环的函数。
function sum(arr) {
var res = 0;
for (var x of arr) {
res += x;
}
return res;
}
基准
我使用benchmark.js(typescript版本)对一些实现进行了基准测试:
const arr = Array.from({ length: 100 }, () => Math.random());
const reducer = function (p: number, a: number) {
return p + a;
};
const recursion = function (arr: number[], i: number) {
if(i > 0) return arr[i] + recursion(arr, i - 1)
else return 0
};
const recursion2 = function (arr: number[], i: number, len: number) {
if(i < len) return arr[i] + recursion2(arr, i + 1, len)
else return 0
};
const recursion3 = function (arr: number[], i: number) {
if(i < arr.length) return arr[i] + recursion3(arr, i + 1)
else return 0
};
new Benchmark.Suite()
.add("jquery", () => {
let res = 0;
$.each(arr, (_, x) => (res += x));
})
.add("lodash", ()=>_.sum(arr))
.add("forEach", () => {
let res = 0;
arr.forEach((x) => (res += x));
})
.add("reduce", () => arr.reduce((p, a) => p + a, 0))
.add("predefined reduce", () => arr.reduce(reducer, 0))
.add("eval", () => eval(arr.join("+")))
.add("recursion", () => recursion(arr, arr.length - 1))
.add("recursion2", () => recursion2(arr, 0, arr.length))
.add("recursion3", () => recursion3(arr, 0))
.add("naive", () => (
arr[0]+arr[1]+arr[2]+arr[3]+arr[4]+arr[5]+arr[6]+arr[7]+arr[8]+arr[9]+
arr[10]+arr[11]+arr[12]+arr[13]+arr[14]+arr[15]+arr[16]+arr[17]+arr[18]+arr[19]+
arr[20]+arr[21]+arr[22]+arr[23]+arr[24]+arr[25]+arr[26]+arr[27]+arr[28]+arr[29]+
arr[30]+arr[31]+arr[32]+arr[33]+arr[34]+arr[35]+arr[36]+arr[37]+arr[38]+arr[39]+
arr[40]+arr[41]+arr[42]+arr[43]+arr[44]+arr[45]+arr[46]+arr[47]+arr[48]+arr[49]+
arr[50]+arr[51]+arr[52]+arr[53]+arr[54]+arr[55]+arr[56]+arr[57]+arr[58]+arr[59]+
arr[60]+arr[61]+arr[62]+arr[63]+arr[64]+arr[65]+arr[66]+arr[67]+arr[68]+arr[69]+
arr[70]+arr[71]+arr[72]+arr[73]+arr[74]+arr[75]+arr[76]+arr[77]+arr[78]+arr[79]+
arr[80]+arr[81]+arr[82]+arr[83]+arr[84]+arr[85]+arr[86]+arr[87]+arr[88]+arr[89]+
arr[90]+arr[91]+arr[92]+arr[93]+arr[94]+arr[95]+arr[96]+arr[97]+arr[98]+arr[99]))
.add("loop with iterator", () => {
let res = 0;
for (const x of arr) res += x;
})
.add("traditional for loop", () => {
let res = 0;
// cache the length in case the browser can't do it automatically
const len = arr.length;
for (let i = 0; i < len; i++) res += arr[i];
})
.add("while loop", () => {
let res = 0;
let i = arr.length;
while (i--) res += arr[i];
})
.add("loop in a function ", () => sum(arr))
.on("cycle", (event) => console.log(String(event.target)))
.run();
在chrome 104中,基于for循环的实现是最快的:
jquery x 1,832,472 ops/sec ±1.35% (61 runs sampled)
lodash x 2,079,009 ops/sec ±1.11% (68 runs sampled)
forEach x 4,887,484 ops/sec ±2.35% (67 runs sampled)
reduce x 21,762,391 ops/sec ±0.46% (69 runs sampled)
predefined reduce x 2,026,411 ops/sec ±0.50% (68 runs sampled)
eval x 33,381 ops/sec ±2.54% (66 runs sampled)
recursion x 2,252,353 ops/sec ±2.13% (62 runs sampled)
recursion2 x 2,301,516 ops/sec ±1.15% (65 runs sampled)
recursion3 x 2,395,563 ops/sec ±1.65% (66 runs sampled)
naive x 31,244,240 ops/sec ±0.76% (66 runs sampled)
loop with iterator x 29,554,762 ops/sec ±1.07% (66 runs sampled)
traditional for loop x 30,052,685 ops/sec ±0.67% (66 runs sampled)
while loop x 18,624,045 ops/sec ±0.17% (69 runs sampled)
loop in a function x 29,437,954 ops/sec ±0.54% (66 runs sampled)
Firefox 104显示了类似的行为:
jquery x 1,461,578 ops/sec ±1.58% (64 runs sampled)
lodash x 4,931,619 ops/sec ±0.80% (66 runs sampled)
forEach x 5,594,013 ops/sec ±0.51% (68 runs sampled)
reduce x 3,731,232 ops/sec ±0.53% (66 runs sampled)
predefined reduce x 2,633,652 ops/sec ±0.54% (66 runs sampled)
eval x 105,003 ops/sec ±0.88% (66 runs sampled)
recursion x 1,194,551 ops/sec ±0.24% (67 runs sampled)
recursion2 x 1,186,138 ops/sec ±0.20% (68 runs sampled)
recursion3 x 1,191,921 ops/sec ±0.24% (68 runs sampled)
naive x 21,610,416 ops/sec ±0.66% (66 runs sampled)
loop with iterator x 15,311,298 ops/sec ±0.43% (67 runs sampled)
traditional for loop x 15,406,772 ops/sec ±0.59% (67 runs sampled)
while loop x 11,513,234 ops/sec ±0.60% (67 runs sampled)
loop in a function x 15,417,944 ops/sec ±0.32% (68 runs sampled)
讨论
定义匿名函数的实现通常较慢,因为创建匿名函数是一个很大的开销。当使用大型阵列(例如,长度为1000而不是100)运行基准测试时,reduce和基于for循环的实现之间的差异在chrome中变得微不足道。
Chrome的V8引擎知道如何在reduce中内联简单的匿名函数,因为reduce测试用例比预定义的reduce用例快得多。Firefox似乎尝试了类似的方法,但效率较低。非内联函数调用在js中非常慢,因为调用堆栈的效率低于编译软件中的调用堆栈。
与reduce类似,基于forEach和jquery的实现使用匿名函数,速度相对较慢。lodash有一个专门的sum实现,但它(从v4.0开始)是作为sumBy的一个特例实现的,这是相对低效的。
eval是迄今为止最慢的测试用例。这是有意义的,因为使用串联构造字符串可能会导致多个动态分配(速度较慢)。接下来,必须调用解析器,然后才能最终执行代码。
我加入了一些递归实现,因为互联网上的一些人声称递归比js中的循环更快。我无法再现他们的例子-使用benchmark.js,递归非常慢,并且当使用console.time和循环时,两个函数都需要相同的时间。在计算和时,正如预期的那样,递归比循环慢得多,这可能是由于js调用堆栈的大量使用。
天真的实现是手动添加阵列的所有100个元素。虽然很不方便,但这是最快的实现。但幸运的是,for循环非常接近。在循环中添加单个函数调用不会损害性能。因此,您可以自由使用上面的实用程序功能。
我无法解释为什么while循环比for循环慢。反向迭代数组似乎不是问题所在。
其他回答
这里有一个优雅的单线解决方案,它使用堆栈算法,尽管人们可能需要一些时间来理解这个实现的美。
const getSum = arr => (arr.length === 1) ? arr[0] : arr.pop() + getSum(arr);
getSum([1, 2, 3, 4, 5]) //15
基本上,该函数接受一个数组,并检查该数组是否正好包含一个项。如果为false,则从堆栈中弹出最后一项并返回更新的数组。
这段代码的妙处在于,该函数包括arr[0]检查,以防止无限循环。一旦到达最后一项,它将返回全部金额。
对于真正大量的人来说,循环或减少可能是过程密集型的。使用高斯怎么样?
sum = (n * (n+1))/2;
来自mathcentral。
有人在找像我这样的功能性的oneliner吗?
假设:
const arr = [1, 2, 3, 4];
这是现代JS的一条直线:
sum = arr.reduce((a, b) => a + b, 0);
(如果您碰巧需要支持没有箭头功能的旧IE:)
sum = arr.reduce(function (a, b) {return a + b;}, 0);
注意,这里的初始值是0,因此如果需要,可以将其用作偏移量。还要注意,需要这个初始值,否则使用空数组调用函数将出错。
这可以通过循环所有项,并在每次迭代中将它们添加到一个和变量中来实现。
var array = [1, 2, 3];
for (var i = 0, sum = 0; i < array.length; sum += array[i++]);
JavaScript不知道块的作用域,所以可以访问sum:
console.log(sum); // => 6
同上,但注释和准备为简单函数:
function sumArray(array) {
for (
var
index = 0, // The iterator
length = array.length, // Cache the array length
sum = 0; // The total amount
index < length; // The "for"-loop condition
sum += array[index++] // Add number on each iteration
);
return sum;
}
试试这个。。。
function arrSum(arr){
total = 0;
arr.forEach(function(key){
total = total + key;
});
return total;
}