Предотвращение переполнения стека (с F# бесконечными последовательностями последовательностей)
У меня есть этот "обучающий код", который я написал для последовательности Морриса в F#, который страдает от переполнения стека, которого я не знаю, как избежать. "morris" возвращает бесконечную последовательность последовательностей "видеть и говорить" (т. е. {{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 символов в длину.
Проблема, которую я действительно пытаюсь решить, состоит в том, как сохранить ленивый eval и не иметь ограничений по размеру стека для итерации, которую я могу выбрать. Я ищу правильную идиому F#, чтобы сделать ограничение на основе объема памяти.
Обновление Окт 10
После изучения 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);;
И этот получит переполнение стека.
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 seq (он никогда не закончится, так как он закончился 10^5697 цифр).
Некоторые дополнительные заметки:
- Продолжения были той формой, которую я искал, но в этом случае они должны были войти в библиотеку F#, а не в мой код. Я узнал о продолжениях на F# из книги Томаса Петричека по функциональному программированию в реальном мире.
- Ответ ленивого списка, который я принял, содержал другую идиому; ленивая оценка. В моей переписанной библиотеке мне также пришлось использовать ленивый тип, чтобы избежать переполнения стека.
- Версия с отложенным списком работает по счастливой случайности (может быть, по замыслу, но это не в моей нынешней способности определить) - сопоставление с активным шаблоном, которое оно использует при создании и итерации, заставляет списки вычислять значения до того, как требуемая рекурсия становится слишком глубокой, это ленивый, но не такой ленивый, он нуждается в продолжениях, чтобы избежать переполнения стека. Например, к тому моменту, когда 2-й последовательности требуется цифра из 1-й последовательности, она уже рассчитана. Другими словами, LL-версия не является строго JIT-ленивой для генерации последовательности, а только для управления списком.
3 ответа
Вы должны обязательно проверить
но я постараюсь опубликовать более полный ответ позже.
ОБНОВИТЬ
Хорошо, решение ниже. Он представляет последовательность Морриса как 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
UPDATE2
Если вы просто хотите считать, это тоже хорошо:
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's для длины, так как я думаю, что это переполнит' int '.
I believe there are two main problems here:
Лень очень неэффективна, поэтому вы можете ожидать, что ленивая функциональная реализация будет работать на порядки медленнее. Например, реализация 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)
}