Pure Python, Project Euler, Question 3, Optimisation testing.

3.py

""" Sample Results:
Testing equivalency:
 - Passed (6857)

Averaging each function over 10 runs:

|--- Lazy Method
|     lazy_gp : 0.201404
| opt_lazy_gp : 0.100885
|   super_opt : 0.138018
|    opt_test : 0.143662
|--- 'Smart' Method 
|     func_gp : 0.292142
|       py_gp : 0.243346
|      opt_gp : 0.135746
|--- Simple Method 
|  simple_opt : 0.000624

Total Time: 12.734000
"""

import math

def is_prime(x):    
    for i in xrange(2, x):
        if x % i == 0:
            return False
    return True

def prime_factor(x, step = 1):
    for i in xrange(1, int(math.sqrt(x) + 1), step):
        if x % i == 0 and is_prime(i):
            yield i

def lazy_gp(i):
    """ Calculate highest prime factor of x

    Purely my own solution, this function was written in a lazy fashion"""
    n = None
    f = prime_factor(i)
    for n in f:
        pass
    return n

def opt_lazy_gp(i):
    """ Optimized version of gp(x)

    Currently the fastest version"""

    # This is the only added line
    step = 2 if i%2 else 1

    n = None
    f = prime_factor(i, step)
    for n in f:
        pass
    return n

def super_opt(i):
    """ "Optimized" version of opt_lazy_gp(x)

    (Removed function calls)"""
    step = 2 if i%2 else 1

    # This is actually slower, I suspect it is because it is kept in memory
    
    f = [x for x in xrange(1, int(math.sqrt(i)+ 1 ), step)
         if i % x == 0 and [y for y in xrange(2, x) if x % y == 0] == []]

    return f[-1]

def opt_is_prime(x):
    return [y for y in xrange(2, x) if x % y == 0] == []

def opt_prime_factor(x, step = 1):
    return [x for x in xrange(1, int(math.sqrt(i) + 1), step)
         if i % x == 0 and opt_is_prime(x)]

def opt_test(i):
    """ Combined version of opt_gp and super_opt to help find bottlenecks """

    f = opt_prime_factor(i, 2 if i%2 else 1)
    return f [-1]
    

def remove_multiples(i, li):
    """ Sets i and all of its multiples False in a list"""
    for x in xrange(i, len(li), i):
        if x in li:
            li.remove(x)

def prime_list(n):
    """ Generates a list of primes below n

    From:
    http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/

    Although I understand the function primes1(n),
    this is the primes2(n) function which I do not claim to

    It appears to be based on the "Geniune Sieve of Eratosthenes" Paper:
    http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
    """

    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n/3)
    for i in xrange(1,int(math.sqrt(n))/3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      k*k/3      ::2*k] = [False] * ((n/6-k*k/6-1)/k+1)
            sieve[k*(k-2*(i&1)+4)/3::2*k] = [False] * ((n/6-k*(k-2*(i&1)+4)/6-1)/k+1)
    return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]


def func_gp(i):
    sqrt_i = int(math.sqrt(i))
    primes = prime_list(sqrt_i)

    # "functional"
    factors = filter(lambda x: i % x == 0, range(2, sqrt_i))
    prime_factors = filter(lambda x: x in primes, factors)

    return prime_factors[-1]

def py_gp(i):
    sqrt_i = int(math.sqrt(i))
    primes = prime_list(sqrt_i)

    # pythonic
    factors = [x for x in range(2, sqrt_i + 1) if i % x == 0]
    prime_factors = [x for x in primes if x in factors]

    return prime_factors[-1]

def opt_gp(i):
    sqrt_i = int(math.sqrt(i))
    primes = prime_list(sqrt_i)

    # optimised using
    # http://stackoverflow.com/questions/6800193/what-is-the-most-efficient-way-of-finding-all-the-factors-of-a-number-in-python

    # Note: This line alone saves ~40% of run time. 
    step = 2 if i%2 else 1

    # This line is barely more efficient than the simple pythonic method used above
    factors = set(
        reduce(
            list.__add__,
            ([x, i//x] for x in range(1, sqrt_i + 1, step)
             if i % x == 0)))

    # faster but does not retain ordering!
    # prime_factors = list(factors.intersection(primes))
    prime_factors = [x for x in primes if x in factors]

    return prime_factors[-1]

def simple_opt(n):
    """ A version directly from http://www.s-anand.net/euler.html for comparison """
    i = 2
    while i * i < n:
        while n % i == 0:
            n = n / i
        i = i + 1
    return n

if __name__ == '__main__':
    from timeit import Timer
    from time import time

    i = 600851475143
    num_times = 10
    answer = 6857

    print("Testing equivalency:")
    if (answer ==
        lazy_gp(i) ==
        func_gp(i) ==
        py_gp(i) ==
        opt_gp(i) ==
        opt_lazy_gp(i) ==
        super_opt(i) ==
        opt_test(i) ==
        simple_opt(i)):
        
        print (" - Passed (%i)" % answer)
    else:
        print (" - Failed!")
        print (" - Should be: 6857")

    print("\nAveraging each function over %i runs:\n" % num_times)

    start_time = time()

    print("|--- Lazy Method")
    
    t = Timer("lazy_gp(600851475143 )", "from __main__ import lazy_gp")
    print("|     lazy_gp : %f" % (t.timeit(num_times)/num_times))
    
    t = Timer("opt_lazy_gp(600851475143 )", "from __main__ import opt_lazy_gp")
    print("| opt_lazy_gp : %f" % (t.timeit(num_times)/num_times))
    
    t = Timer("super_opt(600851475143 )", "from __main__ import super_opt")
    print("|   super_opt : %f" % (t.timeit(num_times)/num_times))
    
    t = Timer("opt_test(600851475143 )", "from __main__ import opt_test")
    print("|    opt_test : %f" % (t.timeit(num_times)/num_times))

    print("|--- 'Smart' Method ")
    
    t = Timer("func_gp(600851475143 )", "from __main__ import func_gp")
    print("|     func_gp : %f" % (t.timeit(num_times)/num_times))   

    t = Timer("py_gp(600851475143 )", "from __main__ import py_gp")
    print("|       py_gp : %f" % (t.timeit(num_times)/num_times))
    
    t = Timer("opt_gp(600851475143 )", "from __main__ import opt_gp")
    print("|      opt_gp : %f" % (t.timeit(num_times)/num_times))

    print("|--- Simple Method ")
    
    t = Timer("simple_opt(600851475143 )", "from __main__ import simple_opt")
    print("|  simple_opt : %f" % (t.timeit(num_times)/num_times))  

    end_time = time()

    print("\nTotal Time: %f" % (end_time - start_time))