快速运行总和

Question

我想runningSum在一个数字数组(或任何有序的可添加东西的集合)上的函数返回一个相同长度的数组,其中每个元素i是A中所有元素的总和,直到包含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,除了它构建一个具有所有中间值的结果数组.

更一般的是拥有一个接受任何序列的函数,并提供一个输入序列的运行总和的序列.

Answer 1

您正在寻找的一般组合子通常被称为scan,并且可以定义(如列表中的所有高阶函数)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)]
        })
    }
}

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

这是一个非常有用的通用功能,遗憾的是它没有包含在标准库中.

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

let cumSum = els.scan(0, +)

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

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

Answer 2

斯威夫特4

一般序列情况

引用OP:

更一般的是拥有一个接受任何序列的函数,并提供一个输入序列的运行总和的序列.

Sequence比如说,考虑一些任意顺序(符合)

var seq = 1... // 1, 2, 3, ... (CountablePartialRangeFrom)

要创建另一个(懒惰)运行总和的序列seq,您可以使用全局sequence(state:next:)函数:

var runningSumSequence =
    sequence(state: (sum: 0, it: seq.makeIterator())) { state -> Int? in
    if let val = state.it.next() {
        defer { state.sum += val }
        return val + state.sum
    }
    else { return nil }
}

// Consume and print accumulated values less than 100
while let accumulatedSum = runningSumSequence.next(),
    accumulatedSum < 100 { print(accumulatedSum) }
// 1 3 6 10 15 21 28 36 45 55 66 78 91

// Consume and print next
print(runningSumSequence.next() ?? -1) // 120

// ...

如果我们愿意(为了它的乐趣),我们可以将封闭压缩到sequence(state:next:)上面:

var runningSumSequence =
    sequence(state: (sum: 0, it: seq.makeIterator())) {
        (state: inout (sum: Int, it: AnyIterator<Int>)) -> Int? in
        state.it.next().map { (state.sum + $0, state.sum += $0).0 }
}

但是,对于这些单行返回,类型推断往往会破坏(仍然是一些开放的错误,也许？)sequence(state:next:),迫使我们明确指定类型state,因此... in闭包中的粗糙.

或者:自定义序列累加器

protocol Accumulatable {
    static func +(lhs: Self, rhs: Self) -> Self
}
extension Int : Accumulatable {}

struct AccumulateSequence<T: Sequence>: Sequence, IteratorProtocol
where T.Element: Accumulatable {
    var iterator: T.Iterator
    var accumulatedValue: T.Element?

    init(_ sequence: T) {
        self.iterator = sequence.makeIterator()
    }

    mutating func next() -> T.Element? {
        if let val = iterator.next() {
            if accumulatedValue == nil {
                accumulatedValue = val
            }
            else { defer { accumulatedValue = accumulatedValue! + val } }
            return accumulatedValue

        }
        return nil
    }
}

var accumulator = AccumulateSequence(1...)

// Consume and print accumulated values less than 100
while let accumulatedSum = accumulator.next(),
    accumulatedSum < 100 { print(accumulatedSum) }
// 1 3 6 10 15 21 28 36 45 55 66 78 91

具体数组案例:使用 reduce(into:_:)

从Swift 4开始,我们可以使用reduce(into:_:)将运行总和累积到数组中.

let runningSum = arr
    .reduce(into: []) { $0.append(($0.last ?? 0) + $1) }
    // [2, 4, 6, 8, 10, 12]

通过使用reduce(into:_:),[Int]累加器将不会在后续的reduce迭代中被复制; 引用语言参考:

reduce(_:_:)当结果是写时复制类型(例如a Array或a) 时,此方法优于效率Dictionary.

另请参见实现reduce(into:_:),指出累加器是作为inout提供的闭包的参数提供的.

但是,每次迭代仍会导致append(_:)对累加器数组的调用; O(1)在许多调用中平均摊销,但在这里仍然是一个可以说是不必要的开销,因为我们知道累加器的最终大小.

因为数组使用指数策略增加其分配的容量,所以将单个元素附加到数组是O(1)对该append(_:)方法的多次调用求平均值时的操作.当一个数组具有额外的容量而没有与另一个实例共享其存储时,附加一个元素就是O(1).当一个数组需要在附加之前重新分配存储或者它的存储与另一个副本共享时,附加是O(n),其中n是数组的长度.

因此,知道累加器的最终大小,我们可以明确地保留它的使用容量reserveCapacity(_:)(例如,对于本机实现map(_:))

let runningSum = arr
    .reduce(into: [Int]()) { (sums, element) in
        if let sum = sums.last {
            sums.append(sum + element)
        }
        else {
            sums.reserveCapacity(arr.count)
            sums.append(element)
        }
} // [2, 4, 6, 8, 10, 12]

为了它的喜悦,浓缩:

let runningSum = arr
    .reduce(into: []) {
        $0.append(($0.last ?? ($0.reserveCapacity(arr.count), 0).1) + $1)
} // [2, 4, 6, 8, 10, 12]

Swift 3:enumerated()用于后续调用reduce

另一个Swift 3替代方案(带有开销......)enumerated().map与reduce每个元素映射结合使用:

func runningSum(_ arr: [Int]) -> [Int] {
    return arr.enumerated().map { arr.prefix($0).reduce($1, +) }
} /* thanks @Hamish for improvement! */

let arr = [2, 2, 2, 2, 2, 2]
print(runningSum(arr)) // [2, 4, 6, 8, 10, 12]

好处是你不必在一个数组中使用数组作为收集器reduce(而是反复调用reduce).

Answer 3

只是为了好玩：一线运行的总和：

let arr = [1, 2, 3, 4]

let rs = arr.map({ () -> (Int) -> Int in var s = 0; return { (s += $0, s).1 } }())

print(rs) // [1, 3, 6, 10]

它的作用与JAL的答案中的（更新的）代码相同，特别是不会生成任何中间数组。sum变量在立即求值的闭包中捕获，并返回转换。