Python代码优化（比C慢20倍）

Question

我写了一个非常糟糕的优化C代码，它做了一个简单的数学计算：

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))


unsigned long long int p(int);
float fullCheck(int);

int main(int argc, char **argv){
  int i, g, maxNumber;
  unsigned long long int diff = 1000;

  if(argc < 2){
    fprintf(stderr, "Usage: %s maxNumber\n", argv[0]);
    return 0;
  }
  maxNumber = atoi(argv[1]);

  for(i = 1; i < maxNumber; i++){
    for(g = 1; g < maxNumber; g++){
      if(i == g)
        continue;
      if(p(MAX(i,g)) - p(MIN(i,g)) < diff &&  fullCheck(p(MAX(i,g)) - p(MIN(i,g))) && fullCheck(p(i) + p(g))){
          diff = p(MAX(i,g)) - p(MIN(i,g));
          printf("We have a couple %llu %llu with diff %llu\n", p(i), p(g), diff);
      }
    }
  }

  return 0;
}

float fullCheck(int number){
  float check = (-1 + sqrt(1 + 24 * number))/-6;
  float check2 = (-1 - sqrt(1 + 24 * number))/-6;
  if(check/1.00 == (int)check)
    return check;
  if(check2/1.00 == (int)check2)
    return check2;
  return 0;
}

unsigned long long int p(int n){
  return n * (3 * n - 1 ) / 2;
}

然后我尝试（只是为了好玩）把它移植到Python下，看看它会有什么反应。我的第一个版本几乎是1:1的转换，运行速度非常慢（Python为120秒以上，C为1秒）。 我做了一些优化，这是我得到的：

^{pr2}$

它的运行时间大约为16秒，比C语言好，但也几乎慢了20倍。 现在，我知道在这类计算中，C比Python好，但是我想知道的是，我是否遗漏了一些东西（Python方面，比如一个非常慢的函数之类）可以使这个函数更快。 请注意，我使用的是python3.1.1，如果这有区别的话

Answer 1

由于quickCheck被调用了将近25000000次，您可能需要使用memorization来缓存答案。在

你可以用C和Python做记忆。C语言的速度也会快得多。在

在quickCheck的每个迭代中都在计算1/6。我不确定Python是否会对此进行优化，但是如果您可以避免重新计算常量值，您会发现事情会更快。C编译器为您完成这项工作。在

做像if condition: return True; else: return False这样的事情是愚蠢的，而且耗时。只需做return condition。在

{cdx>必须在Python中创建浮点值。你似乎需要整数。您应该使用//2除法。从功能上讲，它将更接近于C版本，但我不认为它有明显的更快。在

最后，Python通常被解释。解释器总是比C语言慢得多

Answer 2

因为函数p（）单调递增，所以可以避免比较值，因为g>；i意味着p（g）>；p（i）。此外，内环可以很早被打破，因为p（g）-p（i）>；=diff意味着p（g+1）-p（i）>；=diff。在

为了正确起见，我更改了quickCheck中的等式比较，将差异与epsilon进行比较，因为与浮点的精确比较非常脆弱。在

在我的机器上，使用Python2.6将运行时间减少到7.8ms。在JIT中使用PyPy可以将此时间缩短到0.77ms

在进行微优化之前，先看看微优化。微优化使得发现算法的变化变得更加困难，以获得相对较小的收益。在

EPS = 0.00000001
def quickCheck(n):
    partial_c = sqrt(1 + 24*n) / -6
    c = 1/6 + partial_c
    if abs(int(c) - c) < EPS:
        return True
    c = 1/6 - partial_c
    if abs(int(c) - c) < EPS:
        return True
    return False

def p(i):
    return i * (3 * i - 1 ) / 2

def main(maxNumber):
    diff = 1000

    for i in range(1, maxNumber):
        for g in range(i+1, maxNumber):
            if p(g) - p(i) >= diff:
                break 
            if quickCheck(p(g) - p(i)) and quickCheck(p(g) + p(i)):
                print('New couple ', p(g), p(i), p(g) - p(i))
                diff = p(g) - p(i)

Answer 3

我在我的机器上从~7秒变为~3秒：

• 为每个值预先计算i * (3 * i - 1 ) / 2，在你的计算中，它被计算了两次
• 对quickCheck的缓存调用
• 通过向范围中添加+1删除了if i == g
• 删除if p_i > p_g，因为p总是小于p

同时将quickCheck函数放在main中，使所有变量都成为局部变量（比全局变量查找速度更快）。 我相信还有更多的微优化可用。在

def main():
        maxNumber = 5000
        diff = 1000

        p = {}
        quickCache = {}

        for i in range(maxNumber):
            p[i] = i * (3 * i - 1 ) / 2

        def quickCheck(n):
            if n in quickCache: return quickCache[n]
            partial_c = (sqrt(1 + 24 * (n)))/-6 
            c = 1/6 + partial_c
            if int(c.real) == c.real:
                    quickCache[n] = True
                    return True
            c = c - 2*partial_c
            if int(c.real) == c.real:
                    quickCache[n] = True
                    return True
            quickCache[n] = False
            return False

        for i in range(1, maxNumber):
                mi = p[i]
                for g in range(i+1, maxNumber):
                        ma = p[g]
                        if ma - mi < diff and quickCheck(ma - mi) and quickCheck(ma + mi):
                                print('New couple ', ma, mi)
                                diff = ma - mi