Optimizing Project Euler Solution #12

Question

Just to reiterate my prev. post, as I think it helps structure my weaknesses.

1. Coding methodology: Is the algorithm I used feasible or mostly correct? If not, how do I correct it and why won't it work or scale? I realize in some cases there are always going to be optimal solutions that will be over my head mathematically, but generally you can yield a solution that is within a reasonable range of optimal that is passable without knowing a ton of number theory in my experience. Where possible, I hope to learn algorithms along the way (such as the Sieve of Eratosthenes for prime ranges).

2. Coding execution: Given some pseudocode that we determine algorithmically will work, is the code written executed without redundancies and minimizing runtime?

3. Being more pythonic: Is something I'm not doing pythonic or can it be done simpler with some sort of library I don't know about? I believe this is mostly semantic, though in some cases can have large effects on performance (for instance, using map() instead of a for loop to apply int()).

I submitted the following code as a solution to Project Euler's #12. It's extremely slow, running in mean 7.13 seconds over 100 trials (I think; just using other submitted solutions as a benchmark. It seems as though solutions <1 seconds are generally decent.)

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def triangle_number(n):
    for i in range(n):
        n += i  
    return n

n = 1
while True:
    if len(factors(triangle_number(n))) >= 500:
        print n, triangle_number(n)   
        break
    else:
        n +=1

The code for the factors function was borrowed from here.

Answer 1

Use itertools

Itertools is a seriously overpowered module in the Python stlib, so use it as much as possible, for example the following:

