Speeding up a script -- looking for ideas

[Tim Peters]

[Richard Bow]
> I'm hoping to get some hints for significantly speeding up the below
> script. I've found 43 integers between 1 and 1,000,000 that satisfy the
> condition, and would like to push on toward 10,000,000 in hopes
> of finding an integer for which there are 3 pairs. Of course, another
> reason for asking is to learn more Python from you guys.

I'm going to cheat by using a better algorithm.  This finds all the results
up to 10,000,000 in about half a second on my box (under current CVS Python,
which is a bit zippier).  You'll find going up to 100,000,000 more
interesting (which takes longer than an eyeblink, but a lot less time than
it's taking me to add this gratuitous parenthetical comment <wink>).

The key gimmick:  The cube root of N is a *hell* of a lot smaller than N.
So rather than look at each N and then look for all ways of expressing N as
the sum of two cubes, instead loop over all cubes and figure out all the N
that can be gotten via adding two cubes.

This is Rule #1 of Python optimization:

    Any Python program using a dict is 1000x faster than any C program.

There are no exceptions to this rule <ahem>.


def drive(start, end):
    largest_root = int(end ** 0.333)
    while (largest_root + 1) ** 3 < end:
        largest_root += 1

    cubes = [i**3 for i in xrange(1, largest_root + 1)]
    ncubes = len(cubes)

    n2cubes = {}  # map n to list of (cube1, cube2)
    for i in xrange(ncubes):
        cube1 = cubes[i]
        for j in xrange(i, ncubes):
            cube2 = cubes[j]
            n = cube1 + cube2
            if n > end:
                break
            n2cubes.setdefault(n, []).append((cube1, cube2))

    for n, pairs in n2cubes.iteritems():
        if len(pairs) >= 2:
            print n, pairs