避免堆栈溢出（使用F＃无限序列的序列）

我有我为f＃中的morris seq编写的“学习代码”，该代码遭遇堆栈溢出，我不知道如何避免。 “morris”返回无限序列的“see and say”序列（即{{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 

您可以使用Seq.nth选择第n次迭代，但在达到堆栈溢出前，您只能获得如此之多的结果。 递归的一点是尾递归，它实质上构建了一组链接的枚举器。 这不是问题所在。 它是在第4000个序列中调用“枚举”的时候。 请注意，使用F＃1.9.6.16，以前的版本超过14000）。 这是因为链接序列被解析的方式。 序列是懒惰的，所以“递归”是懒惰的。 也就是说，seq n调用seq n-1调用seq n-2等等来获得第一个项目（第一个＃是最差的情况）。

我明白[|0|] |> Seq.append str |> Seq.windowed 2 ，会让我的问题变得更糟，如果我消除了这个问题，我可以将＃产生的三倍。 实际上，代码工作得很好。 morris的第3125次迭代的长度将超过10 ^ 359个字符。

我真正想要解决的问题是如何保留惰性评估，并根据迭代的堆栈大小设置无限制。 我正在寻找适当的F＃成语，以根据内存大小制定限制。

10月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处理函数调用链来生成序列。 F＃附带的Seq模块是不能在不使用堆栈的情况下跟随链的。 有一个优化用于追加和递归定义的序列，但只有当递归实现附加时，该优化才有效。

所以这会起作用

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＃libary是个问题，我编写了自己的Seq模块，它实现了append，pairwise，scan和collectution使用连续性，现在我可以开始生成和打印50,000 seq没有问题（它会永远不会完成，因为它已经结束10 ^ 5697位数字）。

一些附加说明：

继续是我正在寻找的成语，但在这种情况下，他们必须进入F＃库，而不是我的代码。 我从Tomas Petricek的真实世界功能编程书中了解到F＃中的延续。

我接受的懒惰列表答案持有另一个成语; 懒惰的评价。 在我重写的库中，我还必须利用惰性类型来避免堆栈溢出。

惰性列表版本排序由运气（也许通过设计，但超出了我当前的判断能力） - 它在构建和迭代时使用的活动模式匹配导致列表在所需递归变得太深之前计算值，所以它很懒，但不是很懒，它需要延续才能避免堆栈溢出。 例如，当第二个序列需要第一个序列中的一个数字时，它已经被计算出来了。 换句话说，LL版本并非严格的JIT懒序列生成，只有列表管理。

---

你一定要退房

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

但我会稍后尝试发布更全面的答案。

UPDATE

好的，下面有一个解决方案。 它将Morris序列表示为int的LazyLists的LazyList，因为我认为你希望它在两个方向都是懒惰的。

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()    

内存使用率保持不变（在我的盒子下16M）...还没有完成运行，但我计算了第55长度快，即使在我的慢箱子，所以我认为这应该工作得很好。 请注意，我使用'bignum'的长度，因为我认为这会溢出'int'。

---

我相信这里有两个主要问题：

懒惰是非常低效的，所以你可以期望一个懒惰的函数实现运行速度慢几个数量级。 例如，这里描述的Haskell实现比我在下面给出的F＃慢了2400倍。 如果你想要一个解决方法，你最好的办法可能是通过将计算结果聚合成批量按需生产的批量批次来分摊计算。

Seq.append函数实际上是从IEnumerable调用到C＃代码中的，因此它的尾部调用并没有被消除，并且每次通过时都会泄漏更多的堆栈空间。 当你列举整个序列时，就会显示出来。

在计算第50个子序列的长度时，以下内容比您的实现快80倍以上，但对您而言可能并不够懒：

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的折叠，如果你使用一个struct作为累加器， 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)
}

链接地址: http://www.djcxy.com/p/80571.html

上一篇: Avoiding stack overflow (with F# infinite sequences of sequences)

下一篇: How to make FsLex rules tail