1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
-- The Computer Language Benchmarks Game
-- http://benchmarksgame.alioth.debian.org/
-- contributed by Mike Pall
local function BottomUpTree(item, depth)
if depth > 0 then
local i = item + item
depth = depth - 1
local left, right = BottomUpTree(i-1, depth), BottomUpTree(i, depth)
return { item, left, right }
else
return { item }
end
end
local function ItemCheck(tree)
if tree[2] then
return tree[1] + ItemCheck(tree[2]) - ItemCheck(tree[3])
else
return tree[1]
end
end
local N = tonumber(arg and arg[1]) or 4
if N == 0 then
N = 0
elseif N == 1 then
N = 9.5
elseif N == 2 then
N = 11.99
elseif N == 3 then
N = 12.85
elseif N == 4 then
N = 14.72
elseif N == 5 then
N = 15.82
end
local mindepth = 4
local maxdepth = mindepth + 2
if maxdepth < N then maxdepth = N end
do
local stretchdepth = maxdepth + 1
local stretchtree = BottomUpTree(0, stretchdepth)
io.write(string.format("stretch tree of depth %d\t check: %d\n",
stretchdepth, ItemCheck(stretchtree)))
end
local longlivedtree = BottomUpTree(0, maxdepth)
for depth=mindepth,maxdepth,2 do
local iterations = 2 ^ (maxdepth - depth + mindepth)
local check = 0
for i=1,iterations do
check = check + ItemCheck(BottomUpTree(1, depth)) +
ItemCheck(BottomUpTree(-1, depth))
end
io.write(string.format("%d\t trees of depth %d\t check: %d\n",
iterations*2, depth, check))
end
io.write(string.format("long lived tree of depth %d\t check: %d\n",
maxdepth, ItemCheck(longlivedtree)))
|
