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

rzed rzantow at gmail.com
Sun Sep 2 15:36:45 CEST 2007


jwrweatherley at gmail.com wrote in
news:1188733902.513512.87510 at r34g2000hsd.googlegroups.com: 

> 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
>

Once p >= 1000, it ain't goin' back. If you break out of the 
innermost loop here after that happens, you'll save a bunch of 
time.
 
> 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.
>
[...]
 
> 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? 
> 




More information about the Python-list mailing list