Yielding a chain of values
tjreedy at udel.edu
Sat Sep 10 00:01:19 CEST 2005
<aurora00 at gmail.com> wrote in message
news:1126285038.776094.66550 at o13g2000cwo.googlegroups.com...
>>>unless you are going many levels deep
> (and that's usually a design smell of some kind)
> No, its not a bug. its a feature! See the discussion in the recursive
> generator thread below:
> In my opinion, traversing recursive data structure is where generator
> shine best. Alternative implementation using iterator is lot more
> difficult and lot less elegant. Unfortunate the right now recursive
> generator would carry a price tag of O(n^2) to the level of depth.
The problem with asymptotic 'big O' notation is that is leaves out both the
constant multiplier and lesser terms and promotes the misperception that
'lower order' asymtotic behavior is always preferable. But much real
computation is done with small and effectively non-asymptotic values where
the omitted components *are* significant.
In this case, the O(depth^2) cost applies, I believe, to resumptions (and
yields) of suspended generators, which are *much* faster than function
calls, so that the omitted multiplier is relatively small. Given that
there is also at least one function call cost for each tree node, I expect
one would need a somewhat deep (intentionally vague without specific timing
data) and unbalanced tree for the resume price to be worrisome.
In any case, having an easily written and understood version can help in
testing a faster and more complicated version, especially on random,
non-corner case examples.
Terry J. Reedy
More information about the Python-list