我想知道是否有更好的方法来为数组的部分和生成性能更好的解决方案。
给定一个数组 say x = [ 0, 1, 2, 3, 4, 5 ]，我生成了项目的子数组，然后计算每个数组的总和，得到：
[ 0, 1, 3, 6, 10, 15 ]
所以完整的代码是：
x.map((y,i)=>x.filter((t,j)=>j<=i))
.map(ii=>ii.reduce((x,y)=>x+y,0))
我想知道平面地图或其他一些数组方法是否会有不需要扩展每个子数组的解决方案。
问问题
5295 次
11 回答
22
很多，通过保持运行总数：
function* partialSums(iterable) {
let s = 0;
for (const x of iterable) {
s += x;
yield s;
}
}
const x = [0, 1, 2, 3, 4, 5];
console.log(Array.from(partialSums(x)).join(', '));线性时间，在线。（您也可以直接生成一个数组；在下面展开。）
const partialSums = arr => {
let s = 0;
return arr.map(x => s += x);
};
const x = [0, 1, 2, 3, 4, 5];
console.log(partialSums(x).join(', '));于 2019-06-10T00:34:20.857 回答
6
平面地图在您的情况下没有用，因为您不是试图将作为列表的部分结果展平，但我们可能会尝试在单个reduce中解决您的问题：
[0, 1, 2, 3, 4, 5]
.reduce(
([arr, sum], el) => { // We pass along array and running sum
const next = sum + el
return [[...arr, next], next]
},
[[], 0] // We need to seed our reduce with empty array and accumulator for calculating running sum
)[0] // Array containing array and the last sum is returned, so we need to take only the first element
它也只对数组进行一次迭代，因此它可能比创建切片然后对它们求和的解决方案性能更高一些。
或带有 的版本array.push，它重用相同的数组：
[0, 1, 2, 3, 4, 5]
.reduce(
([arr, sum], el) => { // We pass along array and running sum
const next = sum + el
arr.push(next)
return [arr, next]
},
[[], 0] // We need to seed our reduce with empty array and accumulator for calculating running sum
)[0]
于 2019-06-10T06:56:46.140 回答
6
下面，scan采用映射函数f和初始累加器r-
const scan = (f, r, [ x, ...xs ]) =>
x === undefined
? [ r ]
: [ r, ...scan (f, f (r, x), xs) ]
const add = (x, y) =>
x + y
const print = (...vs) =>
vs .forEach (v => console .log (v))
const data =
[ 0, 1, 2, 3, 4, 5 ]
print
( scan (add, 0, data)
, scan (Math.max, 3, data)
, scan (add, 0, [])
)
// [ 0, 0, 1, 3, 6, 10, 15 ]
// [ 3, 3, 3, 3, 3, 4, 5 ]
// [ 0 ]如果您需要一个不使用初始累加器的程序，则可以使用输入数组的第一个元素。这种变化被称为scan1-
const scan = (f, r, [ x, ...xs ]) =>
x === undefined
? [ r ]
: [ r, ...scan (f, f (r, x), xs) ]
const scan1 = (f, [ x, ...xs ]) =>
x === undefined
? []
: scan (f, x, xs)
const add = (x, y) =>
x + y
const print = (...vs) =>
vs .forEach (v => console .log (v))
const data =
[ 0, 1, 2, 3, 4, 5 ]
print
( scan1 (add, data)
, scan1 (Math.max, data)
, scan1 (Math.min, data)
, scan1 (add, [])
)
// [ 0, 1, 3, 6, 10, 15 ]
// [ 0, 1, 2, 3, 4, 5 ]
// [ 0, 0, 0, 0, 0, 0 ]
// []如有必要，可以进行性能优化并解决堆栈溢出问题，所有这些都不会牺牲功能风格 -
const scan = (f, init, xs) =>
loop
( ( r = []
, a = init
, i = 0
) =>
i >= xs.length
? push (a, r)
: recur
( push (a, r)
, f (a, xs[i])
, i + 1
)
)
现在让我们用一个大输入来运行它 -
// BIG data!
const data =
Array .from (Array (10000), (_, x) => x)
// fast and stack-safe
console .time ("scan")
const result = scan (add, 0, data)
console .timeEnd ("scan")
// scan: 8.07 ms
console .log (result)
// [ 0, 0, 1, 3, 6, 10, 15, ..., 49985001 ]
这取决于以下通用功能过程 -
const recur = (...values) =>
({ recur, values })
const loop = f =>
{ let r = f ()
while (r && r.recur === recur)
r = f (...r.values)
return r
}
const push = (x, xs) =>
( xs .push (x)
, xs
)
展开下面的代码片段以在您自己的浏览器中验证结果 -
const recur = (...values) =>
({ recur, values })
const loop = f =>
{ let r = f ()
while (r && r.recur === recur)
r = f (...r.values)
return r
}
const push = (x, xs) =>
( xs .push (x)
, xs
)
const scan = (f, init, xs) =>
loop
( ( r = []
, a = init
, i = 0
) =>
i >= xs.length
? push (a, r)
: recur
( push (a, r)
, f (a, xs[i])
, i + 1
)
)
const add = (x, y) =>
x + y
const data =
Array .from (Array (10000), (_, x) => x)
console .time ("scan")
const result = scan (add, 0, data)
console .timeEnd ("scan")
console .log (result)
// [ 0, 0, 1, 3, 6, 10, 15, ..., 49995000 ]于 2019-06-10T01:44:27.620 回答
5
您只需在每一步中将当前值添加到前一个结果中，这样您就可以使用简单的 reduce。
const array = [0, 1, 2, 3, 4, 5, 6];
const sums = array.reduce((acc,current,index) => {
const prev = acc.length ? acc[index-1] : 0;
acc.push(prev + current);
return acc;
},[]);
console.log(sums.toString());于 2019-06-10T10:04:07.447 回答
5
您可以简单地使用for带有变量的循环来跟踪最后的总和
let x = [ 0, 1, 2, 3, 4, 5 ]
let sum = (arr) => {
let sum = 0
let final = []
for(let i=0; i<arr.length; i++){
sum+= arr[i]
final.push(sum)
}
return final
}
console.log(sum(x))您还可以使用地图：
let x = [0, 1, 2, 3, 4, 5]
let sum = (arr) => {
let sum = 0
return arr.map(current => sum += current )
}
console.log(sum(x))于 2019-06-10T01:46:07.840 回答
4
如果您问是否有更快或更有效的方法，那么其他答案就足够了。
但是，如果我们将其表述为映射函数，我认为与您当前的解决方案类似的东西更易于阅读且更具声明性。
特别是像“将每个值映射到自身加上数组中所有先前的值”之类的东西。
您可以使用过滤器，就像您在问题中所做的那样，但我认为切片更清晰。
const x = [ 0, 1, 2, 3, 4, 5 ];
// A common generic helper function
const sum = (acc, val) => acc + val
const sums = x.map((val, i, self) => val + self.slice(0, i).reduce(sum, 0))
于 2019-06-10T11:29:38.117 回答
2
如果您保留一个外部累加器变量，则可以直接使用 map ：
const x = [ 0, 1, 2, 3, 4, 5 ];
let acc = 0;
const prefixSum = x.map(x => acc += x);
console.log(prefixSum);于 2019-06-14T07:14:45.430 回答
1
一种选择是使用一个.map使用.reduceinside 来总结切片的部分数组：
const x = [0, 1, 2, 3, 4, 5];
const sum = (x, y) => x + y;
const partialSums = x.map((_, i, arr) => arr.slice(0, i + 1).reduce(sum));
console.log(partialSums);于 2019-06-10T00:14:05.913 回答
0
一种方法可以是使用每个然后对数组进行切片以一个一个地获取元素，然后将它们全部加起来array.reduce你可以这样做
let x = [0, 1, 2, 3, 4, 5]
let sum = []
x.forEach((_, index) => {
index++;
sum.push(x.slice(0, index).reduce((a, b) => a + b))
})
console.log(sum)我们得到[0]then [0,1]then[0,1,2]然后[0,1,2,3]通过[0,1,2].reduce((a, b) => a + b))我们得到 3。只需将其推送到新数组即可。这是你的答案。
通过这样做，我们可以走得更短。对我来说，这似乎是一个非常优化的解决方案。
let ar = [0, 1, 2, 3, 4, 5]
let s = 0
let arr = []
ar.forEach((n, i) => arr.push(s += n))
console.log(arr)或者.map，你可以
let ar = [0, 1, 2, 3, 4, 5], s = 0
console.log(ar.map((n, i) => s += n))于 2019-06-10T17:55:01.300 回答
0
最简单的答案是单线：如果 x 是 [0,1,2,3,4,5]
x.map(i=>s+=i, s=0)
于 2020-08-28T21:08:19.090 回答
0
这是使用递归函数的简单答案。
var array = [ 0, 1, 2, 3, 4, 5 ];
function sumArray(arrayToSum, index){
if(index < arrayToSum.length-1){
arrayToSum[index+1] = arrayToSum[index] + arrayToSum[index+1];
return sumArray(arrayToSum, index+1);
}else
return arrayToSum;
}
sumArray(array, 0);
console.log(array);
于 2019-06-10T16:26:05.110 回答