幾乎相同的C++和Python代碼非常大的執行時間差異

Question

我試圖寫的Python爲Problem 12 (Project Euler)的解決方案。解決方案太慢了，所以我試圖在互聯網上檢查其他人的解決方案。我發現用C++編寫的this code與我的Python代碼幾乎完全相同，只是有一些微不足道的差異。

的Python：

def find_number_of_divisiors(n): 
    if n == 1: 
     return 1 

    div = 2 # 1 and the number itself 
    for i in range(2, n/2 + 1): 
     if (n % i) == 0: 
      div += 1 
    return div 

def tri_nums(): 
    n = 1 
    t = 1 
    while 1: 
     yield t 
     n += 1 
     t += n 

t = tri_nums() 
m = 0 
for n in t: 
    d = find_number_of_divisiors(n) 
    if m < d: 
     print n, ' has ', d, ' divisors.' 
     m = d 

    if m == 320: 
     exit(0) 

C++：

#include <iostream> 

int main(int argc, char *argv[]) 
{ 
    unsigned int iteration = 1; 
    unsigned int triangle_number = 0; 
    unsigned int divisor_count = 0; 
    unsigned int current_max_divisor_count = 0; 
    while (true) { 
     triangle_number += iteration; 
     divisor_count = 0; 
     for (int x = 2; x <= triangle_number/2; x ++) { 
      if (triangle_number % x == 0) { 
       divisor_count++; 
      } 
     } 
     if (divisor_count > current_max_divisor_count) { 
      current_max_divisor_count = divisor_count; 
      std::cout << triangle_number << " has " << divisor_count 
         << " divisors." << std::endl; 
     } 
     if (divisor_count == 318) { 
      exit(0); 
     } 

     iteration++; 
    } 
    return 0; 
} 

的Python代碼需要1分鐘和我的機器執行上25.83秒。而C++代碼大約需要4.628秒。它的速度快了18倍。我曾預計C++代碼會更快，但不會有這麼大的幅度，這也只是一個簡單的解決方案，它只包含2個循環以及一堆增量和模塊。

雖然我很感謝如何解決這個問題的答案，但我想問的主要問題是爲什麼C++代碼如此之快？我在Python中使用/做錯了什麼？

---

更換範圍與x範圍：

與x範圍的Python代碼替換範圍之後需要1分鐘左右11.48秒執行。 （大約快1.2倍）

Answer 1

這正是C++與Python相比將會大放異彩的代碼：一個相當緊密的循環，用於執行算術運算。 （我在這裏忽略算法加速，因爲你的C++代碼使用相同的算法，而且看起來你明確沒有要求這麼做......）

C++將這種代碼編譯成相對較少處理器的指令數量（以及它所做的一切可能都適合CPU高速緩存的超高速級別），而Python對每個操作都有很多的間接級別。例如，每次增加一個數字時，都會檢查該數字是否只是溢出，並且需要移入更大的數據類型。

這就是說，一切都不一定丟失！這也是像PyPy這樣的即時編譯器系統能夠很好地完成的代碼，因爲一旦它經歷了幾次循環，它就會將代碼編譯成類似於C++代碼啓動的代碼。在我的筆記本電腦：

$ time python2.7 euler.py >/dev/null 
python euler.py 72.23s user 0.10s system 97% cpu 1:13.86 total 

$ time pypy euler.py >/dev/null      
pypy euler.py > /dev/null 13.21s user 0.03s system 99% cpu 13.251 total 

$ clang++ -o euler euler.cpp && time ./euler >/dev/null 
./euler > /dev/null 2.71s user 0.00s system 99% cpu 2.717 total 

使用Python代碼的版本xrange而不是range。對於我來說，優化級別對於C++代碼沒有什麼影響，並且使用GCC而不是Clang。

雖然我們處於這種情況，但這也是Cython可以做得很好的一種情況，它將幾乎Python代碼編譯爲使用Python API的C代碼，但在可能的情況下使用原始C代碼。如果我們通過添加一些類型聲明，並刪除迭代器更改您的代碼只是一點點，因爲我不知道如何用Cython有效地處理這些，讓

cdef int find_number_of_divisiors(int n): 
    cdef int i, div 
    if n == 1: 
     return 1 

    div = 2 # 1 and the number itself 
    for i in xrange(2, n/2 + 1): 
     if (n % i) == 0: 
      div += 1 
    return div 

cdef int m, n, t, d 
m = 0 
n = 1 
t = 1 
while True: 
    n += 1 
    t += n 
    d = find_number_of_divisiors(t) 
    if m < d: 
     print n, ' has ', d, ' divisors.' 
     m = d 

    if m == 320: 
     exit(0) 

然後在我的筆記本電腦，我得到

$ time python -c 'import euler_cy' >/dev/null 
python -c 'import euler_cy' > /dev/null 4.82s user 0.02s system 98% cpu 4.941 total 

（在C++代碼的2倍以內）。

Answer 2

重寫除數計數算法使用divisor function使運行時間縮短到小於1秒。它仍然有可能變得更快，但並不是真的有必要。

這是爲了表明：在使用語言特性和編譯器進行任何優化技巧之前，您應該檢查您的算法是否是瓶頸。編譯器/解釋器的技巧確實非常強大，正如Dougal的答案中所示，Python和C++之間的差距已經被等價的代碼所封閉。但是，正如你所看到的，算法的改變會立即帶來巨大的性能提升，並將運行時間降低到算法效率低下的C++代碼的水平（我沒有測試C++版本，但是在我6年前的計算機上，下面的代碼完成運行在〜0.6s）。

下面的代碼是用Python 3.2.3編寫和測試的。

import math 

def find_number_of_divisiors(n): 
    if n == 1: 
     return 1 

    num = 1 

    count = 1 
    div = 2 
    while (n % div == 0): 
     n //= div 
     count += 1 

    num *= count 

    div = 3 
    while (div <= pow(n, 0.5)): 
     count = 1 
     while n % div == 0: 
      n //= div 
      count += 1 

     num *= count 
     div += 2 

    if n > 1: 
     num *= 2 

    return num 

Answer 3

這是我建立在nhahtdh的因子計數優化再加上我自己的因式分解代碼變種自己：

def prime_factors(x): 
    def factor_this(x, factor): 
     factors = [] 
     while x % factor == 0: 
      x /= factor 
      factors.append(factor) 
     return x, factors 
    x, factors = factor_this(x, 2) 
    x, f = factor_this(x, 3) 
    factors += f 
    i = 5 
    while i * i <= x: 
     for j in (2, 4): 
      x, f = factor_this(x, i) 
      factors += f 
      i += j 
    if x > 1: 
     factors.append(x) 
    return factors 

def product(series): 
    from operator import mul 
    return reduce(mul, series, 1) 

def factor_count(n): 
    from collections import Counter 
    c = Counter(prime_factors(n)) 
    return product([cc + 1 for cc in c.values()]) 

def tri_nums(): 
    n, t = 1, 1 
    while 1: 
     yield t 
     n += 1 
     t += n 

if __name__ == '__main__': 
    m = 0 
    for n in tri_nums(): 
     d = factor_count(n) 
     if m < d: 
      print n, ' has ', d, ' divisors.' 
      m = d 
      if m == 320: 
       break