1# The Computer Language Shootout Benchmarks 2# http://shootout.alioth.debian.org 3# 4# contributed by Jesse Millikan 5 6# disable output 7alias puts_orig puts 8def puts str 9 # disable puts 10end 11 12def item_check(tree) 13 if tree[0] == nil 14 tree[1] 15 else 16 tree[1] + item_check(tree[0]) - item_check(tree[2]) 17 end 18end 19 20def bottom_up_tree(item, depth) 21 if depth > 0 22 item_item = 2 * item 23 depth -= 1 24 [bottom_up_tree(item_item - 1, depth), item, bottom_up_tree(item_item, depth)] 25 else 26 [nil, item, nil] 27 end 28end 29 30max_depth = 16 # ARGV[0].to_i 31min_depth = 4 32 33max_depth = min_depth + 2 if min_depth + 2 > max_depth 34 35stretch_depth = max_depth + 1 36stretch_tree = bottom_up_tree(0, stretch_depth) 37 38puts "stretch tree of depth #{stretch_depth}\t check: #{item_check(stretch_tree)}" 39stretch_tree = nil 40 41long_lived_tree = bottom_up_tree(0, max_depth) 42 43min_depth.step(max_depth + 1, 2) do |depth| 44 iterations = 2**(max_depth - depth + min_depth) 45 46 check = 0 47 48 for i in 1..iterations 49 temp_tree = bottom_up_tree(i, depth) 50 check += item_check(temp_tree) 51 52 temp_tree = bottom_up_tree(-i, depth) 53 check += item_check(temp_tree) 54 end 55 56 puts "#{iterations * 2}\t trees of depth #{depth}\t check: #{check}" 57end 58 59puts "long lived tree of depth #{max_depth}\t check: #{item_check(long_lived_tree)}" 60 61undef puts 62alias puts puts_orig 63