Project Euler 2 가속화 2.21 마이크로초를 절약합니다.

피보나치 수열의 항은 앞의 2개의 항의 합이다. 처음 2항을 1, 2로 하면, 처음 10항은

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
수열의 항의 값이 400 만 이하인 짝수 값의 항의 합계를 구해라.
ㅡㅡㅡ//오…사쿠라. 네. jp/p로지ぇc테우ぇr/그리고 x. php? cmd=레아 d&파게=P로 b㎇m%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분 정도 걸렸지만.