c++ - 几乎相同的 C++ 和 Python 代码的执行时间差异很大

Question

我正在尝试为 Problem 12 (Project Euler) 编写解决方案在 Python 中。解决方案太慢了，所以我尝试在互联网上查看其他人的解决方案。我找到了 this code用 C++ 编写，与我的 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 个循环和一堆增量和 mod 的简单解决方案来说也是如此。

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

---

用 xrange 替换范围:

将 range 替换为 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

使用带有 xrange 的 Python 代码版本而不是 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 倍内)。