Python presentations

[Steven D'Aprano]

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