例如给定一个数组,比如
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))
我想知道是否有flat map或其他数组方法的解决方案,不需要扩展每个子数组。
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))
我想知道是否有flat map或其他数组方法的解决方案,不需要扩展每个子数组。
通过保持一个不断更新的总数:
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(', '));
yield
这个词有点弱。像个男子汉一样将每个项目添加到数组中,然后使用 return
返回它。 - Malekaiconcat
(或等效地,spread)是一种有害的方式,可以通过创建flatMap
或scan
来解决问题并假装自己更加功能强大,而局部变异则是实现必要函数的好方法。那么你反对什么呢? - Ry-在您的情况下,平面图不会有用,因为您不是要将作为列表的部分结果压平,但我们可能可以尝试在单个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]
push
替换它,但这会改变数组,使其不再是纯函数式的。你看到问题标签中的 functional-programming
了吗? - Krzysztof Atłasikpush
的版本是引用透明的,所以也没问题。我编辑了我的答案,包括第二个版本。 - Krzysztof Atłasikfor
循环来跟踪最后的总和。
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))
下面的代码,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 ]
[ r, ...scan (f, f (r, x), xs) ]
展开运算符 – 复制 0 + 1 + … + n−1 项,二次函数。 [ x, ...xs ]
解构赋值 – 复制 n−1 + n−2 + … + 0 项,二次函数。谢谢添加另一个版本。 - Ry-[r, ...s]
和[r].concat(s)
是相同的。 - Ry-您只需要在每个步骤中将当前值添加到先前结果中,因此可以使用简单的 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());
如果你想知道是否有比其他答案更快或更有效的方法,那么其他答案已经足够了。
然而,我认为如果我们把它表述为映射函数,类似于你当前的解决方案,那么它更易读且更具声明性。
具体来说,就是"将每个值映射到其本身加上数组中所有先前值的总和"。
你可以像在问题中所做的那样使用过滤器,但我认为切片会更清晰。
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))
It's possible to use map directly, if you keep an external accumulator variable:
const x = [ 0, 1, 2, 3, 4, 5 ];
let acc = 0;
const prefixSum = x.map(x => acc += x);
console.log(prefixSum);
一种选择是使用单个.map
,其中内部使用.reduce
来总结切片的部分数组:
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);
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]
,然后是 [0,1]
,接着是 [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))
.map
而不是像forEach
一样”,但为什么呢? - Ry-map
来产生一个推送副作用并且丢弃结果。(好吧,我猜这不是毫无意义的,因为这意味着你在技术上没有复制我的答案。) - Ry-.map
,例如 arr.map(x => x * 2)
与 let result = []; arr.forEach(x => { result.push(x * 2) })
之间的区别,而 let result = []; arr.map(x => { result.push(x * 2) })
只是两者最糟糕的结合。 - Ry-x.map(i=>s+=i, s=0)