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

[Greg Copeland]

On Sep 2, 7:20 am, Arnaud Delobelle <arno... at googlemail.com> wrote:
> On Sep 2, 12:51 pm, jwrweather... at gmail.com wrote:
>
>
>
> > I'm pretty new to python, but am very happy with it. As well as using
> > it at work I've been using it to solve various puzzles on the Project
> > Euler site -http://projecteuler.net. So far it has not let me down,
> > but it has proved surprisingly slow on one puzzle.
>
> > The puzzle is: p is the perimeter of a right angle triangle with
> > integral length sides, {a,b,c}. which value of p  < 1000, is the
> > number of solutions {a,b,c} maximised?
>
> > Here's my python code:
>
> > #!/usr/local/bin/python
>
> > solutions = [0] * 1001
> > p = 0
>
> > for a in xrange(1, 1000):
> >     for b in xrange(1, 1000 - a):
> >         for c in xrange(1, 1000 - a - b):
> >             p = a + b + c
> >             if p < 1000:
> >                 if a ** 2 + b ** 2 == c ** 2:
> >                     solutions[p] += 1
>
> > max = 0
> > maxIndex = 0
> > index = 0
> > for solution in solutions:
> >     if solution > max:
> >         max = solution
> >         maxIndex = index
> >     index += 1
>
> > print maxIndex
>
> > It takes 2 minutes and twelve seconds on a 2.4GHz Core2Duo MacBook
> > Pro. Surprised at how slow it was I implemented the same algorithm in
> > C:
>
> > #include <stdio.h>
> > #include <stdlib.h>
>
> > int main() {
> >   int* solutions = calloc(1000, sizeof(int));
>
> >   int p;
> >   for(int a = 1; a < 1000; ++a) {
> >     for(int b = 1; b < 1000 - a; ++b) {
> >       for(int c = 1; c < 1000 - a - b; ++c) {
> >         p = a + b + c;
> >         if(p < 1000) {
> >           if(a * a + b * b == c * c) {
> >             solutions[p] += 1;
> >           }
> >         }
> >       }
> >     }
> >   }
>
> >   int max = 0;
> >   int maxIndex = 0;
>
> >   for(int i = 0; i < 1000; ++i) {
> >     if(solutions[i] > max) {
> >       max = solutions[i];
> >       maxIndex = i;
> >     }
> >   }
> >   printf("%d\n", maxIndex);
> >   return 0;
>
> > }
>
> > gcc -o 39 -std=c99 -O3 39.c
>
> > 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?
>
> from math import sqrt
>
> solutions = [0] * 1001
> p = 0
>
> for a in xrange(1, 1000):
>     a2 = a*a
>     for b in xrange(1, 1000 - a):
>         c = sqrt(a2 + b*b)
>         if c == int(c) and a+b+c < 1000:
>             solutions[a+b+int(c)] += 1
>
> max = 0
> maxIndex = 0
> index = 0
> for solution in solutions:
>     if solution > max:
>         max = solution
>         maxIndex = index
>     index += 1
>
> print maxIndex
>
> --
> Arnaud

For the curious:

O	O + P	A	A + P
======= ======= ======= =======
2:22.56 0:25.65 0:00.75 0:00.20

O = Original Implementation
P = Psyco (psyco.full())
A = Arnaud's Revised Implementation