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

[jwrweatherley]

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?

[Neil Cerutti]

On 2007-09-02, Martin v. Löwis <ma****@v.loewi s.dewrote:

>>(2) it is a interpretation language

Not quite. It's compiled to byte-code - just like Java (would
you call Java an 'interpreted language' ?)

Python is not implemented like Java. In Java (at least in
HotSpot), the byte code is further compiled to machine code
before execution; in Python, the byte code is interpreted.

Whether this makes Python an interpreter or a compiler, I don't
know.

I'd call it an integrated compiler and virtual machine--a classic
combination.

--
Neil Cerutti

[Paul Rubin]

Steven D'Aprano <st***@REMOVE-THIS-cybersource.com .auwrites: A big

question mark in my mind is Lisp, which according to aficionados is
just as dynamic as Python, but has native compilers that generate
code running as fast as highly optimized C. I'm not qualified to
judge whether the lessons learnt from Lisp can be applied to Python,
but in any case Lisp is an old, old language -- only Fortran is
older. The amount of development effort and money put into Lisp
dwarfs that put into Python by possibly a hundred or more.

Writing a simple Lisp compiler is not all that difficult. There's a
chapter in SICP about how to do it, so it's sometimes part of
introductory courses. To get C-like performance you end up having to
rely on user-supplied type declarations and/or type inference, but
even without that you can still do ok. I'd say Lisp is a less dynamic
language than Python. Lisp doesn't have duck typing and doesn't
represent class instance variables as dictionary elements that have to
be looked up at runtime all the time. This maybe even applies to
locals, e.g. in Python if you say

x = 3
print "hello"
y = x + 4

you're possibly not guaranteed that y=7, because you might have bound
sys.stdout to something with a .write method that reaches up the call
stack and messes with the caller's local variables, and if the langref
manual says this is supposed to work, then the compiler has to do it
like CPython. Maybe Python 4.0 will fix some of this stuff.

[jwrweatherley]

Thanks for all the answers to my question. I think what I need to take
away from this is that xrange is an object - I thought it was just
some loop construct, and that maths is slow in python - so avoid
pathological looping.I remember the first time I tried Objective-C on
OS X I used the NSNumber class for arithmetic - the results that time
were pretty awful too!

[Paul Boddie]

On 3 Sep, 15:39, jwrweather...@g mail.com wrote:

Thanks for all the answers to my question. I think what I need to take
away from this is that xrange is an object

Indeed, but using xrange can be faster than converting your "for"
loops to "while" loops plus a counter; I converted your code to use
the latter arrangement and it was noticeably slower. Perhaps the
repeated invocation of each xrange object's next method is less
expensive than repeatedly obtaining new incremented int objects and
testing them against other int objects.

- I thought it was just some loop construct, and that maths is slow in
python - so avoid pathological looping.

You'd be wise to avoid doing unnecessary work deep within nested loops
in any programming language. Sadly, it's not possible for the compiler
to work out that some calculations can be lifted out of the innermost
loops in Python, since the various guarantees that make such
operations possible in other languages are not offered by Python.

I remember the first time I tried Objective-C on OS X I used the
NSNumber class for arithmetic - the results that time were pretty
awful too!

Obviously, it'd be a fairer test if you used comparable numeric types
in both implementations , but a more capable numeric type would be
overkill for the C implementation of this program, and a less capable
numeric type doesn't exist for Python unless you're willing to use a
dialect such as Pyrex (as others have shown).

Paul

[Bruno Desthuilliers]

Martin v. Löwis a écrit :

>>(2) it is a interpretation language

Not quite. It's compiled to byte-code - just like Java (would you call
Java an 'interpreted language' ?)

Python is not implemented like Java. In Java (at least in HotSpot),
the byte code is further compiled to machine code before execution;

This is a VM-specific feature.

in Python, the byte code is interpreted.

Idem.

Whether this makes Python an interpreter or a compiler,
I don't know.

This is an old troll^Mdiscussi on !-)

Now IANAL, but AFAIK, the byte-code compilation stage can make a great
difference performances-wide, and for a same language, a byte-compiled
implementation is likely to be faster than a pure-interpreted one, at
least because of the saving on parsing time (please someone correct me
if I'm wrong) ...

[paulhankin]

On Sep 2, 12:51 pm, jwrweather...@g mail.com wrote:

... right-angled triangle puzzle solver

max = 0
maxIndex = 0
index = 0
for solution in solutions:
if solution max:
max = solution
maxIndex = index
index += 1

print maxIndex

Not that it solves your slowness problem, or has anything to
do with the question you asked :), but you can replace this
last segment of your code with:

print solutions.index (max(solutions) )

--
Paul Hankin