时间戳

首页 > 解决方案 > 在 Kotlin 中以 O(n) 时间以纯函数式编程风格计算所有前缀和

kotlin - 在 Kotlin 中以 O(n) 时间以纯函数式编程风格计算所有前缀和

问题描述

是否可以在 Kotlin 的 O(n) 时间内以纯函数式编程风格计算数组的所有前缀和？

我所说的纯函数式编程的意思是允许仅对集合使用函数式编程扩展函数，例如_Collections,ktmap中的,reduce​​ , fold,sum等，而传统的命令式编程方法涉及更改状态和可变数据，例如普通循环，又名可变变量s，并且不允许使用可变数组。（我认为这符合维基百科上的定义）var

更具体地说，这里是我想要实现的一个例子，它是用在 O(n) 时间内运行的命令式编程编写的，另一个是在 O(n^2) 时间内运行的函数式编程。

fun prefixSumsImperative(numbers: IntArray): IntArray {
    val prefixSums = IntArray(numbers.size)
    var prefixSum = 0
    for ((i, number) in numbers.withIndex()) {
        prefixSum += number
        prefixSums[i] = prefixSum
    }
    return prefixSums
}

fun prefixSumsFunctionalONSquared(numbers: IntArray): IntArray =
    (0 until numbers.size).map { numbers.take(it).sum() }.toIntArray()

标签： kotlinfunctional-programmingpurely-functionalprefix-sum

解决方案

从 Kotlin 1.4 开始，您可以为此目的使用scan和函数：runningFold

fun prefixSumsFunctional(numbers: IntArray): IntArray =
    numbers.runningFold(0) { sum, num ->
        sum + num
    }.toIntArray()

推荐阅读