Создание последовательности последовательностей вызывает StackOverflowException

Question

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

Я попытался прочитать в большом файле через функцию File.ReadLines, чтобы я мог выполнять итерацию по файлу по одной строке за один раз без необходимости хранить весь файл в памяти. Мой подход состоял в том, чтобы сгруппировать последовательность в последовательность меньших подпоследовательностей (по одному на файл, который должен быть выписан).

Я нашел полезную функцию, которую создал Томас Петричек на fssnip под названием groupWhen. Эта функция отлично поработала для моего первоначального тестирования на небольшом подмножестве файла, но при использовании реального файла возникает исключение StackoverflowException. Я не уверен, как настроить группу. Чтобы предотвратить эту функцию (я все еще являюсь зеленым цветом F #).

Вот упрощенная версия кода, показывая только соответствующие части, которые воссоздают StackoverflowExcpetion ::

// This is the function created by Tomas Petricek where the StackoverflowExcpetion is occuring 
module Seq = 
    /// Iterates over elements of the input sequence and groups adjacent elements. 
    /// A new group is started when the specified predicate holds about the element 
    /// of the sequence (and at the beginning of the iteration). 
    /// 
    /// For example: 
    /// Seq.groupWhen isOdd [3;3;2;4;1;2] = seq [[3]; [3; 2; 4]; [1; 2]] 
    let groupWhen f (input:seq<_>) = seq { 
    use en = input.GetEnumerator() 
    let running = ref true 

    // Generate a group starting with the current element. Stops generating 
    // when it founds element such that 'f en.Current' is 'true' 
    let rec group() = 
     [ yield en.Current 
     if en.MoveNext() then 
      if not (f en.Current) then yield! group() // *** Exception occurs here *** 
     else running := false ] 

    if en.MoveNext() then 
     // While there are still elements, start a new group 
     while running.Value do 
     yield group() |> Seq.ofList } 

Это суть кода делает функцию использования Tomas':

module Extractor = 

    open System 
    open System.IO 
    open Microsoft.FSharp.Reflection 

    // ... elided a few functions include "isNextObject" which is 
    //  a string -> bool (examines the line and returns true 
    //  if the string meets the criteria to that we are at the 
    //  start of the next inner file) 

    let writeFile outputDir file = 
     // ... write out "file" to the file system 
     // NOTE: file is a seq<string> 

    let writeFiles outputDir (files : seq<seq<_>>) = 
     files 
     |> Seq.iter (fun file -> writeFile outputDir file) 

И вот соответствующий код в консольном приложении, который использует следующие функции:

let lines = inputFile |> File.ReadLines 

writeFiles outputDir (lines |> Seq.groupWhen isNextObject) 

Любые идеи о правильном способе остановки группы. Когда вы дуете стек? Я не уверен, как бы преобразовать функцию для использования аккумулятора (или вместо этого использовать продолжение, которое, я думаю, является правильной терминологией).

Answer 1

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

Чтобы смягчить эту проблему, можно просто заменить список с ленивой последовательности:

let rec group() = seq { 
    yield en.Current 
    if en.MoveNext() then 
    if not (f en.Current) then yield! group() 
    else running := false } 

Однако, я хотел бы рассмотреть более радикальные подходы. Этот пример является хорошей иллюстрацией того, почему вам следует избегать самостоятельной рекурсии и вместо этого прибегать к готовым складкам.

Например, если судить по вашему описанию, возможно, что Seq.windowed может работать именно вам.

Answer 2

Легко использовать последовательности в F #, IMO. Вы можете случайно получить переполнение стека, а также медленные.

Так (на самом деле не отвечая на ваш вопрос), лично я бы просто сгиб с послед линий, используя что-то вроде этого:

let isNextObject line = 
    line = "---" 

type State = { 
    fileIndex : int 
    filename: string 
    writer: System.IO.TextWriter 
    } 

let makeFilename index = 
    sprintf "File%i" index 

let closeFile (state:State) = 
    //state.writer.Close() // would use this in real code 
    state.writer.WriteLine("=== Closing {0} ===",state.filename) 

let createFile index = 
    let newFilename = makeFilename index 
    let newWriter = System.Console.Out // dummy 
    newWriter.WriteLine("=== Creating {0} ===",newFilename) 
    // create new state with new writer 
    {fileIndex=index + 1; writer = newWriter; filename=newFilename } 

let writeLine (state:State) line = 
    if isNextObject line then 
     /// finish old file here  
     closeFile state 
     /// create new file here and return updated state 
     createFile state.fileIndex 
    else 
     //write the line to the current file 
     state.writer.WriteLine(line) 
     // return the unchanged state 
     state 

let processLines (lines: string seq) = 
    //setup 
    let initialState = createFile 1 
    // process the file 
    let finalState = lines |> Seq.fold writeLine initialState 
    // tidy up 
    closeFile finalState 

(Очевидно, что реальная версия будет использовать файлы, а не на консоли)

Да, это грубо, но это легко рассуждать, с никаких неприятных сюрпризов.

Вот тест:

processLines [ 
    "a"; "b" 
    "---";"c"; "d" 
    "---";"e"; "f" 
] 

А вот что выглядит результат:

=== Creating File1 === 
a 
b 
=== Closing File1 === 
=== Creating File2 === 
c 
d 
=== Closing File2 === 
=== Creating File3 === 
e 
f 
=== Closing File3 ===