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

Piet van Oostrum wrote:
Dave Angel <davea@xxxxxxxxxxxxxxxxx> (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@xxxxxxx
.

Relevant Pages

  • Re: Why is my code faster with append() in a loop than with a large list?
    ... XXX yield p ... (the powers are returned one higher than the actual value) ... num /= factor ...
    (comp.lang.python)
  • Re: Self Study problem help - Group theory
    ... > numerator and the denominator will decompose into powers of the primes ... Where do the *powers* of primes come from? ... > the bottom, and none of them are 2, so no matter what we can never ...
    (sci.math)
  • Re: What is Sum(1/p log p)?
    ... I know PNT. ... split the sum according to powers of 2 (see below for what ... the difference of number of primes between two consecutive ...
    (sci.math.research)
  • Re: A question on "sufficiently large".
    ... large even integer is a sum of two primes and exactly 13 powers ... Roger Heath-Brown didn't prove that every sufficiently large even number is a sum of 2 primes, ... large even number is a sum of 2 primes and 13 powers of 2. ...
    (sci.logic)
  • Re: Hashtable efficiency
    ... Probably because finding primes is a lot more difficult that finding ... powers of 2. ... The *reason* why you use prime hash table sizes is that it's the simplest ...
    (comp.lang.java.programmer)
Loading