Revision 9b51354a3b153a85cbe9c63c8b54573aa3e64353 authored by Tim Besard on 20 July 2023, 13:14:05 UTC, committed by Tim Besard on 20 July 2023, 13:26:20 UTC
1 parent bd8350b
binarytree.jl
# This file is a part of Julia. License is MIT: https://julialang.org/license
module BinaryTreeMutable
# Adopted from
# https://benchmarksgame-team.pages.debian.net/benchmarksgame/description/binarytrees.html#binarytrees
using Base.Threads
using Printf
mutable struct Node
l::Union{Nothing, Node}
r::Union{Nothing, Node}
end
function make(n::Int)
return n === 0 ? Node(nothing, nothing) : Node(make(n-1), make(n-1))
end
function check(node::Node)
return 1 + (node.l === nothing ? 0 : check(node.l) + check(node.r))
end
function binary_trees(io, n::Int)
@printf io "stretch tree of depth %jd\t check: %jd\n" n+1 check(make(n+1))
long_tree = make(n)
minDepth = 4
resultSize = div((n - minDepth), 2) + 1
results = Vector{String}(undef, resultSize)
Threads.@threads for depth in minDepth:2:n
c = 0
niter = 1 << (n - depth + minDepth)
for _ in 1:niter
c += check(make(depth))
end
index = div((depth - minDepth),2) + 1
results[index] = @sprintf "%jd\t trees of depth %jd\t check: %jd\n" niter depth c
end
for i in results
write(io, i)
end
@printf io "long lived tree of depth %jd\t check: %jd\n" n check(long_tree)
end
end #module
using .BinaryTreeMutable
# Memory usage is 466MB
BinaryTreeMutable.binary_trees(devnull, 16)
GC.gc()
Computing file changes ...