[PYTHON] Project Euler 2 Acceleration 2.21 Économisez des microsecondes.

Les termes de la suite de Fibonacci sont la somme des deux termes précédents. Si les deux premiers termes sont 1, 2, alors les 10 premiers termes sont:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Trouvez la somme des termes de valeur paire avec une valeur de colonne numérique inférieure ou égale à 4 millions. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202

Au début, j'ai écrit le code comme je l'avais imaginé.

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

Lorsque j'ai examiné le problème de savoir s'il y avait quelque chose qui pouvait être accéléré, j'ai remarqué que des nombres pairs apparaissaient tous les trois termes.

Lorsque n1 est le terme avant le terme pair et n2 est le terme pair, les termes n3, n4, n5 qui les suivent peuvent être exprimés par les équations suivantes.

n4 est nécessaire pour dériver le terme suivant, mais n3 peut probablement être omis! De plus, si vous choisissez des conditions paires, vous devriez pouvoir omettre l'instruction if qui détermine si elle est paire ou non!

J'ai donc écrit le code suivant.

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

J'ai commenté l'impression et mesuré le temps avec le code suivant.

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)

En conséquence, 1 million d'exécutions ont sauvé 2,21 secondes (2,21 microsecondes par exécution).

Économisez 221 secondes (environ 3 minutes et 40 secondes) en exécutant 100 millions de fois! De grandes économies!

Il m'a fallu environ 15 minutes pour écrire un nouveau code car c'était un code que je n'exécutais qu'une seule fois dans ma vie.