F#:有效地从 List.scan 获取最后一个状态

Question

我正在一个非常大的列表上运行List.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

在 F# 4.0 中，添加了List.mapFold，这很好地实现了此功能。

[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的解决方案可能是最快和最简单的。

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

我认为

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

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