Re: Help- Recursion v. Iter Speed comparison

From: actuary77 (actuary77_at_elemental-systems.com)
Date: 03/02/05 

Date: Wed, 02 Mar 2005 02:58:15 -0600
To: Robert Kern <rkern@ucsd.edu>

Robert Kern wrote:
> actuary77 wrote:
>
>> Recurse from 9999 time: 4.3059999942779541 seconds
>>
>> Iter from 9999 time: 0.0099999904632568359 seconds
>>
>> No comparison, why is recursion so slow?
>
>
> I usually don't delve too deeply into language design issues, so I hope
> others will correct me if I'm wrong. Recursion is usually slower than
> the equivalent iteration unless if it is specifically optimized by the
> language implementation. Most Schemes, for example, do tail-call
> optimization, and so many uses of recursion run pretty fast. CPython is
> not one of those implementations.
>
>> Would using a generator be faster than recursion?
>
>
> Try it.
>
>> I really have complex list comprehension.
>
>
> Then you shouldn't be using list comprehensions.
>
>> I am interating n times.
>> I have initial function: func(x)
>> I have initial seed value: _aseed
>>
>>
>> iteration value
>> 1 func(_aseed)
>> 2 func(func(_aseed))
>> ....
>> n func(func(func...........(_aseed))
>>
>>
>> What would be the fastest way to do this?
>
>
> Non-generator:
> def f1(aseed):
> values = [func(aseed)]
> for i in range(n-1):
> values.append(func(values[-1]))
> return values
>
> Generator:
> def f2(aseed):
> value = func(aseed)
> for i in range(n):
> yield value
> value = func(aseed)
>
> Probably not *the* fastest solutions, but I'll wager that the speed
> gains you get from a faster solution will be more than paid for by a
> loss in clarity.
>
> Do the simplest thing that could possibly work. Don't bother with
> trickier/less Pythonic approaches until they're really called for.
>
I have a question on the generator solution. I have reviewed docs and I
am unable to return a value from the generator. Below is a little speed
comparison for a:
   1. A recursive solution
   2. A non-generator, list comprehension approach (Thank you)
   3. The generator.

Do you have any suggestions:

''' A comparison of Recursion, list comprehension and a generator '''

import sys
from time import time
sys.setrecursionlimit(10000)

cnt=10000 # number of times to run each test

# The parameters
seed=10
n=100
def myfunc(x):
     return x + .00005

#================================================
# A Recursive Approach
#================================================

def rec(afunc,x,n):
     y = afunc(x)
     if n == 0:
         return y
     else:
         return rec(afunc,y,n-1)

_b=time()
for _i in range(0,cnt):
     _y = rec(myfunc,seed,n)

_e=time()
_t=_e-_b
print "rec result: %r time: %f\n" % (_y,_t*10000.)

#================================================
# non-generator
#================================================

def f1(afunc,aseed,n):
     values = [afunc(aseed)]
     for i in range(n-1):
         values.append(afunc(values[-1]))
     return values[-1]

_b=time()
for _i in range(0,100):
     _y = f1(myfunc,seed,n)
_e=time()
_t=_e-_b

print "f1 result: %r time: %f\n" % (_y,_t*10000.)

#================================================
# generator
#================================================

def f2(afunc,aseed,n):
     v = myfunc(aseed)
     print v
     for i in range(n):
         yield v
         v = afunc(v)

def f2gen(i):
     for _i in range(1,n-1):
         f2(myfunc,seed,n)
     return f2(myfunc,seed,n)

_b=time()
for _i in range(0,cnt):
     _y = f2gen(_i)
_e=time()
_t=_e-_b
print "f2gen result: %r time: %f\n" % (_y,_t*10000.)

==>

rec result: 10.005049999999988 time: 47669.999599

f1 result: 10.004999999999988 time: 399.999619

f2gen result: <generator object at 0x008D74E0> time: 30739.998817

I don't know how to get the generator to work correcly, I understand
that the yield preserves the state of the funcion every time it is
called. So in order to have myfunc called 50 times, the generator must
be called 50 times, but it refuses to return a value. PEP 255 isn't
helping me.

Any further guidance would be greatly appreciated.

Relevant Pages

  • DOM question
    ... recursion is used for DOM traversals. ... So I tried it without using a generator: ... def content_elements: ...
    (comp.lang.python)
  • RE: bad generator performance
    ... Aside from the recursion question... ... To make it work I had to build a data tree - I used the files and ... the generator version takes about 1/4 of the time that the ... for iterator in: ...
    (comp.lang.python)
  • Re: bad generator performance
    ... I would assume the recursion is ... good idea to represent the bookmarks as a tree (with folders as internal ... the generator version takes about 1/4 of the time that the ...
    (comp.lang.python)
  • Re: What is the "functional" way of doing this?
    ... grand conclusions about the general speed of recursion etc. in Python from ... As soon as the size of the list increases the generator function ... Not especially surprising. ... naturally more expensive than a single function call. ...
    (comp.lang.python)
  • RE: Simple Recursive Generator Question
    ... but one of the things you're missing is ... The generator saves you having to pass the "index" param recursively. ... > Changing yield to print, shows that the recursion works correctly. ...
    (comp.lang.python)