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

Scott David Daniels Scott.Daniels at Acm.Org
Mon Jul 6 12:53:34 EDT 2009

```Piet van Oostrum wrote:
>>>>>> Dave Angel <davea at dejaviewphoto.com> (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
Scott.Daniels at Acm.Org

```