Re: Help- Recursion v. Iter Speed comparison

[actuary77]

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.
--
http://mail.python.org/mailman/listinfo/python-list