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

Dave Angel davea at ieee.org
Mon Jul 6 19:13:48 CEST 2009


Scott David Daniels wrote:
> <div class="moz-text-flowed" style="font-family: -moz-fixed">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
>
> </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.





More information about the Python-list mailing list