Some Java/C# design flaws

bearophile bearophileHUGS at lycos.com
Mon Feb 1 08:25:16 PST 2010


Justin Johansson:
> Would you kindly explain what exactly is the "quadratic enumerable
> behaviour" problem.

This is a binary tree preorder scan in Python, it contains "yield" that makes this a generator:

def preorder(root):
    if root is not None:
        yield root
        if root.left is not None:
            for n in preorder(root.left):
                yield n
        if root.right is not None:
            for n in preorder(root.right):
                yield n

Being it a generator you can give the root of the binary tree to it, and then you can iterate on all the nodes like this:
for node in preorder(root):
   do_something(node)

I am not 100% sure, but I think the problem comes from those  for n in preorder(root.left):  that turn a tree scan, that is O(n) in a O(n^2) algorithm.

Some Python people have proposed an improvement to generators that as a side effect can lead to reducing that quadratic behaviour back to linear. The following is not the syntax they have proposed but it's more easy to understand. Instead of:
for n in preorder(root.left):
    yield n
Something that works as:
yield *preorder(root.left)
That is a yield that knows how to deal with more than one item, then the C machinery under Python has a chance to optimize things away. I think Lua doesn't share this Python problem.

Bye,
bearophile



More information about the Digitalmars-d mailing list