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. pe02.png

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. pe02_2.png

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). pe02_3.png

É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.

Recommended Posts

Project Euler 2 Acceleration 2.21 Économisez des microsecondes.
Qu'est-ce que Project Euler 3 Acceleration?
Projet Euler 7
Projet Euler 47
Projet Euler 31
Projet Euler 38
Projet Euler 17
Projet Euler 26
Projet Euler 8
Projet Euler 23
Projet Euler 22
Projet Euler 19
Projet Euler 50
Projet Euler 42
Projet Euler 33
Projet Euler 32
Projet Euler 43
Projet Euler 35
Projet Euler 36
Projet Euler 24
Projet Euler 46
Projet Euler 48
Projet Euler 45
Projet Euler 6
Projet Euler 44
Projet Euler 39
Projet Euler 40
Projet Euler 49
Projet Euler 29
Projet Euler 27
Projet Euler 41
Projet Euler 18
Projet Euler 13
Projet Euler 30
Projet Euler 16
Projet Euler 14
Projet Euler 34
Projet Euler 25
[Projet Euler] problème1
Projet Euler15 "Chemin du treillis"
Projet Euler Original Method Group 1
[Note] Projet Euler en Python (problème 1-22)
Programmation fonctionnelle dans Python Project Euler 3
Projet Euler # 5 "Minimum Multiple" en Python
Projet Euler 4 Tentative d'accélération
Programmation fonctionnelle dans Python Project Euler 2
Projet Euler 11 "Produit maximum dans la grille"
Projet Euler # 15 "Lattice Path" en Python
Projet Euler # 4 "Calligraphie maximum" en Python
Projet Euler 9 Conservation des résultats des calculs