F#：有效地从 List.scan 获取最后状态

Question

我运行 List.scan 遍历了一个非常大的列表，以便计算运行总数。完成后，除了扫描输出之外，我还需要总数，以便不均匀地划分列表。 total是scan输出的最后一个状态，我真的很想避免为了得到最终状态而额外遍历列表。我能想到的唯一方法是传递一个可变引用来累加总数。有没有更好的方法来解决这个问题？

let l = <very large list of int64>
let runningTotal=List.scan (fun s x -> x+s) 0L l
let total= <last element of runningTotal- very inefficient>
doSomething total runningTotal

Answer 1

我认为实际上只访问列表中的最后一个元素确实是不可能的。也就是说，你说，你的清单非常大。当涉及到非常大的输入时，列表可能不是开始时的最佳数据结构。我想到的是，在这种情况下您当然可以使用数组而不是列表。数组也比列表更节省内存，因为列表将为每个元素创建一个引用，每个元素大约 12 个字节。而数组只有对第一个元素的引用。

如果数组适合您，那么这就是解决方案，因为您可以在没有 O(n) 开销的情况下访问数组的最后一个元素。

Answer 2

这是一种方法。由于我们可以定义 lambda 来做任何事情，只需让它始终将结果存储在 ref 单元格中即可。由于扫描从头到尾进行，结果将是最后一个值。

let last = ref 0L
let l = <very large list of int64>
let runningTotal=List.scan (fun s x ->let t = x+s;last=:t;t) 0L l
let total= !last
doSomething total runningTotal

Answer 3

在 F# 4.0 中，List.mapFold 变为 added，这很好地实现了这一点。

[1;2;3;4] |> List.mapFold (fun state elem -> let nxt = state + elem in (nxt,nxt)) 0

// > val it : int list * int = ([1; 3; 6; 10], 10)

List.last 也在 4.0 中添加，尽管它的性能仍然是 O(n)。如果您想从 F# 3.1 及更早版本的列表中提取最后一个元素，可以使用 fold 来完成，但同样，这是 O(n)。

let last lst =
    lst |> List.fold (fun _ x -> x) Unchecked.defaultof<_>

@John 的解决方案可能是最快和最简单的。

F#：有效地从 List.scan 获取最后状态

F#: Efficiently get last state from List.scan

f#

list