Предотвращение переполнения стека (с бесконечными последовательностями F# последовательностей)
Интеграционные тесты позволяют вам проверить все варианты использования вашего приложения.
Модульные тесты проверяют правильность низкоуровневой логики в вашем приложении.
Интеграционные тесты более полезны для менеджеров, чтобы они чувствовали себя в большей безопасности в отношении состояния проекта (но также полезны и для разработчиков!).
Модульные тесты более полезны для разработчиков, пишущих и изменяющих логику приложения.
И, конечно же, используйте их обоих для достижения наилучших результатов.
3 ответа
Вам обязательно стоит посетить
, но я постараюсь опубликовать более подробный ответ позже.
UPDATE
Хорошо, решение ниже. Он представляет последовательность Морриса как LazyList из LazyLists типа int, поскольку я предполагаю, что вы хотите, чтобы он был ленивым «в обоих направлениях».
LazyList F # (в 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 для длины, так как я думаю, что это приведет к переполнению int.
но два других уникальны для 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()
Использование памяти остается неизменным (менее 16M на моем компьютере) ... еще не закончил работу, но я быстро вычислил 55-ю длину, даже на моем медленном компьютере, поэтому я думаю, что это должно работать нормально. Также обратите внимание, что я использовал bignum для длины, так как я думаю, что это приведет к переполнению int.
но два других уникальны для 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()
Использование памяти остается неизменным (менее 16M на моем компьютере) ... еще не закончил работу, но я быстро вычислил 55-ю длину, даже на моем медленном компьютере, поэтому я думаю, что это должно работать нормально. Также обратите внимание, что я использовал bignum для длины, так как я думаю, что это приведет к переполнению int.
поэтому я думаю, что это должно работать нормально. Также обратите внимание, что я использовал bignum для длины, так как я думаю, что это приведет к переполнению int. поэтому я думаю, что это должно работать нормально. Также обратите внимание, что я использовал bignum для длины, так как я думаю, что это приведет к переполнению int.Просто сохраните предыдущий элемент, который вы искали.
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)
}
Я считаю, что здесь есть две основные проблемы:
Лень очень неэффективна, поэтому можно ожидать, что ленивая функциональная реализация будет работать на порядки медленнее. Например, реализация 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 ], которые можно было бы исключить и использовать функционально без значительного снижения производительности, если бы вы использовали структуру в качестве аккумулятора.