Project Euler 2 高速化 2.21マイクロ秒を節約する。
フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項の値が400万以下の, 偶数値の項の総和を求めよ.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202
最初は思いつくままコードを書いてみた。
def cof():
(v1, v2) = (1, 2)
max = 4 * (10**6)
s = 0
while v2<=max:
if not v2 % 2: s += v2
(v1, v2) = (v2, v1+v2)
print s
なんか高速化できるところないかなと問題を眺めていたところ、偶数は3項おきに出現することに気が付いた。
n1を偶数の前の項、n2を偶数項とした時、それらに続く項n3,n4,n5は次の式で表せる。
n4はその次の項を導出するのに必要だけど、n3はおそらく省略できるはず!しかも偶数項に決め打てば偶数かどうかの判定をするif文も省略できるはず!
ということで次のコードを書いてみた。
def cof2():
(v1, v2) = (1, 2)
max = 4 * (10**6)
s = 0
while v2 <= max:
s += v2
(v1, v2) = (v1+2*v2, 2*v1+3*v2)
print s
print をコメントアウトし、次のコードで時間を測定してみた。
def get_time(func,name,num):
import time
print "%s start." % name
total = 0
for i in range(0,num):
start = time.time()
func()
end = time.time()
total += end - start
print "%s finished." % name
print total
if __name__ == '__main__':
num = 10 ** 6
#num = 1
get_time(cof,"cof",num)
get_time(cof2,"cof2",num)
結果、100万回実行で2.21秒(1回あたり2.21マイクロ秒)節約できた。
1億回実行すれば221秒(約3分40秒)の節約!すごい節約!
人生で1回しか実行しないコードなうえ、新たなコードを作るにバグに悩まされて15分くらいかかったけど。
Author And Source
この問題について(Project Euler 2 高速化 2.21マイクロ秒を節約する。), 我々は、より多くの情報をここで見つけました https://qiita.com/cof/items/2591c15c6f63c89f304c著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .