| -- The Computer Language Shootout |
| -- http://shootout.alioth.debian.org/ |
| -- contributed by Mike Pall |
| -- modified by Sokolov yura |
| |
| --collectgarbage("setstepmul", 0) -- sometimes it helps much. For this benchmark ~ 10% |
| |
| 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 } -- Faster for LuaJIT: return { item, false } |
| end |
| end |
| |
| local function ItemCheck(tree) |
| if #tree == 3 then -- Faster for LuaJIT: 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 0 |
| 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))) |
| |