代码之家 › 专栏 › 技术社区 › Tony Lee

避免堆栈溢出(使用无限序列)

sequences tail-recursion stack-overflow f#

28

Tony Lee · 技术社区 · 16 年前

我有一个“学习代码”,我在f中为MorrisSeq编写的代码,它遭受了堆栈溢出的困扰,我不知道如何避免。Morris“返回“see and say”序列的无限序列(即,,,,,1,2,1,1,1,1,1,2,2,1,3,1,2,2,1,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次迭代,但您只能在遇到堆栈溢出之前完成。我拥有的一个递归位是尾部递归,它本质上构建了一组链接的枚举器。这不是问题所在。它是在say-the-4000序列上调用“enum”的时候。注意,这是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习语,以便根据内存大小进行限制。

更新OCT’10

在学习了f一点,一点点哈斯克尔,思考和调查这个问题一年多后,我终于可以回答我自己的问题。但和往常一样,困难的问题,首先是错误的问题。问题不在于序列,而是因为一个递归定义的序列。我的功能编程技巧现在有点好了,所以更容易看到下面的版本发生了什么,它仍然会得到stackoverflow

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

这个会得到一个stackoverflow。

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

为了证明F libary是问题所在,我编写了自己的seq模块,该模块使用连续性实现了追加、成对、扫描和收集,现在我可以开始生成和打印50000个seq而无需任何问题(它永远不会完成,因为它的长度超过了10^5697位)。

一些附加说明:

延续是我所寻找的习惯用法,但在本例中,它们必须进入f_库,而不是我的代码。我从 Tomas Petricek's 现实世界函数编程 书。
我接受的懒惰列表答案包含了另一个习语:懒惰评估。在我重写的库中,我还必须利用lazy类型来避免stackoverflow。
惰性列表版本是靠运气工作的(可能是靠设计,但这超出了我目前的判断能力),它在构造和迭代时使用的活动模式匹配会导致列表在所需的递归变得太深之前计算值,所以它很懒惰,但不是很懒惰,它需要继续以避免堆栈溢出。例如,当第二个序列需要第一个序列中的数字时,它已经被计算出来了。换句话说,ll版本并不是严格的jit-lazy序列生成,而是列表管理。

3 回复 | 直到 10 年前

1

12

Brian 16 年前

你一定要去看看

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

但稍后我将尝试发布一个更全面的答案。

更新

好的,下面是一个解决方案。它将莫里斯序列表示为int的lazylist中的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

更新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”。

2

3

J D 16 年前

我认为这里有两个主要问题:

懒惰是非常低效的,因此您可以期望懒惰的函数实现以更慢的速度运行。例如,haskell实现描述了 here 比下面的f慢2400倍。如果你想要一个解决方法,你最好的办法可能是将计算集中在一起,按需生产批次。
这个 Seq.append 函数实际上是从 IEnumerable 因此,它的尾部调用不会被消除,每次通过它时都会泄漏更多的堆栈空间。当您开始枚举序列时,就会出现这种情况。

在计算第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 如果您使用一个结构作为累加器,那么它可以被分解并在功能上使用,而不会造成太大的性能下降。

3

0

Dario 16 年前

只需保存您查找的上一个元素。

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