performance of recursive generator

aurora aurora00 at gmail.com
Thu Aug 11 23:44:08 CEST 2005


> You seem to be assuming that a yield statement and a function call are  
> equivalent.  I'm not sure that's a valid assumption.

I don't know. I was hoping the compiler can optimize away the chain of  
yields.

> Anyway, here's some data to consider:
>
> -------------------- test.py --------------------
> def gen(n):
>      if n:
>          for i in gen(n/2):
>              yield i
>          yield n
>          for i in gen(n/2):
>          	yield i
>
> def gen_wrapper(n):
>      return list(gen(n))
>
> def nongen(n, func):
> 	if n:
> 	    nongen(n/2, func)
> 	    func(n)
> 	    nongen(n/2, func)
>
> def nongen_wrapper(n):
> 	result = []
> 	nongen(n, result.append)
> 	return result
> -------------------------------------------------

This test somehow water down the n^2 issue. The problem is in the depth of  
recursion, in this case it is only log(n). It is probably more interesting  
to test:

def gen(n):
      if n:
          yield n
          for i in gen(n-1):
              yield i



More information about the Python-list mailing list