Geek asks and answers

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

The following code takes about two minutes to run on Python 3.3, but the equivalent version of VB.net works in less than one second. Is there any particular inefficiency I made here that slows down Python? Or is it just a slow translator? Can a Python math library be much slower? (Initializing x, x1, and x3 to float doesn't really matter).

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 understand that there are better algorithms to achieve the same. I'm interested in improving the Python implementation of this in order to learn more about 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
+3
source share
4 answers

, . ( ) . , cProfile :

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

, -, round, . , - , .

+4

python: python , . - python, .

, :

  • numpy ( programming). , yoy numpy, python . , 20-100 .
  • cython , , C. . .

python, , numpy - , cython weave, , C- .

+1

cython to C -ify Python. ( __future__, xrange ) Python 2.7 ipython notebook.

from __future__ import division

%%timeit
inc = 2*3*5*7
for x in xrange(inc,200000,inc):
    n = 0
    y = x * x + x
    for x1 in xrange(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: a,b = x,n

1 loops, best of 3: 1min 5s per loop


%load_ext cythonmagic
%%cython -f
#cython: boundscheck=False
#cython: wraparound=False
from __future__ import division
from libc.math cimport fabs
from libc.math cimport round as cround
import time
cdef int inc = 2*3*5*7
cdef int x
cdef int n
cdef int y
cdef int x1
cdef double x2
cdef double x3
cdef int a, b
t0 = time.time()
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 = cround(x2)
        if fabs(x2 - x3) < 0.0000001:
            if x3 < x1: break
            n += 1
    if n > 500: a,b = x,n
t1 = time.time()
print "time elapsed:", t1 - t0, "sec"

time elapsed: 0.900931119919 sec
+1

pypy python. pypy JIT-, .

pypy 36 , python .

EDIT: , , , x2 , .is_integer , python3, pypy 1 . , , .

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 = float(x1) / (x1 - x) * x
        if x2.is_integer():
            if x2 < x1: break
            n += 1
    if n > 500: print(x, n)
0

More articles:


All Articles