On Sun, 16 Sep 2012 18:13:36 +0200, Alexander Blinne wrote: > I did some timing with the following versions of the function: > > def powerlist1(x, n): > result=[1] > for i in xrange(n-1): > result.append(result[-1]*x) > return result > > def powerlist2(x,n): > if n==1: > return [1] > p = powerlist3(x,n-1) > p.append(p[-1]*x) > return p
Is that a typo? I think you mean to make a recursive call to powerlist2, not a non-recursive call to powerlist3. > def powerlist3(x,n): > return [x**i for i in xrange(n)] > > with Python 2.7 you are quite right, i used x=4. Below n=26 powerlist3 > is the fastest version, for n>26 powerlist1 is faster, powerlist2 is > always slower than both. Making powerlist2 recursive, the results I get with Python 2.7 are: py> from timeit import Timer as T py> x = 2.357 py> n = 8 py> t1 = T('powerlist1(x, n)', ... setup='from __main__ import powerlist1, x, n') py> t2 = T('powerlist2(x, n)', ... setup='from __main__ import powerlist2, x, n') py> t3 = T('powerlist3(x, n)', ... setup='from __main__ import powerlist3, x, n') py> min(t1.repeat(number=100000, repeat=5)) 0.38042593002319336 py> min(t2.repeat(number=100000, repeat=5)) 0.5992050170898438 py> min(t3.repeat(number=100000, repeat=5)) 0.334306001663208 So powerlist2 is half as fast as the other two, which are very close. For large n, #1 and #3 are still neck-and-neck: py> n = 100 py> min(t1.repeat(number=100000, repeat=5)) 3.6276791095733643 py> min(t3.repeat(number=100000, repeat=5)) 3.58870792388916 which is what I would expect: the overhead of calling Python code will be greater than the speed up from avoiding float multiplications. But long integer unlimited-precision multiplications are slow. To really see the advantage of avoiding multiplications using Horner's Method (powerlist1), we need to use large integers and not floats. py> x = 12345678*10000 py> n = 3 py> min(t1.repeat(number=100000, repeat=5)) 0.2199108600616455 py> min(t3.repeat(number=100000, repeat=5)) 0.551645040512085 As n becomes bigger, the advantage also increases: py> n = 10 py> min(t1.repeat(number=100000, repeat=5)) 0.736515998840332 py> min(t3.repeat(number=100000, repeat=5)) 2.4837491512298584 In this case with n = 10, powerlist1 does 9 multiplications. But powerlist3 makes ten calls to the ** operator. The number of multiplications will depend on how cleverly exponentiation is implemented: at worst, using a naive algorithm, there will be 36 multiplications. If the algorithm is a bit smarter, there will be 19 multiplications. Either way, when the calculation is dominated by the cost of multiplication, powerlist3 is between two and four times as expensive as powerlist1. -- Steven -- http://mail.python.org/mailman/listinfo/python-list