FilesExpand file tree

 main

/

binarytrees.lua

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

66 lines (57 loc) · 1.51 KB

 main

/

binarytrees.lua

Top

File metadata and controls

• Code
• Blame

66 lines (57 loc) · 1.51 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

66

-- 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

-- we don't look at commandline arguments anyhow

local N = 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)))