如何加速python循环

Question

我看了几个网站上的几个讨论,但没有一个给我一个解决方案.这段代码运行时间超过5秒:

for i in xrange(100000000):
  pass

我正在研究整数优化问题,我必须使用 O(n log n)算法编辑:一个O(n²/ 4)算法,其中n代表所有矩阵'项,即在下面的代码中, n*m个= 10000.因此,对于矩阵100*100与10000层的元件,这将导致在近25000000迭代....它的代码可以总结如下:

m = 100
n = 100
for i in xrange(m):
  for j in xrange(n):
    for i2 in xrange(i + 1, m):
      for j2 in xrange(j + 1, n):
        if myarray[i][j] == myarray[i2][j2] and myarray[i2][j] == myarray[i][j2]:
          return [i, j], [i2, j2]

我应该放弃Python并返回Java或C？

我使用Python 2.7并且Psyco不可用.PyPy不支持Tkinter开箱即用,我正在使用Tkinter.

那么,它们会提高循环速度吗？还有其他解决方案吗？

Answer 1

不是最漂亮的编码风格,但绝望的时代需要绝望的编码.尝试将嵌套的嵌套循环转换为一个大的生成器表达式:

try:
    i,j,i2,j2 = ((i,j,i2,j2)
        for i in xrange(m)
          for j in xrange(n)
            for i2 in xrange(i + 1, m)
              for j2 in xrange(j + 1, n)
                if myarray[i][j] == myarray[i2][j2] and 
                    myarray[i2][j] == myarray[i][j2]).next()
    return [i,j],[i2,j2]
except StopIteration:
    return None

更新为使用builtins next和product,而Py3 range代替xrange:

from itertools import product
match = next(((i,j,i2,j2)
    for i, j in product(range(m), range(n))
        for i2, j2 in product(range(i+1, m), range(j+1, n))
            if myarray[i][j] == myarray[i2][j2] and 
                myarray[i2][j] == myarray[i][j2]), None)
if match is not None:
    i,j,i2,j2 = match
    return [i,j],[i2,j2]
else:
    return None

Answer 2

你仍然可以使用python表示法,并使用Cython项目获得C的速度.第一步是在C循环中转换循环:它是通过键入循环中使用的所有变量自动完成的:

cdef int m = 100
cdef int n = 100
cdef int i, j, i2, j2
for i in xrange(m):
  for j in xrange(n):
    for i2 in xrange(i + 1, m):
      for j2 in xrange(j + 1, n):

对于下一部分,如果myarray是纯C数组,那么没有丰富的python comparaison或数组访问会更好.使用你的python数组,你可以通过本机比较来删除丰富的比较(如果你的数组有两倍):

        cdef double a, b, c, d
        a = myarray[i][j]
        b = myarray[i2][j2]
        c = myarray[i2][j]
        d = myarray[i][j2]

        if a == b and c == d:
          return [i, j], [i2, j2]

您可以通过运行查看优化的进展情况cython -a yourfile.pyx,然后打开yourfile.html生成.您将看到Cython如何优化您的代码,并消除了Python开销.

Answer 3

很遗憾地告诉你，这不是优化的问题。无论您选择哪种语言或实现，该算法都不是O(n*log n)最坏和平均的情况。您可能想了解Big-O 表示法的工作原理并开发更好的算法。