2
\$\begingroup\$

I tried to make a dynamic tree in python. It is simple and i have gotten it to work so far. I created a function in main that generates some example data for the tree and then the main goal was to create a member function that uses recursion to print all the data (display_data()). The only issue with this that i have is the recursion depth problem, as well as the speed. Essentially the recursion and loop pattern builds up quite a bit on the overall run time. Also note this is a side project, I need to understand dynamic trees for a tic-tac-toe AI I am attempting(failing) to write.

tree.py

class Tree():
    """Implement a dynamic tree

                   1
                 / | \
                /  |   \
              2    3     4
             / \       / | \
            5   6     7  8  9
           /  / | \
          10 11 12 13
    """

    def __init__(self):
        self.children = []
        self.data = []

    def create_children(self, amount):
        for i in range(amount):
            self.children.append(Tree())

    def create_data(self, data):
        for datum in data:
            self.data.append(datum)

    def display_data(self):
        print(self.data, end = ' ')
        for child in self.children:
            child.display_data()

main.py

from tree import Tree

def example_data(root):
    """
        ['Child', 1] ['nChild', 1] ['nChild', 2]
        ['Child', 2] ['nChild', 1] ['nChild', 2]
        ['Child', 3] ['nChild', 1] ['nChild', 2]

    """
    root.create_data(["Root"])
    root.create_children(3)

    counter = 1
    for child in root.children:
        child.create_data(["Child", counter])
        child.create_children(2)
        counter += 1

        ncounter = 1
        for nchild in child.children:
            nchild.create_data(["nChild", ncounter])
            ncounter += 1

    return root

if __name__ == "__main__":
    root = example_data(Tree())
    root.display_data()
\$\endgroup\$
2
\$\begingroup\$

Specific suggestions:

  1. It is idiomatic to wrap the stuff after if __name__ == "__main__": in a main function.
  2. Rather than the generic data I would suggest figuring out exactly which information you want to attach to each Tree and creating fields for each of them rather than a fully generic list of stuff. This will make it much less painful to work with actual Trees because you can use for example tree.name or tree.counter instead of tree.data[0] and tree.data[1].
  3. You can enumerate a list to loop over it without maintaining a separate index variable, as in for index, child in enumerate(root.children):

In general it'll be much easier to see how to improve this code once it's wired into a production use case rather than example code. The problem with writing code to an example "spec" is that the example inevitably doesn't completely fit the production use case - some crucial features will be missing and others will be superfluous. For example, storing the count of children separately. This information is already encoded in the length of the children list, so you are duplicating the information for no obvious reason. This could conceivably be useful if you're dealing with giant amounts of data, but if your application is sufficiently optimized that this is a real concern you probably should look into other languages or frameworks like numpy or pandas.

General suggestions:

  1. black can automatically format your code to be more idiomatic.
  2. isort can group and sort your imports automatically.
  3. flake8 with a strict complexity limit will give you more hints to write idiomatic Python:

    [flake8]
    max-complexity = 4
    ignore = W503,E203
    

    (The max complexity limit is not absolute by any means, but it's worth thinking hard whether you can keep it low whenever validation fails. For example, I'm working with a team on an application since a year now, and our complexity limit is up to 7 in only one place. Conversely, on an ugly old piece of code I wrote without static analysis support I recently found the complexity reaches 87!)

  4. I would then recommend adding type hints everywhere and validating them using a strict mypy configuration:

    [mypy]
    check_untyped_defs = true
    disallow_untyped_defs = true
    ignore_missing_imports = true
    no_implicit_optional = true
    warn_redundant_casts = true
    warn_return_any = true
    warn_unused_ignores = true
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.