当我编写这个函数时,我知道我不会得到尾部调用优化。我仍然没有想出一个处理这个问题的好方法,希望有人能提供建议。
我有一棵树:
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万个节点,有什么办法可以使这样的东西工作吗?
谢谢,Derek
以下是使用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"
count' h 0 (fun (x: int) -> x)`
- Derek Ealy