Why is this loop heavy code so slow in Python? Possible Project Euler spoilers

[Alex Martelli]

Paul Rubin <http://phr.cx@NOSPAM.invalid> wrote:

> aleax at mac.com (Alex Martelli) writes:
> > ...which suggests that creating an xrange object is _cheaper_ than
> > indexing a list...
> 
> Why not re-use the xrange instead of keeping a list around?
> 
>     Python 2.4.4 (#1, Oct 23 2006, 13:58:00) 
>     >>> a = xrange(3)
>     >>> print list(a)
>     [0, 1, 2]
>     >>> print list(a)
>     [0, 1, 2]

Reusing xranges is exactly what my code was doing -- at each for loop
you need an xrange(1, k) for a different value of k, which is why you
need some container to keep them around (and a list of xrange objects is
the simplest applicable container).

Your suggestion doesn't appear to make any sense in the context of the
optimization problem at hand -- what list(...) calls are you thinking
of?!  Please indicate how your suggestion would apply in the context of:

def f3(M=M, solutions=solutions):
    "pull out all the stops"
    xrs = [xrange(1, k) for k in xrange(0, M+1)]
    for a in xrs[M]:
        a2 = a*a
        for b in xrs[M-a]:
            s = a2 + b*b
            for c in xrs[M-a-b]:
                if s == c*c:
                    solutions[a+b+c] += 1


Alex