On Sep 2, 7:20 am, Arnaud Delobelle <[EMAIL PROTECTED]> wrote: > On Sep 2, 12:51 pm, [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
