1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tests/shootout/binary-trees.py Sat Dec 02 00:23:46 2006 +0100
1.3 @@ -0,0 +1,44 @@
1.4 +# The Computer Language Shootout Benchmarks
1.5 +# http://shootout.alioth.debian.org/
1.6 +#
1.7 +# contributed by Antoine Pitrou
1.8 +# modified by Dominique Wahli
1.9 +
1.10 +from sys import argv
1.11 +
1.12 +def make_tree(item, depth):
1.13 + if depth > 0:
1.14 + item2 = 2 * item
1.15 + depth -= 1
1.16 + return (item, make_tree(item2 - 1, depth), make_tree(item2, depth))
1.17 + else:
1.18 + return (item, None, None)
1.19 +
1.20 +def check_tree((item, left, right)):
1.21 + if left is not None:
1.22 + return item + check_tree(left) - check_tree(right)
1.23 + else:
1.24 + return item
1.25 +
1.26 +def main():
1.27 + min_depth = 4
1.28 + max_depth = max(min_depth + 2, int(argv[1]))
1.29 + stretch_depth = max_depth + 1
1.30 +
1.31 + print "stretch tree of depth %d\t check: %d" % (stretch_depth, check_tree(make_tree(0, stretch_depth)))
1.32 +
1.33 + long_lived_tree = make_tree(0, max_depth)
1.34 +
1.35 + for depth in xrange(min_depth, stretch_depth, 2):
1.36 + iterations = 2**(max_depth - depth + min_depth)
1.37 +
1.38 + check = 0
1.39 + for i in xrange(1, iterations + 1):
1.40 + check += check_tree(make_tree(i, depth)) + check_tree(make_tree(-i, depth))
1.41 +
1.42 + print "%d\t trees of depth %d\t check: %d" % (iterations * 2, depth, check)
1.43 +
1.44 + print "long lived tree of depth %d\t check: %d" % (max_depth, check_tree(long_lived_tree))
1.45 +
1.46 +if __name__ == '__main__':
1.47 + main()