Pat*_*eme 25 javascript arrays functional-programming prefix-sum
我想知道是否有更好的方法可以为数组的部分和生成更好的性能的解决方案。
给定一个说的数组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))
我想知道平面图或其他数组方法是否具有不需要扩展每个子数组的解决方案。
Ry-*_*Ry- 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(', '));下面，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 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
)
)
您可以简单地使用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))平面映射在您的情况下将不会有用，因为您没有尝试将部分结果以列表的形式展平，但是我们可能可以尝试通过一个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]
您只需在每一步中将当前值添加到先前的结果中，这样您就可以使用简单的归约。
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());一种选择是使用 single .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);