bench/yarv/bm_so_binary_trees.rb

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