Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Hans Boehm's binary trees benchmark in F#
[<CompilationRepresentation(CompilationRepresentationFlags.UseNullAsTrueValue)>]
type Tree = Empty | Node of Tree * Tree
let rec make depth =
if depth=0 then Empty else Node(make (depth-1), make (depth-1))
let rec check = function
| Empty -> 1
| Node(l, r) -> 1 + check l + check r
let test maxDepth =
let minDepth = 4
let maxDepth = max (minDepth+2) maxDepth
let stretchDepth = maxDepth + 1
let stretchTree = System.Threading.Tasks.Task.Run(fun () ->
let check = make stretchDepth |> check |> string
"stretch tree of depth "+string stretchDepth+"\t check: "+check )
let longLivedTree =
let tree = make maxDepth
let check = check tree |> string
"long lived tree of depth "+string maxDepth+"\t check: "+check, tree
let loopTrees = Array.init ((maxDepth-minDepth)/2+1) (fun d ->
let d = minDepth+d*2
let n = 1 <<< (maxDepth - d + minDepth)
let c =
let mutable c = 0
for _ in 1..n do
c <- c + check(make d)
c
string n+"\t trees of depth "+string d+"\t check: "+string c )
stretchTree.Result |> stdout.WriteLine
loopTrees |> Array.iter stdout.WriteLine
fst longLivedTree |> stdout.WriteLine
do
for maxDepth in 12..16 do
let timer = System.Diagnostics.Stopwatch.StartNew()
test maxDepth
printfn "%fs" timer.Elapsed.TotalSeconds
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.