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

[Piet van Oostrum]

>>>>> 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).

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 <piet at cs.uu.nl>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email: piet at vanoostrum.org