避免堆溢出(F#无限序列的序列)

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

题

我有这个"学习码"我写的对于莫里斯seq 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.n但你只能得到这么远的前你打了一堆溢出。一位递归我是尾递归和它在本质上建立一个联的组员.那不是问题所在。这就是当"enum"是所谓的上说的4000th序列。注意，是用F#1.9.6.16，以前版本的平顶上述14000).这是因为方式的联序得到解决。该序列被偷懒，因此，"递归"是懒惰。就是说，seq n呼吁seq n-1其中要求seq n-2等获得第一个项目(第一#是最糟糕的情况下)。

我明白了 [|0|] |> Seq.append str |> Seq.windowed 2, 是我的问题变得更糟，我可以三倍#我可以生成的，如果我取消。实际上发言的代码工作不够好。该3125th迭代的莫里斯将超过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))

这basicially创建一个真正的长链的Seq处理功能的电话产生的sequnces.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模块，该模块实施的追加，对扫描和收集使用continutions现在我可以开始产生和印刷出50,000seq没有一个问题(它永远不会完成，因为它是在10^5697数字长)。

一些附加的注释：

  • 延续了成语我一直在寻找，但是在这种情况下，他们不得不去到F#库，不是我的代码。我学会了关于延续F#从 托马斯Petricek的 真实世界的编程功能 书。
  • 懒惰的列表的回答，我接受举行的其他成语;懒惰的评估。在我改写的图书馆，我也不得不利用的懒惰的类型计算器，以避免.
  • 懒惰的清单版本sorta的工作由运(或许通过设计但是这超出了我的当前能力来确定)-该活动的模式匹配它使用的话，这是建设和迭代的原因列表计算值之前，需要递归变得太深，所以它是懒惰，但不那么懒，它需要的延续，以避免计算器.例如，通过时间的第2次序需要一个数字从第1次序，它已经计算的。换句话说，LL版本不是严格实懒惰为序列的产生，只列出管理。
有帮助吗？

解决方案

你一定要看看

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(类型)，但其他两个独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长快速，甚至在我的慢速箱，因此，我认为这应该只是罚款。还注意我用'于是的长度，因为我认为这将溢出的一个'int'.

其他提示

我认为有两个主要问题：

  • 懒惰的效率非常低，所以你可以期待一个懒惰的功能实施的运行订单的幅度较慢。例如，Haskell的执行情况的描述 在这里， 2 400×慢于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