The Computer Language
22.05 Benchmarks Game

binary-trees Python 3 #4 program

source code

# The Computer Language Benchmarks Game
# https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
#
# contributed by Antoine Pitrou
# modified by Dominique Wahli and Daniel Nanz
# modified by Joerg Baumann
# modified by Jonathan Ultis

import sys
import multiprocessing as mp

def make_tree(dd):
    if dd > 0:
        return (make_tree(dd-1), make_tree(dd-1))
    return (None, None)

def check_tree(node):
    l, r = node
    if l is None:
        return 1
    else:
        return 1 + check_tree(l) + check_tree(r)

def make_check(dd, make=make_tree, check=check_tree):
    return check(make(dd))

def main(n, min_depth=4):

    max_depth = max(min_depth + 2, n)
    stretch_depth = max_depth + 1

    if mp.cpu_count() > 1:
        pool = mp.Pool()
        chunkmap = pool.map
    else:
        chunkmap = map

    print('stretch tree of depth {0}\t check: {1}'.format(
          stretch_depth, make_check(stretch_depth)))

    long_lived_tree = make_tree(max_depth)

    mmd = max_depth + min_depth
    for dd in range(min_depth, stretch_depth, 2):
        ii = 2 ** (mmd - dd)
        cs = sum(chunkmap(make_check, (dd,)*ii))
        print('{0}\t trees of depth {1}\t check: {2}'.format(ii, dd, cs))

    print('long lived tree of depth {0}\t check: {1}'.format(
          max_depth, check_tree(long_lived_tree)))


if __name__ == '__main__':
    main(int(sys.argv[1]))
 


    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
Python 3.10.4


Sun, 08 May 2022 21:56:48 GMT

MAKE:
mv binarytrees.python3-4.python3 binarytrees.python3-4.py
pytype .
Traceback (most recent call last):
  File "/home/dunham/.local/bin/pytype", line 5, in <module>
    from pytype.tools.analyze_project.main import main
ModuleNotFoundError: No module named 'pytype'
make: [/home/dunham/all-benchmarksgame/2000-benchmarksgame/nanobench/makefiles/u64q.programs.Makefile:387: binarytrees.python3-4.python3_run] Error 1 (ignored)

1.40s to complete and log all make actions

COMMAND LINE:
/opt/src/Python-3.10.4/bin/python3 -OO binarytrees.python3-4.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