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
