Why is this loop heavy code so slow in Python? Possible Project Euler spoilers
Mark Dickinson
dickinsm at gmail.com
Sun Sep 2 21:23:21 CEST 2007
On Sep 2, 7:51 am, 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?
Below is some code and some timings that show that Python is spending
at least 1/3 of its time computing the squares: a*a, b*b and c*c. So
to explain why Python is so much slower than C, it should be enough to
explain what's going on with these multiplications. Here's my attempt
at an explanation:
To compute a*a, Python has to do the following, all at run-time
(1) Find the type of a.
(2) Look up the corresponding multiplication method for this type.
(3) (In the multiplication method): find the type of the right-hand
side, in this case a again.
(4) Having established that both arguments are ints, worry about
whether the result is going to overflow (in which case a long needs to
be returned).
(5) Do the multiplication.
(6) Allocate a new Python integer to hold the result, and return it.
The C code only has to do step (5), and this boils down to a single
machine instruction.
Mark
Code and timings: (Python 2.5.1/G4.)
def test():
solutions = [0] * 1000
for a in xrange(1, 1000):
for b in xrange(1, 1000 - a):
for c in xrange(1, 1000 - a - b):
if a*a + b*b == c*c:
solutions[a+b+c] += 1
return solutions
def test2():
solutions = [0] * 1000
squares = [x*x for x in xrange(1000)]
for a in xrange(1, 1000):
for b in xrange(1, 1000 - a):
for c in xrange(1, 1000 - a - b):
if squares[a] + squares[b] == squares[c]:
solutions[a+b+c] += 1
return solutions
>>> from profile import run
>>> run("l = test(); l2 = test2()")
5 function calls in 299.984 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall
filename:lineno(function)
1 0.010 0.010 0.010 0.010 :0(setprofile)
1 0.000 0.000 299.973 299.973 <string>:1(<module>)
1 0.000 0.000 299.984 299.984 profile:0(l = test(); l2
= test2())
0 0.000 0.000 profile:0(profiler)
1 182.262 182.262 182.262 182.262 test.py:1(test)
1 117.711 117.711 117.711 117.711 test.py:10(test2)
More information about the Python-list
mailing list