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