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 下，看看它会如何 react 。我的第一个版本几乎是 1:1 的转换，运行速度非常慢(Python 超过 120 秒，C 低于 1 秒)。 我做了一些优化，这是我得到的:

#!/usr/bin/env/python
from cmath import sqrt
import cProfile
from pstats import Stats

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

def main():        
        maxNumber = 5000
        diff = 1000
        for i in range(1, maxNumber):
                p_i = i * (3 * i - 1 ) / 2
                for g in range(i, maxNumber):
                        if i == g:
                                continue
                        p_g = g * (3 * g - 1 ) / 2
                        if p_i > p_g:
                                ma = p_i
                                mi = p_g
                        else:
                                ma = p_g
                                mi = p_i

                        if ma - mi < diff and quickCheck(ma - mi):
                                if quickCheck(ma + mi):
                                        print ('New couple ', ma, mi)
                                        diff = ma - mi


cProfile.run('main()','script_perf')
perf = Stats('script_perf').sort_stats('time', 'calls').print_stats(10)

它运行大约 16 秒，比 C 语言好，但也慢了近 20 倍。 现在，我知道 C 在这种计算方面比 Python 更好，但我想知道是否有我遗漏的东西(Python 方面，比如一个非常慢的函数等)可以使这个函数快点。 请注意，我使用的是 Python 3.1.1，如果这有所不同的话

Answer 1

由于 quickCheck 被调用了将近 25,000,000 次，您可能需要使用内存来缓存答案。

您可以用 C 和 Python 进行内存。在 C 中，事情也会快得多。

您在 quickCheck 的每次迭代中计算 1/6。我不确定这是否会被 Python 优化，但如果你能避免重新计算常量值，你会发现事情会更快。 C 编译器会为您做这件事。

做类似if condition: return True; else: return False 很愚蠢——而且很耗时。只需执行返回条件。

在 Python 3.x 中，/2 必须创建浮点值。您似乎为此需要整数。您应该使用 //2 划分。就其功能而言，它将更接近 C 版本，但我认为它不会快得多。

最后，Python一般都是解释型的。解释器总是比 C 慢得多。