为什么Seq在迭代大型csv文件时会给堆栈溢出

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#中的序列的理解是整个序列不保存在内存中,只保存在正在处理的元素中.因此,我预计已处理的行不会保留在堆栈中.我的误会在哪里？

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深层计算层链.

正如丹尼尔解释的那样,你可以通过急切地评估结果序列(例如将其转换为列表)来逃避这一点.

编辑

这是尝试进一步解释出现了什么问题.当你打电话时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()

我们会得到一个堆栈溢出.