1

Project Euler からの問題 48 の説明:

系列、1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317。系列の最後の 10 桁を検索します、1^1 + 2^2 + 3^3 + ... + 1000^1000。

Pythonでワンライナーを使用してこの問題を解決しました：

print sum([i**i for i in range(1,1001)])%(10**10)

Python では除算 mod n が非常に高速であることを思い出したので、ほぼ瞬時にそのようにしました。しかし、これが内部でどのように機能するのか (Python はどのような最適化を行うのか?)、なぜこれがそれほど高速なのかはまだわかりません。

これについて説明していただけますか？操作はmod 10**10、全体の合計ではなく、リスト内包表記のすべての反復に適用されるように最適化されていますか?

$ time python pe48.py 
9110846700

real 0m0.070s
user 0m0.047s
sys  0m0.015s
4

2 に答える 2

4

とすれば

print sum([i**i for i in range(1,1001)])%(10**10)

と

print sum([i**i for i in range(1,1001)])

Python でも同様に高速に機能するため、最後の質問に対する答えは「いいえ」です。

したがって、Python は整数の累乗を非常に高速に実行できなければなりません。そして、たまたま整数の累乗が O(log(n)) の乗算になります: http://en.wikipedia.org/wiki/Exponentiation#Efficient_computation_of_integer_powers

基本的には、 2^100 = 2*2*2*2*2... を 100 回実行する代わりに、 2^100 が 2^64 * 2^32 * 2^4 でもあることに気付きます。 2 を何度も二乗して、2^2、2^4、2^8 などを得ることができます。これら 3 つの要素すべての値を見つけたら、それらを乗算して最終的な答えを求めます。これにより、必要な乗算操作がはるかに少なくなります。その方法の詳細はもう少し複雑ですが、Python は十分に成熟しており、そのようなコア機能で十分に最適化されています。

于 2013-03-17T23:19:42.943 に答える
1

いいえ、全額に適用されます。合計自体の計算は非常に高速です。引数が整数の場合、指数をすばやく実行するのはそれほど難しくありません。

于 2013-03-17T23:20:19.787 に答える