1 # The Computer Language Shootout Benchmarks 2 # http://shootout.alioth.debian.org/ 3 # 4 # contributed by Antoine Pitrou 5 # modified by Dominique Wahli 6 7 #from sys import argv 8 9 def make_tree(item, depth): 10 if depth > 0: 11 item2 = 2 * item 12 depth -= 1 13 return (item, make_tree(item2 - 1, depth), make_tree(item2, depth)) 14 else: 15 return (item, None, None) 16 17 def check_tree(tree): 18 (item, left, right) = tree 19 if left is not None: 20 return item + check_tree(left) - check_tree(right) 21 else: 22 return item 23 24 def main(): 25 min_depth = 4 26 max_depth = max(min_depth + 2, 16) #int(argv[1])) 27 stretch_depth = max_depth + 1 28 29 print "stretch tree of depth %d\t check: %d" % (stretch_depth, check_tree(make_tree(0, stretch_depth))) 30 31 long_lived_tree = make_tree(0, max_depth) 32 33 for depth in xrange(min_depth, stretch_depth, 2): 34 iterations = 2**(max_depth - depth + min_depth) 35 36 check = 0 37 for i in xrange(1, iterations + 1): 38 check += check_tree(make_tree(i, depth)) + check_tree(make_tree(-i, depth)) 39 40 print "%d\t trees of depth %d\t check: %d" % (iterations * 2, depth, check) 41 42 print "long lived tree of depth %d\t check: %d" % (max_depth, check_tree(long_lived_tree)) 43 44 if __name__ == '__main__': 45 main()