Why is this algorithm slow in Python compared to its VB.net implementation?

Question

The following code takes around two minutes to run on Python 3.3, but an equivalent VB.net version runs in less than one second. Is there a particular inefficiency I've done here that makes it slow on Python? Or is it just a slower interpreter? Could Python's math library be that much slower? (Initializing x, x1, and x3 to float doesn't make much difference).

Python:

inc = 2*3*5*7
for x in range(inc,200000,inc):
    n = 0
    y = x * x + x

    for x1 in range(x+1, y):
        x2 = x1 / (x1 - x) * x
        x3 = round(x2)
        if abs(x2 - x3) < 0.0000001:
            if x3 < x1: break
            n += 1
    if n > 500: print(x, n)

(I realize there are better algorithms to accomplish the same thing. I'm interested in improving the Python implementation of this, in order to learn more Python.)

VB Code:

Dim x, x1, x2, x3, y As Double
Dim n As Integer

For x = 0 To 200000 Step 2 * 3 * 5 * 7
  n = 0
  y = x * x + x
  For x1 = x + 1 To y
    x2 = x1 / (x1 - x) * x
    x3 = Round(x2)
    If Math.Abs(x2 - x3) < 0.0000001 Then
      If x3 < x1 Then Exit For
      n += 1
      End If
    Next x1
  If n > 500 Then sb.Append(x & " " & x1 & " " & x3 & " " & n & vbCrLf)
  Next x

Answer 1

You have not written particularly inefficient code, no. You’re simply seeing a normal performance difference between a purely interpreted language (and not a particularly fast one at that) and a compiled language. As evidence, consider the profile generated by running your code under cProfile for fifteen seconds:

% python3 -m cProfile stackoverflow.py & pid=$\!; sleep 15; kill -INT $!
55440 608
60060 608
65520 608
69300 563
73920 527
78540 608
         32855602 function calls in 14.969 seconds
   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1   10.557   10.557   14.969   14.969 so.py:1(<module>)
 16427796    0.646    0.000    0.646    0.000 {built-in method abs}
        1    0.000    0.000   14.969   14.969 {built-in method exec}
        6    0.000    0.000    0.000    0.000 {built-in method print}
 16427797    3.766    0.000    3.766    0.000 {built-in method round}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Your largest cost center appears to be the round function, but even that only consumes about a third of the runtime. This suggests that the issue is not any particular part of your own code, but rather a combination of an inefficient algorithm and a slow interpreter.

Answer 2

Problem is not with the python math --- python math operations are as fast as in any other language. Problem is with speed of python bytecode execution, which is slow.

You can sped it up using following techniques:

• Use numpy arrays and do proper vectorisation (or array programming). Mind that yoy not only you need use numpy, but also you need to remove python loops using vectorisation. I have been using it, and in most of cases you can speed up calculation by 20-100 times wihout much effort.
• Use cython or weave to write code that will be directly translated to C. See this article.

If you want to learn python I'd say that numpy is the way to go, as with cython and weave you'd learn how to write C code more.