Предотвращение переполнения стека (с бесконечными последовательностями последовательностей F#)

StackOverflow https://stackoverflow.com/questions/898988

Вопрос

У меня есть «обучающий код», который я написал для последовательности Морриса в f #, которая страдает от переполнения стека, которого я не знаю, как избежать.«Моррис» возвращает бесконечную последовательность последовательностей «посмотри и скажи» (т. е. {{1}, {1,1}, {2,1}, {1,2,1,1}, {1,1,1 ,2,2,1}, {3,1,2,2,1,1},...}).

    let printList l =
        Seq.iter (fun n -> printf "%i" n) l
        printfn ""

    let rec morris s = 
        let next str = seq {
            let cnt = ref 1  // Stack overflow is below when enumerating
            for cur in [|0|] |> Seq.append str |> Seq.windowed 2 do
                if cur.[0] <> cur.[1] then
                    yield!( [!cnt ; cur.[0]] )
                    cnt := 0
                incr cnt
        }
        seq {
        yield s
        yield! morris (next s) // tail recursion, no stack overflow
        }

    // "main"
    // Print the nth iteration
    let _ =  [1] |> morris |> Seq.nth 3125 |> printList

Вы можете выбрать n-ю итерацию, используя Seq.nth, но вы сможете продвинуться так далеко, прежде чем достигнете переполнения стека.Единственная часть рекурсии, которая у меня есть, — это хвостовая рекурсия, и она, по сути, создает связанный набор перечислителей.Проблема не в этом.Это когда «enum» вызывается, скажем, в 4000-й последовательности.Обратите внимание, что в F# 1.9.6.16 предыдущая версия превысила 14000).Это связано с тем, как разрешаются связанные последовательности.Последовательности ленивы, поэтому «рекурсия» ленива.То есть, seq n вызывает seq n-1, который вызывает seq n-2 и т. д., чтобы получить первый элемент (самый первый # — худший случай).

Я это понимаю [|0|] |> Seq.append str |> Seq.windowed 2, усугубляет мою проблему, и я мог бы утроить #, который мог бы сгенерировать, если бы устранил это.С практической точки зрения код работает достаточно хорошо.3125-я итерация Морриса будет иметь длину более 10^359 символов.

Проблема, которую я действительно пытаюсь решить, заключается в том, как сохранить ленивую оценку и не иметь ограничений на размер стека для итерации, которую я могу выбрать.Я ищу правильную идиому F #, чтобы установить ограничение на основе размера памяти.

Обновление, октябрь 2010 г.

Изучив немного лучше F#, немного Haskell, размышляя и исследуя эту проблему больше года, я наконец могу ответить на свой вопрос.Но, как всегда бывает с трудными задачами, проблема начинается с неправильного вопроса.Проблема не в последовательностях последовательностей, а в том, что последовательность определяется рекурсивно.Мои навыки функционального программирования теперь немного улучшились, и поэтому легче понять, что происходит с версией ниже, которая все еще получает переполнение стека.

let next str = 
    Seq.append str [0]
    |> Seq.pairwise
    |> Seq.scan (fun (n,_) (c,v) ->
            if (c = v) then (n+1,Seq.empty)
            else (1,Seq.ofList [n;c]) ) (1,Seq.empty)
    |> Seq.collect snd

let morris = Seq.unfold(fun sq -> Some(sq,next sq))

По сути, это создает очень длинную цепочку вызовов функций обработки Seq для генерации последовательностей.Модуль Seq, поставляемый с F#, — это то, что не может следовать по цепочке без использования стека.Существует оптимизация, которую он использует для добавления и рекурсивно определенных последовательностей, но эта оптимизация работает только в том случае, если рекурсия реализует добавление.

Так что это сработает

let rec ints n = seq { yield n; yield! ints (n+1) }
printf "%A" (ints 0 |> Seq.nth 100000);;

И этот получит stackoverflow.

let rec ints n = seq { yield n; yield! (ints (n+1)|> Seq.map id) }
printf "%A" (ints 0 |> Seq.nth 100000);;

Чтобы доказать, что проблема в библиотеке F #, я написал свой собственный модуль Seq, который реализовал добавление, попарное сканирование, сканирование и сбор с использованием продолжений, и теперь я могу без проблем начать генерировать и распечатывать 50 000 последовательностей (он никогда не закончится, поскольку все закончилось). длиной 10^5697 цифр).

Некоторые дополнительные примечания:

  • Продолжения — это та идиома, которую я искал, но в данном случае они должны были идти в библиотеку F#, а не в мой код.Я узнал о продолжениях в F# из Томас Петричек Реальное функциональное программирование книга.
  • Ответ на ленивый список, который я принял, содержал другую идиому;ленивая оценка.В моей переписанной библиотеке мне также пришлось использовать ленивый тип, чтобы избежать переполнения стека.
  • Версия ленивого списка работает как бы по счастливой случайности (возможно, по замыслу, но это за пределами моих текущих возможностей определить) - сопоставление активного шаблона, которое она использует во время построения и итерации, заставляет списки вычислять значения до того, как требуемая рекурсия станет слишком глубокой, поэтому это лениво, но не настолько лениво, что нужны продолжения, чтобы избежать переполнения стека.Например, к тому моменту, когда второй последовательности понадобится цифра из первой последовательности, она уже будет вычислена.Другими словами, версия LL не является строго JIT-ленивой для генерации последовательностей, а только для управления списками.
Это было полезно?

Решение

Вам обязательно стоит проверить

http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/FSharp.PowerPack/Microsoft.FSharp.Collections.LazyList.html

но я постараюсь опубликовать более полный ответ позже.

ОБНОВЛЯТЬ

Хорошо, решение ниже.Он представляет последовательность Морриса как LazyList LazyLists int, поскольку я предполагаю, что вы хотите, чтобы она была ленивой в «обаих направлениях».

F# LazyList (в FSharp.PowerPack.dll) имеет три полезных свойства:

  • это лениво (вычисление n-го элемента не произойдет, пока он не будет потребован первым)
  • он не выполняет перерасчет (повторная оценка n-го элемента в том же экземпляре объекта не приведет к его повторному вычислению - он кэширует каждый элемент после его первого вычисления)
  • вы можете «забыть» префиксы (когда вы «вбегаете» в список, префикс, на который больше нет ссылок, доступен для сборки мусора)

Первое свойство является общим для seq (IEnumerable), но два других уникальны для LazyList и очень полезны для вычислительных задач, подобных той, которая поставлена ​​в этом вопросе.

Без лишних слов, код:

// print a lazy list up to some max depth
let rec PrintList n ll =
    match n with
    | 0 -> printfn ""
    | _ -> match ll with
           | LazyList.Nil -> printfn ""
           | LazyList.Cons(x,xs) ->
               printf "%d" x
               PrintList (n-1) xs

// NextMorris : LazyList<int> -> LazyList<int>
let rec NextMorris (LazyList.Cons(cur,rest)) = 
    let count = ref 1
    let ll = ref rest
    while LazyList.nonempty !ll && (LazyList.hd !ll) = cur do
        ll := LazyList.tl !ll
        incr count
    LazyList.cons !count
        (LazyList.consf cur (fun() ->
            if LazyList.nonempty !ll then
                NextMorris !ll
            else
                LazyList.empty()))

// Morris : LazyList<int> -> LazyList<LazyList<int>>
let Morris s =
    let rec MakeMorris ll =
        LazyList.consf ll (fun () ->
            let next = NextMorris ll
            MakeMorris next
        )
    MakeMorris s

// "main"
// Print the nth iteration, up to a certain depth
[1] |> LazyList.of_list |> Morris |> Seq.nth 3125 |> PrintList 10
[1] |> LazyList.of_list |> Morris |> Seq.nth 3126 |> PrintList 10
[1] |> LazyList.of_list |> Morris |> Seq.nth 100000 |> PrintList 35
[1] |> LazyList.of_list |> Morris |> Seq.nth 100001 |> PrintList 35

ОБНОВЛЕНИЕ2

Если вы просто хотите посчитать, это тоже нормально:

let LLLength ll =
    let rec Loop ll acc =
        match ll with
        | LazyList.Cons(_,rest) -> Loop rest (acc+1N)
        | _ -> acc
    Loop ll 0N

let Main() =
    // don't do line below, it leaks
    //let hundredth = [1] |> LazyList.of_list |> Morris |> Seq.nth 100
    // if we only want to count length, make sure we throw away the only
    // copy as we traverse it to count
    [1] |> LazyList.of_list |> Morris |> Seq.nth 100
        |> LLLength |> printfn "%A" 
Main()

Использование памяти остается неизменным (менее 16 МБ на моем компьютере)...еще не закончил бег, но я быстро рассчитал 55-ю длину, даже на своем медленном боксе, так что думаю, все должно работать нормально.Также обратите внимание, что я использовал «bignum» для длины, так как думаю, что это приведет к переполнению «int».

Другие советы

Я считаю, что здесь есть две основные проблемы:

  • Ленивость очень неэффективна, поэтому можно ожидать, что ленивая функциональная реализация будет работать на несколько порядков медленнее.Например, описанная реализация Haskell здесь в 2400 раз медленнее, чем F#, который я привожу ниже.Если вам нужен обходной путь, лучше всего, вероятно, амортизировать вычисления, объединив их в нетерпеливые пакеты, где пакеты создаются по требованию.

  • А Seq.append функция фактически вызывает код C# из IEnumerable и, следовательно, его хвостовой вызов не устраняется, и каждый раз, когда вы проходите через него, вы теряете немного больше места в стеке.Это проявляется, когда вы начинаете перебирать последовательность.

Следующий пример более чем в 80 раз быстрее вашей реализации при вычислении длины 50-й подпоследовательности, но, возможно, он недостаточно ленив для вас:

let next (xs: ResizeArray<_>) =
  let ys = ResizeArray()
  let add n x =
    if n > 0 then
      ys.Add n
      ys.Add x
  let mutable n = 0
  let mutable x = 0
  for i=0 to xs.Count-1 do
    let x' = xs.[i]
    if x=x' then
      n <- n + 1
    else
      add n x
      n <- 1
      x <- x'
  add n x
  ys

let morris =
  Seq.unfold (fun xs -> Some(xs, next xs)) (ResizeArray [1])

Ядром этой функции является складка над ResizeArray это можно было бы вынести за рамки и использовать функционально без слишком большого снижения производительности, если бы вы использовали структуру в качестве аккумулятора.

Просто сохраните предыдущий элемент, который вы искали.

let morris2 data = seq {
    let cnt = ref 0
    let prev = ref (data |> Seq.nth 0)

     for cur in data do
        if cur <> !prev then
            yield! [!cnt; !prev]
            cnt := 1
            prev := cur
        else
            cnt := !cnt + 1

    yield! [!cnt; !prev]
}

let rec morrisSeq2 cur = seq {
    yield cur
    yield! morrisSeq2 (morris2 cur)
}
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top