performance of recursive generator
aurora00 at gmail.com
Thu Aug 11 23:37:36 CEST 2005
On Thu, 11 Aug 2005 01:18:11 -0700, Matt Hammond
<matt.hammond at rd.bbc.co.uk> wrote:
>> Is it an inherent issue in the use of recursive generator? Is there any
>> compiler optimization possible?
> Hi, I could be misunderstanding it myself, but I think the short answer
> to your question is that its an inherent limitation.
> Perhaps if there existed some kind of syntax to hint this to python it
> could optimise it away, eg:
> yield *inorder(t.left)
> ... but AFAIK there isn't :-( so I guess you'll have to avoid recursive
> generators for this app!
That would be unfortunately. I think generator is most elegant in
traversing recursive structure. It is non-trivial to use most other
methods. But the O(n^2) price tag is a big caveat to keep in mind.
Of course I agree we should not optimize prematurely. I'm not about to
rewrite my recursive generators just yet. But O(n^2) complexity is
something important to bear in mind. It doesn't necessary cause problems
in practice. But it might.
More information about the Python-list