# Re: Why is my code faster with append() in a loop than with a largelist?

Discussion in 'Python' started by Dave Angel, Jul 6, 2009.

1. ### Dave AngelGuest

Xavier Ho wrote:
> (Here's a short version of the long version below if you don't want to
>
> Why is version B of the code faster than version A? (Only three lines
> different)
>
> Version A: http://pastebin.com/f14561243
> Version B: http://pastebin.com/f1f657afc
>
> ------------------------------------------------
>
> I was doing the problems on Project Euler for practice with Python last
> night. Problem 12 was to find the value of the first triangular number that
> has over 500 divisors.
> =========================================================================================
>
> The sequence of triangle numbers is generated by adding the natural numbers.
> So the 7[image: ^(]th[image: )] triangle number would be 1 + 2 + 3 + 4 + 5 +
> 6 + 7 = 28. The first ten terms would be:
>
> 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
>
> Let us list the factors of the first seven triangle numbers:
>
> * 1*: 1
> * 3*: 1,3
> * 6*: 1,2,3,6
> *10*: 1,2,5,10
> *15*: 1,3,5,15
> *21*: 1,3,7,21
> *28*: 1,2,4,7,14,28
>
> We can see that 28 is the first triangle number to have over five divisors.
>
> What is the value of the first triangle number to have over five hundred
> divisors?
> =========================================================================================
>
> My initial code was to loop through from 1 to half the number and see which
> were divisors, and as I find them I store them in a list. That would have
> taken days.
>
> My second try was factorising the number each time, and count the divisors
> using the powers of each factor, plus 1, and multiply together.
> The code is here (Version A): http://pastebin.com/f14561243
>
> This worked, but it took overnight to compute. Before I went to bed a friend
> of mine caught me online, and apparently left me a working version under 8
> seconds with only 3 line difference.
> The code is here (Version B): http://pastebin.com/f1f657afc
>
> That was amazing. But I have no idea why his edit makes it so much faster. I
> did a test to see whether if append() was faster (which I doubted) than
> defining a list with a large size to begin with, and I was right:
> http://pastebin.com/f4b46d0db
> Which shows that appending is 40x slower, and was expected. But I still
> can't puzzle out why his use of appending in Version B was so much faster
> than mine.
>
> Any insights would be welcome. I'm going on a family trip, though, so my
> replies may delay.
>
> Best regards,
>
> Ching-Yun "Xavier" Ho, Technical Artist
>
> Contact Information
> Mobile: (+61) 04 3335 4748
> Skype ID: SpaXe85
> Email:
> Website: http://xavierho.com/
>
>

Just by inspection, it would seem the bottleneck in your first version
is that you return a huge list of nearly all zeroes, from factorize().
This slows down countDivisors() a great deal.

It would probably save some time to not bother storing the zeroes in the
list at all. And it should help if you were to step through a list of
primes, rather than trying every possible int. Or at least constrain
yourself to odd numbers (after the initial case of 2).

DaveA

Dave Angel, Jul 6, 2009

2. ### Piet van OostrumGuest

Re: Why is my code faster with append() in a loop than with a large list?

>>>>> Dave Angel <> (DA) wrote:

>DA> It would probably save some time to not bother storing the zeroes in the
>DA> list at all. And it should help if you were to step through a list of
>DA> primes, rather than trying every possible int. Or at least constrain
>DA> yourself to odd numbers (after the initial case of 2).

The first and the last save a constant factor (slightly less than 2):

def factorise(num):
"""Returns a list of prime factor powers. For example:
factorise(6) will return
[2, 2] (the powers are returned one higher than the actual value)
as in, 2^1 * 3^1 = 6."""
powers = []
factor = 2
while num > 1:
power = 0
while num % factor == 0:
power += 1
num /= factor
if power > 0:
powers.append(power+1)
factor += 1
return powers

....
return reduce(mul, powers)

or to skip the odd factors:

def factorise(num):
"""Returns a list of prime factor powers. For example:
factorise(6) will return
[2, 2] (the powers are returned one higher than the actual value)
as in, 2^1 * 3^1 = 6."""
powers = []
factor = 2
while num > 1:
power = 0
while num % factor == 0:
power += 1
num /= factor
if power > 0:
powers.append(power+1)
factor = 3 if factor == 2 else factor + 2
return powers

This can be slightly optimised by taking factor 2 out of the loop.

def factorise(num):
"""Returns a list of prime factor powers. For example:
factorise(6) will return
[2, 2] (the powers are returned one higher than the actual value)
as in, 2^1 * 3^1 = 6."""
powers = []
power = 0
while num % 2 == 0:
power += 1
num /= 2
if power > 0:
powers.append(power+1)
factor = 3
while num > 1:
power = 0
while num % factor == 0:
power += 1
num /= factor
if power > 0:
powers.append(power+1)
factor += 2
return powers

To restrict the search to primes you would have to use a
sieve of Eratosthenes or something similar.
My first attempt (with a sieve from
http://code.activestate.com/recipes/117119/) only gave a speed decrease!!
But this had the sieve recreated for every triangle number. A global
sieve that is reused at each triangle number is better. But the speed
increase relative to the odd factors only is not dramatical.

# Based upon http://code.activestate.com/recipes/117119/

D = {9: 6} # contains composite numbers
Dlist = [2, 3] # list of already generated primes

def sieve():
'''generator that yields all prime numbers'''
global D
global Dlist
for p in Dlist:
yield p
q = Dlist[-1]+2
while True:
if q in D:
p = D[q]
x = q + p
while x in D: x += p
D[x] = p
else:
Dlist.append(q)
yield q
D[q*q] = 2*q
q += 2

def factorise(num):
"""Returns a list of prime factor powers. For example:
factorise(6) will return
[2, 2] (the powers are returned one higher than the actual value)
as in, 2^1 * 3^1 = 6."""
powers = []
power = 0
for factor in sieve():
power = 0
while num % factor == 0:
power += 1
num /= factor
if power > 0:
# if you really want the factors then append((factor, power))
powers.append(power+1)
if num == 1:
break
return powers

--
Piet van Oostrum <>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email:

Piet van Oostrum, Jul 6, 2009

3. ### Piet van OostrumGuest

Re: Why is my code faster with append() in a loop than with a large list?

Sorry, there was an error in the sieve in my last example. Here is a
corrected version:

D = {9: 6} # contains composite numbers
Dlist = [2, 3] # list of already generated primes
def sieve():
'''generator that yields all prime numbers'''
global D
global Dlist
for q in Dlist:
yield q
while True:
q += 2
p = D.pop(q, 0)
if p:
x = q + p
while x in D: x += p
D[x] = p
else:
Dlist.append(q)
D[q*q] = 2*q
yield q

--
Piet van Oostrum <>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email:

Piet van Oostrum, Jul 6, 2009
4. ### Dave AngelGuest

Scott David Daniels wrote:
> <div class="moz-text-flowed" style="font-family: -moz-fixed">Piet van
> Oostrum wrote:
>>>>>>> Dave Angel <> (DA) wrote:

>>
>>> DA> It would probably save some time to not bother storing the
>>> zeroes in the
>>> DA> list at all. And it should help if you were to step through a
>>> list of
>>> DA> primes, rather than trying every possible int. Or at least
>>> constrain
>>> DA> yourself to odd numbers (after the initial case of 2).

>>
>> ...
>> # Based upon http://code.activestate.com/recipes/117119/
>>
>> D = {9: 6} # contains composite numbers

> XXX Dlist = [2, 3] # list of already generated primes
> Elist = [(2, 4), (3, 9)] # list of primes and their squares
>>

> XXX def sieve():
> XXX '''generator that yields all prime numbers'''
> XXX global D
> XXX global Dlist
> def sieve2():
> '''generator that yields all primes and their squares'''
> # No need for global declarations, we alter, not replace
> XXX for p in Dlist:
> XXX yield p
> XXX q = Dlist[-1]+2
>
> for pair in Elist:
> yield pair
> q = pair[0] + 2
>
>> while True:
>> if q in D:
>> p = D[q]
>> x = q + p
>> while x in D: x += p
>> D[x] = p
>> else:

> XXX Dlist.append(q)
> XXX yield q
> XXX D[q*q] = 2*q
> square = q * q
> pair = q, square
> Elist.append(pair)
> yield pair
> D[square] = 2 * q
>> q += 2
>>
>> def factorise(num):
>> """Returns a list of prime factor powers. For example:
>> factorise(6) will return
>> [2, 2] (the powers are returned one higher than the actual
>> value)
>> as in, 2^1 * 3^1 = 6."""
>> powers = []
>> power = 0

> XXX for factor in sieve():
> for factor, limit in sieve2():
>> power = 0
>> while num % factor == 0:
>> power += 1
>> num /= factor

> XXX if power > 0:
> if power: # good enough here, and faster
>> # if you really want the factors then append((factor,
>> power))
>> powers.append(power+1)

> XXX if num == 1:
> XXX break
> XXX return powers
> if num < limit:
> if num > 1:
> # if you really want the factors then append((num, 1))
> powers.append(2)
> return powers
>
> OK, that's a straightforward speedup, _but_:
> factorize(6) == [2, 2] == factorize(10) == factorize(15)
> So I am not sure exactly what you are calculating.
>
>
> --Scott David Daniels
>
>
> </div>
>

The OP only needed the number of factors, not the actual factors. So
the zeroes in the list are unneeded. 6, 10, and 15 each have 4 factors.

Dave Angel, Jul 6, 2009
5. ### Piet van OostrumGuest

Re: Why is my code faster with append() in a loop than with a large list?

>>>>> Scott David Daniels <> (SDD) wrote:

>SDD> # No need for global declarations, we alter, not replace

Yes, I know, but I find it neater to do the global declarations, if only
for documentation. And they don't affect the run time, only the compile
time.
--
Piet van Oostrum <>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email:

Piet van Oostrum, Jul 6, 2009