有没有更好的方法在JavaScript中对数组元素进行部分求和？

Question

我想知道是否有更好的方法来生成一个更高效的部分数组求和解决方案。

例如给定一个数组，比如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或其他数组方法的解决方案，不需要扩展每个子数组。

- Patrick Francis Omogbeme

---

顺便说一下，这被称为“前缀和”或“扫描”。许多集合框架在标准库中都有它，但不幸的是 ECMAScript 没有。 - Jörg W Mittag

Answer 1

通过保持一个不断更新的总数：

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(', '));

- Ry-

---

呃…… yield 这个词有点弱。像个男子汉一样将每个项目添加到数组中，然后使用 return 返回它。 - Malekai

@LogicalBranch：那不会在线，所以你最好使用第二个代码片段。 - Ry-

为什么？2019 年迭代器很棒，不是吗？ - spender

这是一个不错的命令式答案，但它并不适用于标记为函数式编程的问题。这只是将特定的辅助函数一对一地分配给一个非常具体的问题。没有泛化，没有学习到任何东西。 - user5536315

@bob：如果你同意重复使用concat（或等效地，spread）是一种有害的方式，可以通过创建flatMap或scan来解决问题并假装自己更加功能强大，而局部变异则是实现必要函数的好方法。那么你反对什么呢？ - Ry-

Answer 2

在您的情况下，平面图不会有用，因为您不是要将作为列表的部分结果压平，但我们可能可以尝试在单个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] 

- Krzysztof Atłasik

---

这将同样很慢（O(n²)），因为每次想要向数组添加内容时都需要复制该数组。 - Ry-

@Ry- 你可以轻松地用 push 替换它，但这会改变数组，使其不再是纯函数式的。你看到问题标签中的 functional-programming 了吗？ - Krzysztof Atłasik

没有什么是完全函数式的。你拥有这个数组，这完全没问题。 - Ry-

@Ry- 不完全是，你可以有纯函数方法。但正如你所提到的，使用 push 的版本是引用透明的，所以也没问题。我编辑了我的答案，包括第二个版本。 - Krzysztof Atłasik

Answer 3

你可以使用一个带有变量的 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))

您也可以使用map函数：

let x = [0, 1, 2, 3, 4, 5]

let sum = (arr) => {
  let sum = 0
  return arr.map(current => sum += current )
}

console.log(sum(x))

- Code Maniac

---

第二个代码片段看起来非常熟悉，甚至隐藏了这一事实。 - Ry-

@Ry-和上面的那行代码说明“你也可以使用map”，我想展示传统和函数式方法，如果人们觉得这是一个有效的理由来投反对票，我很高兴接受 :) - Code Maniac

Answer 4

以下是关于 IT 技术的翻译内容：

下面的代码，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 ]

- Mulan

---

“scan”是好的。但在JavaScript中实现“scan”，就好像它是Haskell一样，这并不好，因为它会给你二次时间复杂度和栈溢出，即使在不是特别大的数组上也会出现这种情况。 - Ry-

@Ry-，谢谢你的回复，但我并没有看到二次时间复杂度。中间数组肯定是浪费的，但简单的程序确切地展示了需要做什么。这种程序的优化很容易，所以我通常会留给最了解自己需求的最终用户。答案的更新显示了一个堆栈安全的“扫描”。感谢您的评论。 - Mulan

[ r, ...scan (f, f (r, x), xs) ] 展开运算符 – 复制 0 + 1 + … + n−1 项，二次函数。 [ x, ...xs ] 解构赋值 – 复制 n−1 + n−2 + … + 0 项，二次函数。谢谢添加另一个版本。 - Ry-

是的，但是 O(n*(n+1)/2) = O(n²)。其中的“一半”是一个常数因子。 - Ry-

@ScottSauyet：在这方面，[r, ...s]和[r].concat(s)是相同的。 - Ry-

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

- Pablo Lozano

Answer 6

如果你想知道是否有比其他答案更快或更有效的方法，那么其他答案已经足够了。

然而，我认为如果我们把它表述为映射函数，类似于你当前的解决方案，那么它更易读且更具声明性。

具体来说，就是"将每个值映射到其本身加上数组中所有先前值的总和"。

你可以像在问题中所做的那样使用过滤器，但我认为切片会更清晰。

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

- Calin Leafshade

---

代码使用了相同的方法，但我认为这个答案没有解释这种方法的价值。答案应该不仅仅是代码。 - Calin Leafshade

Answer 7

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

- Joe23

---

我点了赞。我猜那些踩的人不熟悉“赋值表达式”，不习惯使用“x => acc += x”。 - LiuXiMin

Answer 8

一种选择是使用单个.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);

- CertainPerformance

Answer 9

一种方法是使用for each，然后对数组进行切片，以逐个获取元素，然后通过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))

- weegee

---

“对我来说，这似乎是一个非常优化的解决方案。”实际上并不是。 “你也可以使用.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-

不，我刚刚解释了为什么它不是你认为的那样更快。试一下基准测试吧。当然，你可以随便使用它，但这将是一个不好的实践。 - Ry-

@Ry- 好的，我会接受你的方法，因为我是一名初级开发者，而且.map返回一个数组，这也可能导致一些数组浪费。我已经编辑了我的答案。 - weegee

Answer 10

最简单的答案是一行代码：如果x为[0,1,2,3,4,5]。

x.map(i=>s+=i, s=0)

- Patrick Francis Omogbeme