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

[Arnaud Delobelle]

On Sep 2, 12:51 pm, jwrweather... at gmail.com wrote:
[...]
> The resulting executable takes 0.24 seconds to run. I'm not expecting
> a scripting language to run faster than native code, but I was
> surprised at how much slower it was in this case. Any ideas as to what
> is causing python so much trouble in the above code?

Sorry I didn't answer your question at all in my previous post
(although my modified method gets the answer in about 6s on a measly
PB G4 1GHz :).
Your little code snippet is just about the worst bit of code for
python to be compared to C.  Three loops, only integer arithmetic:
that's not going to make Python shine!

Nevertheless as you optimise your C snippet (-O3), there are probably
a few things that the compiler does for you:

* as in the inner loop, a*a + b*b always remain the same, it is
probably stored in a register once and for all
* in the second loop, a*a remains the same so it might be calculated
once and for all as well.

It gives this:

M = 1000
solutions = [0] * M

def f1():
    "Your original implementation"
    for a in xrange(1, M):
        for b in xrange(1, M - a):
            for c in xrange(1, M - a - b):
                if a**2 + b**2 == c**2:
                    solutions[a+b+c] += 1

def f2():
    "a*a + b*b precalculated"
    for a in xrange(1, M):
    a2 = a*a
        for b in xrange(1, M - a):
            s = a2 + b*b
            for c in xrange(1, M - a - b):
                if s == c*c:
                    solutions[a+b+c] += 1

It doesn't make it as quick as C of course, but more than halves the
execution time.

--
Arnaud