gpt4 book ai didi

recursion - 使用 2 个递归调用进行 F# 尾调用优化?

转载 作者:行者123 更新时间:2023-12-04 01:57:41 24 4
gpt4 key购买 nike

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

我有一棵树:

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 的 count 实现。尽管如此,它仍然炸毁了堆栈。
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"

最佳答案

您可以使用连续传递样式 (CPS) 来解决该问题。见 Recursing on Recursion - Continuation Passing马修·波德维索基。

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 版本中,尾调用优化被禁用。如果不想在 Release 模式下运行,可以在 Visual Studio 的项目属性中启用优化。

关于recursion - 使用 2 个递归调用进行 F# 尾调用优化?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6317758/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com