Python presentations
Steven D'Aprano
steve+comp.lang.python at pearwood.info
Sun Sep 16 13:35:47 EDT 2012
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
More information about the Python-list
mailing list