The Q6600
Benchmarks Game

binary-trees Python 3 #2 program

source code

# The Computer Language Benchmarks Game
# https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
#
# contributed by Antoine Pitrou
# modified by Dominique Wahli
# modified by Heinrich Acker
# 2to3
# *reset*

import sys

def make_tree(depth):
    if not depth: return None, None
    depth -= 1
    return make_tree(depth), make_tree(depth)

def check_tree(node):
    (left, right) = node
    if not left: return 1
    return 1 + check_tree(left) + check_tree(right)

min_depth = 4
max_depth = max(min_depth + 2, int(sys.argv[1]))
stretch_depth = max_depth + 1

print("stretch tree of depth %d\t check:" % 
    stretch_depth, check_tree(make_tree(stretch_depth)))

long_lived_tree = make_tree(max_depth)

iterations = 2**max_depth

for depth in range(min_depth, stretch_depth, 2):

    check = 0
    for i in range(1, iterations + 1):
        check += check_tree(make_tree(depth))

    print("%d\t trees of depth %d\t check:" % (iterations, depth), check)
    iterations //= 4

print("long lived tree of depth %d\t check:" % 
    max_depth, check_tree(long_lived_tree))

    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
Python 3.8.0


Mon, 11 May 2020 00:26:34 GMT

MAKE:
mv binarytrees.python3-2.python3 binarytrees.python3-2.py
mypy .
There are no .py[i] files in directory '.'
make: [/home/dunham/8000-benchmarksgame/nanobench/makefiles/u64q.programs.Makefile:352: binarytrees.python3-2.python3_run] Error 2 (ignored)

3.78s to complete and log all make actions

COMMAND LINE:
/opt/src/Python-3.8.0/bin/python3 -OO binarytrees.python3-2.py 21

PROGRAM OUTPUT:
stretch tree of depth 22	 check: 8388607
2097152	 trees of depth 4	 check: 65011712
524288	 trees of depth 6	 check: 66584576
131072	 trees of depth 8	 check: 66977792
32768	 trees of depth 10	 check: 67076096
8192	 trees of depth 12	 check: 67100672
2048	 trees of depth 14	 check: 67106816
512	 trees of depth 16	 check: 67108352
128	 trees of depth 18	 check: 67108736
32	 trees of depth 20	 check: 67108832
long lived tree of depth 21	 check: 4194303