如何加速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

很抱歉告诉你，这不是优化的问题。无论你选择哪种编程语言或实现方式，这个算法在最坏和平均情况下都不是 O(n*log n)。你可能需要了解一下 大O符号是怎么工作的，并尝试开发一个更好的算法。

Answer 2

你仍然可以使用Python的写法，同时享受C语言的速度，这可以通过Cython这个项目来实现。第一步是把循环转换成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):

接下来，如果你的数组是纯C语言的数组，那就更好了，这样就不需要复杂的Python比较和数组访问了。对于你的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

这段代码风格可能不是最优雅的，但在紧急情况下，我们需要用一些特别的方式来编码。试着把你那些嵌套的循环变成一个大的生成器表达式：

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

更新了代码，使用了内置的 next 和 product，还有 Python 3 的 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