为什么在遍历大型CSV文件时，Seq会导致堆栈溢出？

Question

我有一个csv文件，结构如下：

1. 第一行是标题行
2. 其余行是数据行，每行都有相同数量的逗号，因此我们可以按列来处理数据

我编写了一个小脚本来遍历文件的每一行，并返回一个元组序列，其中包含列标题和该列中最大数据字符串的长度：

let getColumnInfo (fileName:string) =
    let delimiter = ','

    let readLinesIntoColumns (sr:StreamReader) = seq { 
        while not sr.EndOfStream do     
            yield sr.ReadLine().Split(delimiter) |> Seq.map (fun c -> c.Length )
    }

    use sr = new StreamReader(fileName)     
    let headers = sr.ReadLine().Split(delimiter) 
    let columnSizes =
        let initial = Seq.map ( fun h -> 0 ) headers
        let toMaxColLengths (accumulator:seq<int>) (line:seq<int>)  = 
             let chooseBigger a b = if a > b then a else b
             Seq.map2 chooseBigger accumulator line
        readLinesIntoColumns sr |> Seq.fold toMaxColLengths initial
    Seq.zip headers columnSizes;

这个在小文件上运行良好。但是当它尝试处理一个大文件（> 75 Mb）时，它会因为 StackOverflow 异常而使 fsi 崩溃。如果我删除这一行

Seq.map2 chooseBigger accumulator line

程序执行完毕。

现在，我的问题是：为什么F#会占用堆栈？我对F#中的序列的理解是，整个序列不会被保存在内存中，只有正在处理的元素。因此，我期望已经处理过的行不会留在堆栈中。我的误解出在哪里？

- Aidan

---

75Mb文件中有多少行和列？ - pad

我不知道。至少50,000。并不是因为我想让它工作，而是我更好奇为什么我对F#的理解不足。（虽然让它工作也很好） - Aidan

如果你这样做会发生什么：Seq.map2 chooseBigger accumulator line |> Seq.toList |> seq？ - Daniel

这确实修复了 StackOverflow。我认为你关于惰性导致堆栈溢出的观点是正确的。 - Aidan

Answer 1

我认为这是一个很好的问题。以下是一个更简单的复现：

let test n =
    [for i in 1 .. n -> Seq.empty]
    |> List.fold (Seq.map2 max) Seq.empty
    |> Seq.iter ignore

test创建了一系列空序列，按行计算最大值，然后迭代生成的（空）序列。当 n 的值很高时，即使根本没有值可迭代，这也会导致堆栈溢出！

有点棘手，但我试着解释一下。问题是，当您在序列上进行折叠操作时，Seq.map2 返回一个新序列，该序列延迟其工作直到枚举为止。因此，当您尝试遍历生成的序列时，您最终会调用到一个深度为 n 的计算链中。

如Daniel所解释的，您可以通过及时评估结果序列（例如将其转换为列表）来避免此问题。

编辑

这里尝试进一步解释出了错误的原因。当您调用 Seq.map2 max s1 s2 时，既不会枚举 s1 也不会枚举 s2；您会得到一个新序列，当枚举它时，将枚举它们并比较生成的值。因此，如果我们执行以下操作：

let s0 = Seq.empty
let s1 = Seq.map2 max Seq.emtpy s0
let s2 = Seq.map2 max Seq.emtpy s1
let s3 = Seq.map2 max Seq.emtpy s2
let s4 = Seq.map2 max Seq.emtpy s3
let s5 = Seq.map2 max Seq.emtpy s4
...

然后调用Seq.map2总是立即返回并使用恒定的堆栈空间。然而，枚举s5需要枚举s4，这又需要枚举s3等等。这意味着枚举s99999将会建立一个巨大的调用堆栈，看起来有点像：

...
(s99996's enumerator).MoveNext()
(s99997's enumerator).MoveNext()
(s99998's enumerator).MoveNext()
(s99999's enumerator).MoveNext()

否则会出现堆栈溢出。

- kvb

---

显然，我的逻辑是错误的，因为它适用于较小的文件。我开始走和你一样的路线，但我不明白它怎么会导致堆栈溢出（也许是内存不足）。 - Daniel

@Daniel - 我尝试对我的解释进行扩展。如果这样清楚了，请告诉我。 - kvb

Answer 2

你的代码中包含如此多的序列，以至于很难理解。我猜这就是导致你失误的原因。你可以让它更简单、更高效（渴望并不全是坏事）：

let getColumnInfo (fileName:string) =
  let delimiter = ','
  use sr = new StreamReader(fileName)
  match sr.ReadLine() with
  | null | "" -> Array.empty
  | hdr ->
    let cols = hdr.Split(delimiter)
    let counts = Array.zeroCreate cols.Length
    while not sr.EndOfStream do
      sr.ReadLine().Split(delimiter)
      |> Array.iteri (fun i fld ->
        counts.[i] <- max counts.[i] fld.Length)
    Array.zip cols counts

这里假设所有行都是非空的，并且具有相同数量的列。

您可以通过将此行更改为以下内容来修复您的功能：

Seq.map2 chooseBigger accumulator line |> Seq.toList |> seq

- Daniel

---

它并没有直接回答这个问题，是吗？ - pad

不，它并没有解决问题，但它指出了问题的可能来源（过于懒惰）。采用更简单的方法很可能会避免难以发现的错误。 - Daniel

如果我想让别人指出懒惰是我问题的根源，我就会问我的妻子 :-) - Aidan

她可能会告诉你同样的事情：热情并不全是坏事。 - Daniel

我不明白。尽管“state”被覆盖了，但“x”保持不变。问题出在哪里？ - pad

我认为你在更新中对“将line与自身压缩”这一逻辑的理解不正确（除非我读错了）。显然这不会导致无限循环，因为原帖指出该函数适用于小文件。 - kvb

Answer 3

为什么 F# 会占用堆栈？我对 F# 中序列的理解是，整个序列不会被保存在内存中，只有正在处理的元素。因此，我期望已经处理过的行不会留在堆栈上。我的误解出在哪里？

实际上，这些行本身并没有占用你的堆栈空间。问题在于，你不小心编写了一个函数，它构建了一个巨大的未求值计算（thunk 树），当它被评估时，由于进行了非尾调用 O(n) 次，导致堆栈溢出。每当你从其他序列构建序列而不强制求值时，就容易发生这种情况。

- J D