reduce(list.__add__,

should be:

itertools.chain.from_iterable

For those unfamiliar with itertools, either this:

flatten = itertools.chain.from_iterable

or just flatten can be used.

Also, manually incrementing in a while loop should seriously be avoided, use itertools.count:

for i in itertools.count():

(i is usually used as a loop counter)

Math formula

The function:

triangle_number

should be written as return sum(range(n)), but there is a fast O(1) formula for it.

Answer 2

This is an addition to Caridorc's answer.

The usual reason for using itertools is that you don't want to construct lists when you don't need to. For example, in Python 2, you'd write for i in xrange(100) instead of for i in range(100) so that you don't have to construct a whole list of 100 numbers when you don't need it. If this doesn't make sense to you, familiarize yourself with the difference between generator expressions (genexprs) and list types.

In your case, however, there's a much more serious problem. You've got a Shlemiel the painter's algorithm!

When you write reduce(list.__add__, list_of_lists), you're essentially writing list_1 + ... + list_n. Python will evaluate this as follows:

• Take list_1 and list_2. Create a new list object of the proper size, and copy the elements from lists 1 and 2 into this new list. Call it intermediate_1.
• Take intermediate_1 and list_3. Create a new list of the proper size, and copy the elements from these two lists into the new list. Call it intermediate_2.
• …
• Take intermediate_(n-1) and list_n. Create a new list of the proper size, and copy the elements from these two lists into the new list. This is the final result.

Do you see the problem? This code is quadratic in both runtime and memory usage.

Here's some hard data. Consider the following function:

def fn(n):
    lists = [[0] * 10000 for i in xrange(n)]
    combined = reduce(list.__add__, lists)

I ran this for values of n of 1, 10, 100, 200, 250, 300, 400, and 500 (using IPython's %timeit fn(100), which does proper timing), and got the following results:

This definitely looks quadratic, and the coefficient of determination is R² = 0.99655, which indicates an extremely strong correlation.

When we instead use

def fast(n):
    combined = list(itertools.chain.from_iterable(
        [0] * 10000 for i in xrange(n)))

the time for fast(500) is just 65.8 ms instead of 7.42 s. (This shows that it is indeed the Shlemiel factor and not just large lists that's causing the slowdown.)

So, tl;dr, yes, use iterators—but make sure you know why!

So when use reduce?

Just a review of what reduce does for binary operators:

reduce(int.__add__, [x1, x2, x3], x0) = (((x0 + x1) + x2) + x3)

This is extended to general functions as follows:

reduce(f, [x1, x2, x3], x0) = f(f(f(x0, x1), x2), x3)

You should use reduce when you want to write code that looks like either of the above examples. Basically, reduce just saves you a loop.

Conceptually, you use reduce when you want to collapse a bunch of things into one value.

It may help to think of reduce in comparison with its other core functional operations:

• Use map when you want to transform a bunch of values to other things (like "reverse all these strings"). You use map in list comprehensions when you write [s[::-1] for s in strings].
• Use filter when you want to take a bunch of values and keep just some of them (like "take just the strings that are palindromes"). You use reduce in list comprehensions when you write [s for s in strings if s == s[::-1]].
• Use reduce when you want to collapse a bunch of things into one value (like "concatenate all these strings"). You can't use reduce in list comprehensions, because you're not creating a new list (just a value).

Notes:

• The problem in your case is that the version with list_1 + ... + list_n is just as bad in terms of efficiency. reduce wasn't your problem; it was what reduce expanded to.
• With reduce, you can omit the third argument x0, and reduce will use the first element of the sequence, or raise a TypeError if the sequence is empty.

Before noting some examples, it may be helpful to realize that some operations from __builtins__ are just reduce under the hood. For example:

• sum(ints) = reduce(int.__add__, ints, 0);
• all(bools) = reduce(lambda x, y: x and y, bools, True), and, similarly;
• any(bools) = reduce(lambda x, y: x or y, bools, False);
• min(ints) is like reduce(lambda x, y: x if x < y else y, ints) (it's actually a bit smarter), and, similarly;
• max(ints) is like reduce(lambda x, y: x if x > y else y, ints).

A few quick examples:

def factorial(n):
    return reduce(int.__mul__, xrange(1, n + 1), 1)

def replay_chess_game(moves):
    return reduce(lambda board, move: board.then(move),
                  moves,
                  INITIAL_BOARD)

def perform_git_rebase(commits):
    return reduce(lambda head, commit: head.cherry_pick(commit),
                  commits,
                  git_globals.refs.HEAD)

I don't use reduce all that much in Python, but you should definitely know when to use it.

Answer 3

In it's current state, it's hard for me to realise what factors is doing. The name indicates something, and I see it returns a set. So I'd assume that you're getting factors from n but your code is complicated and inscrutable to me. You should add a docstring explaining the basics of your function.

def factors(n):    
    """Return a set of factors by fooing the bar"""
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

It doesn't need to be extensive but a clue about implementation is useful.

triangle_number is also unclearly named, because what it returns is just a sum of numbers up to n. If triangle_number is a particular mathematical or programming concept, you should note that (though you don't need to explain it for people, they can look it up themselves). In this case I knew as you linked to the challenge itself, but bear in mind that the code itself shows no such association.

Also you could just use sum. sum is a built in function that takes a generator expression that @WChargin talked about. In simple terms, a generator is like a for loop condensed into a one line expression. So you could just do this:

def triangle_number(n):
    return sum(i for i in range(n))

Except (as Caridorc pointed out) since you literally just want the sum of all the values, you don't need i for i in. You can call sum on a list directly.

def triangle_number(n):
    return sum(range(n))

Answer 4

Simple maths #1: The n-th triangular number is equal to n (n + 1) / 2. One of n and n+1 is even, so it is either equal to (n/2) * (n+1) if n is even, or equal to n * ((n+1)/2) if n is odd.

These numbers have no common factor, and as a result the number of factors of the product is equal to the product of the number of factors. factors (x * y) = factors (x) * factors (y) if x and y have no common factors.

How does that affect your execution time if you look at the one millionth triangular number: Instead of counting the factors of 500,000,500,000 you count the factors of 500,000 and 1,000,001. With your code, you are checking about 700,000 numbers, where you only need to check 700 + 1000 numbers. That's a factor 500 less work. For larger numbers, it gets worse.

Simple maths #2: You can calculate the number of factors of n generally much faster than counting them by factoring n into its prime factors. If n = p^a * q^b * r^c for example then the number of factors is (a + 1)(b + 1)(c + 1). Take the number 500,000 above which is very quickly factored as 2^5 * 5^6 with 6 * 7 = 42 factors. If you look at bigger numbers this effect gets a lot stronger.

Simple maths #3: If you implement #2 you run into the paradox that numbers with many large prime factors take long to factor, but don't actually have many factors. So you are wasting a lot of time for numbers that cannot possibly be the solution. You are looking for a number with 100 factors - so you don't care whether a number has 2, 3, or 4 factors as long as you know it's nowhere near 100.

When you calculate factors, you usually divide the remaining unfactored number x by divisors up to x^(1/2). Instead, divide by divisors up to x^(1/3). If no factor is found, you don't know that x is a prime, but you know it is a prime, the square of a prime, or the product of two primes, with at most 4 factors. Then you calculate whether your number has enough factors if x has 4 factors (the max possible). And if not, then there is no need to factor further.

As an example, if you examine the n-th triangular number for n around 1 billion, if n is a prime or the product of two large primes you don't need to check divisors up to 31,000 but only up to 1,000.

Keep in mind that the same problem comes again later in the Euler series, but with much much larger numbers.