6

Expert F# 3.0一书的第 9 章展示了在遍历二叉树时如何使用连续传递样式来避免堆栈溢出。我编写的树遍历代码几乎与书中的代码相同，但我仍然得到堆栈溢出。我的代码如下：

type 'a Tree =
  | Leaf   of 'a
  | Branch of 'a Tree * 'a Tree

let rec mkLeftLeaningTree n tree =
  if n = 0 then
    tree
  else
    Branch (mkLeftLeaningTree (n - 1) tree, Leaf "right")

let leftLeaningTree1 = Leaf "left"
let leftLeaningTree2 = mkLeftLeaningTree 30000 leftLeaningTree1
let leftLeaningTree3 = mkLeftLeaningTree 30000 leftLeaningTree2
let leftLeaningTree4 = mkLeftLeaningTree 30000 leftLeaningTree3
let leftLeaningTree5 = mkLeftLeaningTree 30000 leftLeaningTree4
let leftLeaningTree6 = mkLeftLeaningTree 30000 leftLeaningTree5

let sizeContAcc tree =
  let rec worker acc tree cont =
    match tree with
      | Leaf _               -> cont (acc + 1)
      | Branch (left, right) -> worker acc left  (fun acc ->
                                worker acc right cont)
  worker 0 tree id

将此加载到 F# 交互式环境中并计算表达式sizeContAcc leftLeaningTree6会使堆栈溢出。为什么是这样？

4

2 回答 2

2

不幸的是，这可能无法帮助您实际解决问题，但也许它提供了一些在哪里查找的指示。首先，代码和设置。我减小了树本身的大小以使其在 Windows 上工作。其余的是 .NET 4.6，64 位，win7，在 VS2015 Update3 中。

type 'a Tree =
    | Leaf   of 'a
    | Branch of 'a Tree * 'a Tree

[<EntryPoint>]
let main argv =

    ///https://stackoverflow.com/questions/40477122/why-does-traversing-a-large-binary-tree-result-in-a-stack-overflow-even-when-usi



    let rec mkLeftLeaningTree n tree =
      if n = 0 then
        tree
      else
        Branch (mkLeftLeaningTree (n - 1) tree, Leaf "right")



    let leftLeaningTree1 = Leaf "left"
    let leftLeaningTree2 = mkLeftLeaningTree 15000 leftLeaningTree1
    let leftLeaningTree3 = mkLeftLeaningTree 15000 leftLeaningTree2
    let leftLeaningTree4 = mkLeftLeaningTree 15000 leftLeaningTree3
    let leftLeaningTree5 = mkLeftLeaningTree 15000 leftLeaningTree4
    let leftLeaningTree6 = mkLeftLeaningTree 15000 leftLeaningTree5
    let leftLeaningTree7 = mkLeftLeaningTree 15000 leftLeaningTree6
    let leftLeaningTree8 = mkLeftLeaningTree 15000 leftLeaningTree7
    let leftLeaningTree9 = mkLeftLeaningTree 15000 leftLeaningTree8
    let leftLeaningTree10 = mkLeftLeaningTree 15000 leftLeaningTree9
    let leftLeaningTree11 = mkLeftLeaningTree 15000 leftLeaningTree10
    let leftLeaningTree12 = mkLeftLeaningTree 15000 leftLeaningTree11
    let leftLeaningTree13 = mkLeftLeaningTree 15000 leftLeaningTree12
    let leftLeaningTree14 = mkLeftLeaningTree 15000 leftLeaningTree13
    let leftLeaningTree15 = mkLeftLeaningTree 15000 leftLeaningTree14
    let leftLeaningTree16 = mkLeftLeaningTree 15000 leftLeaningTree15
    let leftLeaningTree17 = mkLeftLeaningTree 15000 leftLeaningTree16
    let leftLeaningTree18 = mkLeftLeaningTree 15000 leftLeaningTree17
    let leftLeaningTree19 = mkLeftLeaningTree 15000 leftLeaningTree18
    let leftLeaningTree20 = mkLeftLeaningTree 15000 leftLeaningTree19
    let leftLeaningTree21 = mkLeftLeaningTree 15000 leftLeaningTree20
    let leftLeaningTree22 = mkLeftLeaningTree 15000 leftLeaningTree21
    let leftLeaningTree23 = mkLeftLeaningTree 15000 leftLeaningTree22
    let leftLeaningTree24 = mkLeftLeaningTree 15000 leftLeaningTree23
    let leftLeaningTree25 = mkLeftLeaningTree 15000 leftLeaningTree24
    let leftLeaningTree26 = mkLeftLeaningTree 15000 leftLeaningTree25
    let leftLeaningTree27 = mkLeftLeaningTree 15000 leftLeaningTree26
    let leftLeaningTree28 = mkLeftLeaningTree 15000 leftLeaningTree27
    let leftLeaningTree29 = mkLeftLeaningTree 15000 leftLeaningTree28
    let leftLeaningTree30 = mkLeftLeaningTree 15000 leftLeaningTree29
    let leftLeaningTree31 = mkLeftLeaningTree 15000 leftLeaningTree30

    let sizeContAcc tree =
      let rec worker acc tree cont =
        match tree with
          | Leaf _               -> cont (acc + 1)
          | Branch (left, right) -> worker acc left  (fun acc ->
                                    worker acc right cont)
      worker 0 tree id



    sizeContAcc leftLeaningTree31  |> printfn "%A"

    printfn "%A" argv
    0 // return an integer exit code

