# binary-trees Python 3 #3 program

## source code

```# The Computer Language Benchmarks Game
# https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
#
# contributed by Diogo

from concurrent.futures import ProcessPoolExecutor as PoolExecutor
from multiprocessing import cpu_count
import sys
import gc

def tree_make(n: int) -> list:
""" Creates a tree recursively based on lists of 2 elements

Data:   Lists are core data sets for python so they use less
memory, andalso they provide means for fast iteration

Advice: List creation is expensive, as much as list appending
We can avoid mutating list length, because on low-level
extending a list length will need to discard existing
list and creating a new list with a new length.
But mutating existing list element is not as expensive

Method: Create a list of nones for optimized creation
If we are on bottom level return this list
Else create the child node recursively
Now e overwrite left and right empty nodes with child
"""

# Create base node of empty childs
node = [None, None]

# If we are on bottom, return empty node
if n == 0:
return node

# Populate and return populated node
node[0] = tree_make(n-1)
node[1] = tree_make(n-1)

return node

def tree_check(n: list) -> int:
""" Walkthrough the tree and add 1 for each node found """
# If we are at bottom node, return 1
if n[0] is None:
return 1
# Go through left
left_result = tree_check(n[0])
# Go through right
right_result = tree_check(n[1])
# Append results
result = 1 + left_result + right_result
return result

def tree_make_and_check(n: int, keep_in_memory: bool = False) -> (list, int):
""" Create a tree and check for its value based on nodes """
# Create our tree and get number of nodes
tree: list = tree_make(n)
check: int = tree_check(tree)

# Check if we are returning only the value and discarding tree
# Or if we are keeping tree in memory
# In the case of the long lived tree we are going to keep it in memory
if keep_in_memory:
return (tree, check)
return (None, check)

def data_iter(d: int, n: int):
""" Iterate over tree and check it's content """
niter: int = 1 << (n - d + 4)

# We will have niter results
# Then we can store a list of niter length of 0's
results: list = [0] * niter

# Then as we create trees we mutate the zeros
for index in range(0, niter):
tree: list = tree_make(d)
check: int = tree_check(tree)
results[index] = check

# At the end we sum all results to get final return
c: int = sum(results)

return niter, d, c

def binary_trees_run(n: int, workers: int):
""" Run binary trees benchmark """

# Disable garbage collection for less overhead
gc.disable()

# Create an executor and a dict to track futures
result: dict = {}
executor = PoolExecutor(max_workers=workers)

# Create stretch tree with the pool and verify its check value
# This first tree we are going to create and discard tree
# result['stretch'] = executor.submit(tree_make_and_check, n + 1, False)
stretch_tree = tree_make_and_check(n + 1, False)

# Create long lived tree with the pool and verify its check value
# This long lived tree will be kept in memory until the end
# result['longlived'] = executor.submit(tree_make_and_check, n, True)
longlived = tree_make_and_check(n, True)

# Loop through tree to make iterations as soon as they arrive
# Trees are stored as {id}

# Getting list of depths and storing tuples of (depth, id)
depth_list: list = list(range(4, n, 2) if n % 2 != 0 else range(4, n+1, 2))
id_list: list = list(range(0, len(depth_list)))
iter_list: list = list(zip(depth_list, id_list))

# iter_batch will be a tuple of (depth, id)
# Lets submit workers
for work in iter_list:
item = work[1]
d = work[0]
result[item] = executor.submit(data_iter, d, n)

# Time to get results from those futures
# Print stretch tree result as we get it and discard the tree from memory
# stretch_check_val: int = result['stretch'].result()[1]
# print(f"stretch tree of depth {n+1}\t check: {stretch_check_val}")
# del result['stretch']
print(f"stretch tree of depth {n+1}\t check: {stretch_tree[1]}")

# Loop through iterations and get results in order for correct output
# Once we get the tree for the moment, discard the tree from memory
for value in id_list:
niter, d, c = result[value].result()
print(f"{niter}\t trees of depth {d}\t check: {c}")
del result[value]

# Now we can print long lived tree and discard the tree
# longlived_check_val: int = result['longlived'].result()[1]
# print(f"long lived tree of depth {n}\t check: {longlived_check_val}")
# del result['longlived']
print(f"long lived tree of depth {n}\t check: {longlived[1]}")
del longlived

if __name__ == "__main__":

# Get how many cores available
logicalcpu_cores: int = cpu_count()
workers: int = 2
if logicalcpu_cores > 2:
workers = logicalcpu_cores

n: int = int(sys.argv[1])
binary_trees_run(n, workers)
```

## notes, command-line, and program output

```NOTES:
Python 3.12.3

Mon, 27 May 2024 21:45:06 GMT

MAKE:
mv binarytrees.python3-3.python3 binarytrees.python3-3.py
pyright .
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/binarytrees.python3-3.py
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/binarytrees.python3-3.py:39:5 - error: No overloads for "__setitem__" match the provided arguments (reportCallIssue)
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/binarytrees.python3-3.py:39:5 - error: Argument of type "list[Unknown]" cannot be assigned to parameter "value" of type "None" in function "__setitem__"
"list[Unknown]" is incompatible with "None" (reportArgumentType)
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/binarytrees.python3-3.py:40:5 - error: No overloads for "__setitem__" match the provided arguments (reportCallIssue)
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/binarytrees.python3-3.py:40:5 - error: Argument of type "list[Unknown]" cannot be assigned to parameter "value" of type "None" in function "__setitem__"
"list[Unknown]" is incompatible with "None" (reportArgumentType)
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/binarytrees/tmp/binarytrees.python3-3.py:59:66 - error: Tuple expression not allowed in type annotation
Use tuple[T1, ..., Tn] to indicate a tuple type or Union[T1, T2] to indicate a union type (reportInvalidTypeForm)
5 errors, 0 warnings, 0 informations
make: [/home/dunham/all-benchmarksgame/2000-benchmarksgame/nanobench/makefiles/u64q.programs.Makefile:421: binarytrees.python3-3.python3_run] Error 1 (ignored)

4.57s to complete and log all make actions

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