simplify

Annotated tests/shootout/binary-trees.py

248:6e7b6fcd6302
200:76b0d12a915c
2007-06-23 paulb file changeset files shortlog Introduced a separate fix_structures method to the instance fixing class. Made new dictionaries when fixing references to instances via accesses/writes. Added recursion detection around getting distinct instances from classes.
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()