假设我有一个数字列表，我需要知道从一开始就必须选择多少个元素才能至少获得所需的总和。
该算法很简单：我从列表的开头选择数字，直到所有选择的数字之和超过一定数量为止。
我可以这样写命令式的代码：
fun pickEnough(list: List<Double>, enough: Double): List<Double>? {
var soFar = 0.0
var index = 0
for (index in 0..list.size) {
soFar += list[index]
if (soFar > enough) {
return list.subList(0, index)
}
}
return null
}
一种效率低下但更通用的解决方案是生成所有可能的子列表，并选择第一个其缩减结果足够好的子列表：
fun <T> pickEnough(list: List<T>, reducer: (T, T) -> T, enough: (T) -> Boolean): List<T>? =
list.indices
.map { index -> list.sublist(0, index) }
.first { sublist -> enough(sublist.reduce(reducer)) }
pickEnough(listOf(5,8,0,0,8), { a, b -> a + b}, { it > 10 }) // [5, 8]
是否有既定的功能惯用法，或者可能是比我尝试概括此功能更好的性能和表达能力的组合？
该示例在Kotlin中进行，但我更喜欢与语言无关的答案，尽管可以接受任何语言的答案，只要它们呈现了描述此操作的高级成语即可。
您想要的是一个scan后跟一个takeWhile。scan就像折叠一样，除了它返回一系列连续的状态值。您可以返回一对连续状态，(x, soFar)其中包含序列中的当前值和当前运行总计。然后，您可以从该序列中获取尽可能多的数据，其中当前值尚未导致超出所需的总数。例如，在F＃中，您可以执行以下操作：
let pickEnough (l: seq<double>) (enough: double): seq<double> =
Seq.scan (fun (_, soFar) x -> (x, x+soFar)) (0.0, 0.0) l |>
Seq.skip 1 |>
Seq.takeWhile (fun (x, soFar) -> soFar - x < enough) |>
Seq.map fst
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句