快速运行总和 [英] Swift running sum

问题描述

我想要一个函数 runningSum 在一个数字数组(或任何可添加的有序集合)上返回一个相同长度的数组，其中每个元素 i 是 A 中所有元素的总和，直到包含 i.

I'd like a function runningSum on an array of numbers a (or any ordered collection of addable things) that returns an array of the same length where each element i is the sum of all elements in A up to an including i.

示例:

runningSum([1,1,1,1,1,1]) -> [1,2,3,4,5,6]
runningSum([2,2,2,2,2,2]) -> [2,4,6,8,10,12]
runningSum([1,0,1,0,1,0]) -> [1,1,2,2,3,3]
runningSum([0,1,0,1,0,1]) -> [0,1,1,2,2,3]

我可以使用 for 循环或其他方式来完成此操作.有没有更实用的选择?它有点像reduce，只是它构建了一个包含所有中间值的结果数组.

I can do this with a for loop, or whatever. Is there a more functional option? It's a little like a reduce, except that it builds a result array that has all the intermediate values.

更一般的做法是有一个函数可以接受任何序列并提供一个序列，该序列是输入序列的运行总和.

Even more general would be to have a function that takes any sequence and provides a sequence that's the running total of the input sequence.

推荐答案

您正在寻找的通用组合器通常称为 scan，并且可以根据 reduce 定义(就像列表中的所有高阶函数一样):

The general combinator you're looking for is often called scan, and can be defined (like all higher-order functions on lists) in terms of reduce:

extension Array {
    func scan<T>(initial: T, _ f: (T, Element) -> T) -> [T] {
        return self.reduce([initial], combine: { (listSoFar: [T], next: Element) -> [T] in
            // because we seeded it with a non-empty
            // list, it's easy to prove inductively
            // that this unwrapping can't fail
            let lastElement = listSoFar.last!
            return listSoFar + [f(lastElement, next)]
        })
    }
}

(但我建议这不是一个很好的实现.)

(But I would suggest that that's not a very good implementation.)

这是一个非常有用的通用函数，可惜没有包含在标准库中.

This is a very useful general function, and it's a shame that it's not included in the standard library.

然后，您可以通过专门化起始值和操作来生成累积总和:

You can then generate your cumulative sum by specializing the starting value and operation:

let cumSum = els.scan(0, +)

你可以简单地省略零长度的情况:

And you can omit the zero-length case rather simply:

let cumSumTail = els.scan(0, +).dropFirst()

这篇关于快速运行总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！