几乎相同的C++和Python代码的执行时间差异非常大

Question

我试图用Python 编写问题12(Project Euler)的解决方案.解决方案太慢了,所以我尝试在互联网上检查其他人的解决方案.我发现这个用C++编写的代码与我的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个循环和一堆增量和mod.

虽然我很欣赏如何解决这个问题的答案,但我想问的主要问题是为什么C++代码要快得多？我在python中使用/做错了吗？

---

用xrange替换范围:

用xrange替换范围后,python代码大约需要1分11.48秒才能执行.(快约1.2倍)

Answer 1

与Python相比,这正是C++将要发挥作用的一种代码:一个相当紧凑的循环来进行算术运算.(我将在这里忽略算法加速,因为你的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倍之内).