Some Java/C# design flaws

[Justin Johansson]

bearophile wrote:
> 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

Thanks for the heads up.

It sounds like, at least in this example, that the preorder algorithm be 
re-written in iterative fashion rather than recursive fashion as 
currently is.  I suspect that would bring the generator behaviour back 
to O(n).

Funny about this; virtually every CS101 course covers recursive binary
tree node visitation but rarely is there a mention of the iterative
solution.  The iterative solution is much more tricky but for larger N,
is almost a must for practical situations.

Cheers
Justin