Velocity Reviews > Python presentations

# Python presentations

88888 Dihedral
Guest
Posts: n/a

 09-14-2012
Chris Angelico於 2012年9月14日星期五UTC+8上午6時39分25秒 寫道：
> On Fri, Sep 14, 2012 at 8:33 AM, Alexander Blinne <(E-Mail Removed)> wrote:
>
> > On 13.09.2012 21:01, 88888 Dihedral wrote:

>
> >> def powerlist(x, n):

>
> >> # n is a natural number

>
> >> result=[]

>
> >> y=1

>
> >> for i in xrange(n):

>
> >> result.append(y)

>
> >> y*=x

>
> >> return result # any object in the local function can be returned

>
> >

>
> > def powerlist(x, n):

>
> > result=[1]

>
> > for i in xrange(n-1):

>
> > result.append(result[-1]*x)

>
> > return result

>
> >

>
> > def powerlist(x,n):

>
> > if n==1:

>
> > return [1]

>
> > p = powerlist(x,n-1)

>
> > return p + [p[-1]*x]

>
>
>
> Eh, much simpler.
>
>
>
> def powerlist(x,n):
>
> return [x*i for i in xrange(n-1)]
>
>
>
> But you're responding to a bot there. Rather clever as bots go, though.
>
>
>
> ChrisA

I do not object the list comprehension in concept.
But I have to convert python code to cython from time to time.

Well, this imposes some coding style definitely.

Alexander Blinne
Guest
Posts: n/a

 09-14-2012
On 14.09.2012 00:38, Chris Angelico wrote:
> On Fri, Sep 14, 2012 at 8:33 AM, Alexander Blinne <(E-Mail Removed)> wrote:
>> def powerlist(x,n):
>> if n==1:
>> return [1]
>> p = powerlist(x,n-1)
>> return p + [p[-1]*x]

>
> Eh, much simpler.
>
> def powerlist(x,n):
> return [x*i for i in xrange(n-1)]

I suppose you meant:

def powerlist(x,n):
return [x**i for i in xrange(n-1)]

But this is less efficient, because it needs more multiplications (see
Horner's method)

Chris Angelico
Guest
Posts: n/a

 09-14-2012
On Fri, Sep 14, 2012 at 9:47 PM, Alexander Blinne <(E-Mail Removed)> wrote:
> On 14.09.2012 00:38, Chris Angelico wrote:
>> On Fri, Sep 14, 2012 at 8:33 AM, Alexander Blinne <(E-Mail Removed)> wrote:
>>> def powerlist(x,n):
>>> if n==1:
>>> return [1]
>>> p = powerlist(x,n-1)
>>> return p + [p[-1]*x]

>>
>> Eh, much simpler.
>>
>> def powerlist(x,n):
>> return [x*i for i in xrange(n-1)]

>
> I suppose you meant:
>
> def powerlist(x,n):
> return [x**i for i in xrange(n-1)]
>
> But this is less efficient, because it needs more multiplications (see
> Horner's method)

Err, yes, I did mean ** there. The extra multiplications may be
slower, but which is worse? Lots of list additions, or lots of integer
powers? In the absence of clear and compelling evidence, I'd be
inclined to go with the list comp - and what's more, to skip this
function altogether and use the list comp directly where it's needed.

ChrisA

Alexander Blinne
Guest
Posts: n/a

 09-16-2012
On 14.09.2012 14:19, Chris Angelico wrote:
> Err, yes, I did mean ** there. The extra multiplications may be
> slower, but which is worse? Lots of list additions, or lots of integer
> powers? In the absence of clear and compelling evidence, I'd be
> inclined to go with the list comp - and what's more, to skip this
> function altogether and use the list comp directly where it's needed.

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

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.

With Pypy there is a completely different picture, with n<30 powerlist2
is way faster then the other two, but then powerlist1 is again faster
for greater n, somehow because now C long int cannot be used any longer.

for really big n powerlist3 always takes very much time

Alex

Chris Angelico
Guest
Posts: n/a

 09-16-2012
On Mon, Sep 17, 2012 at 2:13 AM, Alexander Blinne <(E-Mail Removed)> wrote:
> def powerlist3(x,n):
> return [x**i for i in xrange(n)]
>
> for really big n powerlist3 always takes very much time

I would reiterate that a really big n is a really unusual use case for
a function like this, except that... I frankly can't think of *any*
use case for it!! But for many many applications, the simplicity and
readability of a list comp instead of a function is usually going to
outweigh the performance differences.

However, it doesn't surprise me that individually raising a number to
successive powers is slower than iterative multiplication, assuming
you can't massively optimize eg with powers of 2 and bit shifts.

ChrisA

Steven D'Aprano
Guest
Posts: n/a

 09-16-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

Alexander Blinne
Guest
Posts: n/a

 09-17-2012
On 16.09.2012 19:35, Steven D'Aprano wrote:
> On Sun, 16 Sep 2012 18:13:36 +0200, Alexander Blinne wrote:
>> 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.

Yes, it is a typo. I originally tested 2 more versions, but tried to
change the numbering before posting. Bad idea