Почему Seq дает переполнение стека при переборе большого CSV-файла - PullRequest
Новая
       10

Почему Seq дает переполнение стека при переборе большого CSV-файла

4 голосов
/ 09 марта 2012

У меня есть 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 Мб), он выдает fsi с исключением StackOverflow. Если я уберу строку 

Seq.map2 chooseBigger accumulator line

Программа завершена.

Теперь мой вопрос таков: почему F # использует стек? Мое понимание последовательностей в F # заключается в том, что вся последовательность не хранится в памяти, а только элементы, которые обрабатываются. Поэтому я ожидал, что уже обработанные строки не останутся в стеке. Где мое недоразумение?

Ответы [ 3 ]

6 голосов
/ 09 марта 2012

Я думаю, что это хороший вопрос. Вот более простое воспроизведение: 

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 слоев глубиной.

Как объясняет Даниил, вы можете избежать этого, с нетерпением оценив результирующую последовательность (например, преобразовав ее в список).

EDIT

Вот попытка объяснить, что происходит не так. Когда вы звоните 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()

и мы получим переполнение стека.

2 голосов
/ 09 марта 2012

Ваш код содержит так много последовательностей, о которых трудно рассуждать. Я думаю, это то, что сбивает вас с толку. Вы можете сделать это намного проще и эффективнее (рвение не так уж плохо): 

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
1 голос
/ 10 марта 2012

почему F # использует стек?Мое понимание последовательностей в F # заключается в том, что вся последовательность не хранится в памяти, а только элементы, которые обрабатываются.Поэтому я ожидал, что уже обработанные строки не останутся в стеке.Где мое недоразумение?

Сами строки не занимают место в вашем стеке.Проблема в том, что вы случайно написали функцию, которая создает огромное неоцененное вычисление (дерево thunks), которое переполняется стеком при его оценке, потому что оно делает не-хвостовые вызовы O (n) глубокими.Это имеет место, когда вы строите последовательности из других последовательностей и не форсируете оценку чего-либо.

...