Why is my code faster with append() in a loop than with a large list?
Dave Angel
davea at ieee.org
Mon Jul 6 13:13:48 EDT 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