在 Kotlin 中以 O(n) 时间以纯函数式编程风格计算所有前缀和
Compute all prefix sums in purely functional programming style in O(n) time in Kotlin
是否可以在 Kotlin 中以 O(n) 时间计算 purely functional programming 样式的数字数组的所有前缀和?
我所说的纯函数式编程的意思是只允许对集合使用函数式编程扩展函数,例如map
、reduce
、fold
、sum
等. 在 _Collections,kt 中,虽然涉及更改状态和可变数据的传统命令式编程方法(例如普通循环)、可变变量又名 var
s 和可变数组是不允许的。 (我认为这符合维基百科上的定义)
更具体地说,这是我想要实现的一个例子,它是在 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()
此解决方案满足您对功能样式的所有要求:
fun prefixSumsFunctional(numbers: IntArray): IntArray =
numbers.fold(listOf<Int>()) { result, el ->
if (result.isEmpty()) {
result + el
} else {
result + (result.last() + el)
}
}.toIntArray()
不幸的是,解决这个问题需要持久堆栈,标准 Kotlin 库中没有。但是stack可以用pair来模仿:
fun prefixSumsFunctionalPuzzler(numbers: IntArray): IntArray =
generateSequence(numbers.fold(Any() to 0) { stack, value ->
stack to stack.second + value
}) { it.first as Pair<Any, Int> }
.map { it.second }
.take(numbers.size)
.toList().asReversed().toIntArray()
从 Kotlin 1.4 开始,您可以为此目的使用 scan
和 runningFold
函数:
fun prefixSumsFunctional(numbers: IntArray): IntArray =
numbers.runningFold(0) { sum, num ->
sum + num
}.toIntArray()
是否可以在 Kotlin 中以 O(n) 时间计算 purely functional programming 样式的数字数组的所有前缀和?
我所说的纯函数式编程的意思是只允许对集合使用函数式编程扩展函数,例如map
、reduce
、fold
、sum
等. 在 _Collections,kt 中,虽然涉及更改状态和可变数据的传统命令式编程方法(例如普通循环)、可变变量又名 var
s 和可变数组是不允许的。 (我认为这符合维基百科上的定义)
更具体地说,这是我想要实现的一个例子,它是在 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()
此解决方案满足您对功能样式的所有要求:
fun prefixSumsFunctional(numbers: IntArray): IntArray =
numbers.fold(listOf<Int>()) { result, el ->
if (result.isEmpty()) {
result + el
} else {
result + (result.last() + el)
}
}.toIntArray()
不幸的是,解决这个问题需要持久堆栈,标准 Kotlin 库中没有。但是stack可以用pair来模仿:
fun prefixSumsFunctionalPuzzler(numbers: IntArray): IntArray =
generateSequence(numbers.fold(Any() to 0) { stack, value ->
stack to stack.second + value
}) { it.first as Pair<Any, Int> }
.map { it.second }
.take(numbers.size)
.toList().asReversed().toIntArray()
从 Kotlin 1.4 开始,您可以为此目的使用 scan
和 runningFold
函数:
fun prefixSumsFunctional(numbers: IntArray): IntArray =
numbers.runningFold(0) { sum, num ->
sum + num
}.toIntArray()