问题 F＃尾调用优化2次递归调用？

当我写这个函数时，我知道我不会得到尾调优化。我仍然没有想出一个处理这个的好方法，并希望其他人可以提供建议。

我有一棵树：

type Heap<'a> =
| E
| T of int * 'a * Heap<'a> * Heap<'a>

我想计算其中有多少个节点：

let count h =
    let rec count' h acc =
        match h with 
        | E -> 0 + acc
        | T(_, value, leftChild, rightChild) ->
            let acc = 1 + acc
            (count' leftChild acc) + (count' rightChild acc)

    count' h 0

由于添加了子节点的计数，因此未进行优化。如果树有100万个节点，任何想法如何做这样的工作？

谢谢，德里克

这是使用CPS计数的实现。它仍然吹响了堆栈。

let count h =
    let rec count' h acc cont =
        match h with
        | E -> cont (1 + acc)
        | T(_,_,left,right) ->
            let f = (fun lc -> count' right lc cont)
            count' left acc f

    count' h 0 (fun (x: int) -> x)

也许我可以想出一些方法将树分割成足够的碎片，我可以算不上堆栈？

有人询问生成树的代码。它在下面。

member this.ParallelHeaps threads =
    let rand = new Random()
    let maxVal = 1000000

    let rec heaper i h =
        if i < 1 then
            h
        else
            let heap = LeftistHeap.insert (rand.Next(100,2 * maxVal)) h
            heaper (i - 1) heap

    let heaps = Array.create threads E
    printfn "Creating heap of %d elements, with %d threads" maxVal threads
    let startTime = DateTime.Now
    seq { for i in 0 .. (threads - 1) ->
          async { Array.set heaps i (heaper (maxVal / threads) E) }}
    |> Async.Parallel
    |> Async.RunSynchronously 
    |> ignore

    printfn "Creating %d sub-heaps took %f milliseconds" threads (DateTime.Now - startTime).TotalMilliseconds
    let startTime = DateTime.Now

    Array.length heaps |> should_ equal threads <| "The size of the heaps array should match the number of threads to process the heaps"

    let rec reMerge i h =
        match i with 
        | -1 -> h
        | _  -> 
            printfn "heap[%d].count = %d" i (LeftistHeap.count heaps.[i])
            LeftistHeap.merge heaps.[i] (reMerge (i-1) h)

    let heap = reMerge (threads-1) E
    printfn "Merging %d heaps took %f milliseconds" threads (DateTime.Now - startTime).TotalMilliseconds
    printfn "heap min: %d" (LeftistHeap.findMin heap)

    LeftistHeap.count heap |> should_ equal maxVal <| "The count of the reMerged heap should equal maxVal"

10076

2018-06-11 18:28

起源

答案:

您可以使用延续传递样式（CPS）来解决该问题。看到递归递归 - 继续传递作者：Matthew Podwysocki。

let tree_size_cont tree = 
  let rec size_acc tree acc cont = 
    match tree with 
    | Leaf _ -> cont (1 + acc) 
    | Node(_, left, right) -> 
         size_acc left acc (fun left_size -> 
         size_acc right left_size cont) 

  size_acc tree 0 (fun x -> x)

另请注意，在Debug构建中，禁用尾调用优化。如果您不想在发布模式下运行，可以在Visual Studio的项目属性中启用优化。

2018-06-11 19:20

在内存最终用完之前，延续函数不会增长吗？ - Ramon Snir

通常，是的，但这被认为是好的。但是，对于大多数语言，堆栈具有静态大小（在加载或编译时设置），据我所知，包括F＃，因此它会比使用CPS创建内存不足情况更快地创建堆栈溢出。一般来说，许多计算问题需要无限制的任意输入数据结构，无论你是通过显式数据结构还是“隐式”结构，如不断增长的延续都是随意的：数据需要到达某个地方。 - harms

我曾经想过要尝试这样做，但是我自己说出来因为我认为它仍然会破坏堆栈。在Joh建议之后我试了一下，希望我错了。但不，计数功能仍会打击堆栈。这是我的实施......我不能在这里做，我试着用另一个答案。你如何将代码发布到回复中？ - Derek Ealy

`让count h = let rec count'h acc cont =将h与|匹配E - > cont（1 + acc）| T（，，left，right） - >让f =（fun lc - > count'right lc cont）count'left acc f count'h 0（fun（x：int） - > x）` - Derek Ealy

有人指出，如果代码是在调试模式下构建的，则会禁用尾调优化。一旦我在发布模式下重建，我就可以计算出一个拥有100万个节点的树，很甜蜜！谢谢你指出@kvb。 - Derek Ealy

答案:

您可以使用延续传递样式（CPS）来解决该问题。看到递归递归 - 继续传递作者：Matthew Podwysocki。

let tree_size_cont tree = 
  let rec size_acc tree acc cont = 
    match tree with 
    | Leaf _ -> cont (1 + acc) 
    | Node(_, left, right) -> 
         size_acc left acc (fun left_size -> 
         size_acc right left_size cont) 

  size_acc tree 0 (fun x -> x)

另请注意，在Debug构建中，禁用尾调用优化。如果您不想在发布模式下运行，可以在Visual Studio的项目属性中启用优化。

2018-06-11 19:20

在内存最终用完之前，延续函数不会增长吗？ - Ramon Snir

CPS是一个很好的通用解决方案，但您可能还想考虑显式使用堆栈，因为它会更快并且可以说更简单：

let count heap =
  let stack = System.Collections.Generic.Stack[heap]
  let mutable n = 0
  while stack.Count > 0 do
    match stack.Pop() with
    | E -> ()
    | T(_, _, heap1, heap2) ->
        n <- n + 1
        stack.Push heap1
        stack.Push heap2
  n

2018-06-18 19:49

是什么 Stack[heap] 意思？ - Joh

构建一个 Stack 来自给定序列的集合，包含单个元素的列表（值 heap）。 - Jon Harrop

问题 F＃尾调用优化2次递归调用？

答案:

答案:

热门问题