1

私はPythonで問題12（プロジェクトオイラー）の解決策を書こうとしていました。解決策が遅すぎたので、インターネットで他の人の解決策を調べてみました。私はこのコードが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倍高速）

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

xrangeの代わりにPythonコードのバージョンを使用しrangeます。最適化レベルは、C ++コードでは違いがなく、Clangの代わりにGCCを使用しても違いはありません。

私たちがそれに取り組んでいる間、これはCythonが非常にうまくいく場合でもあり、Python APIを使用するCコードにほぼPythonコードをコンパイルしますが、可能な場合は生の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秒未満に短縮されます。それをより速くすることはまだ可能ですが、実際には必要ではありません。

これは、次のことを示しています。言語機能とコンパイラを使用して最適化のトリックを実行する前に、アルゴリズムがボトルネックであるかどうかを確認する必要があります。PythonとC++の間のギャップが同等のコードで閉じられている、Dougalの回答に示されているように、コンパイラー/インタープリターのトリックは確かに非常に強力です。ただし、ご覧のとおり、アルゴリズムの変更により、パフォーマンスがすぐに大幅に向上し、実行時間がアルゴリズム的に非効率なC ++コードのレベルにまで低下します（C ++バージョンはテストしていませんが、6歳のコンピューターでテストしました）。 、以下のコードは〜0.6秒で実行を終了します）。

以下のコードは、Python3.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 に答える