这是用尾调用编译的，在发布模式下优化：

C:\Program Files (x86)\Microsoft SDKs\F#\4.0\Framework\v4.0\fsc.exe -o:obj\Release\ConsoleApplication8.exe --debug:pdbonly --noframework --define:TRACE -- doc:bin\Release\ConsoleApplication8.XML --optimize+ --platform:x64 -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\FSharp.NETFramework\v4.0\4.4.0.0\FSharp.Core .dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\mscorlib.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft \Framework.NETFramework\v4.6\System.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.dll" -r:"C :\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Numerics.dll" --target:exe --warn:3 --warnaserror:76 --vserrors --LCID:1033 --utf8output --fullpaths --flaterrors --subsystemversion:6.00 --highentropyva+ --sqmsessionguid:057b9ccf-c89e-4da6-81ab-5295156e7a19 "C:\Users\userName\AppData\Local\Temp.NETFramework,Version=v4 .6.AssemblyAttributes.fs" AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> C:\Users\userName\Documents\Visual Studio 2015\Projects\StackOverflow6\ConsoleApplication8\bin\Release\ConsoleApplication8.exe

因此，对于 31 棵树，这是可行的：

 .\ConsoleApplication8.exe
450001

现在让我们在调试模式下编译它：

C:\Program Files (x86)\Microsoft SDKs\F#\4.0\Framework\v4.0\fsc.exe -o:obj\Debug\ConsoleApplication8.exe -g --debug:full --noframework --define:DEBUG --define:TRACE --doc:bin\Debug\ConsoleApplication8.XML --optimize- --tailcalls- --platform:anycpu32bitpreferred -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\FSharp.NETFramework \v4.0\4.4.0.0\FSharp.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\mscorlib.dll" -r:"C :\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4 .6\System.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Numerics.dll" --target:exe --warn:3 --warnaserror:76 --vserrors --LCID:1033 --utf8output --fullpaths --flaterrors --subsystemversion:6.00 --highentropyva+ --sqmsessionguid:057b9ccf-c89e-4da6-81ab-5295156e7a19 "C:\Users\ userName\AppData\Local\Temp.NETFramework,Version=v4.6.AssemblyAttributes.fs" AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> C:\Users\userName\Documents\Visual Studio 2015\Projects\StackOverflow6\ConsoleApplication8\ bin\Debug\ConsoleApplication8.exe\Users\userName\Documents\Visual Studio 2015\Projects\StackOverflow6\ConsoleApplication8\bin\Debug\ConsoleApplication8.exe\Users\userName\Documents\Visual Studio 2015\Projects\StackOverflow6\ConsoleApplication8\bin\Debug\ConsoleApplication8.exe

而且，哎呀：

> .\ConsoleApplication8.exe
Process is terminated due to StackOverflowException.

那么区别是什么呢？

在 Release 版本中有 9 个tail调用，如果你反编译 IL，我假设这由某种 while 循环表示。

IL_0073: ldloc.s 6
IL_0075: tail.
IL_0077: call int32 [FSharp.Core]Microsoft.FSharp.Core.LanguagePrimitives/HashCompare::GenericComparisonWithComparerIntrinsic<!a>(class [mscorlib]System.Collections.IComparer, !!0, !!0)

在 Debug 版本中，这将丢失：

L_007d: ldloc.s 6
IL_007f: call int32 [FSharp.Core]Microsoft.FSharp.Core.LanguagePrimitives/HashCompare::GenericComparisonWithComparerIntrinsic<!a>(class [mscorlib]System.Collections.IComparer, !!0, !!0)
IL_0084: ret

对于一个更简单的测试示例，您可以检查这个问题，因为它同时具有算法的递归和尾递归版本。

于 2016-11-09T00:17:41.440 回答
1

我的第一个猜测是您在 cont 参数中将函数堆叠在一起，我将其理解为可能溢出的堆栈（而 Wolfgang 在评论中解释它是一个堆），但我使用 cont 做了一些测试论点，它没有导致任何堆栈溢出。相反，我的速度明显放缓，最终达到了内存溢出。

解决您的特定问题的方法是将需要探索的树显式存储在列表中（您仍然会受到列表最大大小的限制）：

let sizeContAcc tree =
  let rec worker acc tree contList =
    match tree with
      | Leaf _ -> 
        match contList with
        | [] -> acc+1
        | t::cl -> worker (acc+1) t cl
      | Branch (left, right) -> worker acc left (right::contList)
  worker 0 tree []

它有效，并立即为 leftLeaningTree6 提供了 150001。

于 2016-11-08T10:04:56.493 回答