1

我试图用 Python编写问题 12（Project Euler）的解决方案。解决方案太慢了，所以我尝试在互联网上检查其他人的解决方案。我发现这段代码是用 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 个循环和一堆增量和模块。

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

用 xrange 替换范围：

用 xrange 替换 range 后，python 代码大约需要 1 分 11.48 秒才能执行。（大约快 1.2 倍）

4

3 回答 3

8

与 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 倍以内）。

于 2013-03-16T04:44:23.243 回答
4

重写除数计数算法以使用除数函数使运行时间减少到不到 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
于 2013-03-16T05:46:27.723 回答
1

这是我自己的变体，基于 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
于 2013-03-16T06:07:18.143 回答