Performances code

Bonjour,

j’ai un code qui fonctionne plutôt bien pour résoudre un problème sur des nombres entier à chiffres croissants (ex 12557 mais pas 12657) , pour ce problème j’ai créé un générateur crois2, comme je le ne trouvais pas très beau j’en ais fait une nouvelle version crois qui me paraissait meilleure, et j’ai eu une surprise :

 In [19]: %timeit for i in crois(5_000_000): pass                                                                                               
4.79 ms ± 6.71 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [20]: %timeit for i in crois2(5_000_000): pass                                                                                              
12.1 ms ± 122 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [17]: %timeit pb74(5_000_000, crois)                                                                                                        
315 ms ± 810 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [18]: %timeit pb74(5_000_000, crois2)                                                                                                       
155 ms ± 127 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Donc le générateur crois est 2.5 fois plus rapide que crois2, mais quand je les appelle dans ma fonction pb74 celle est 2 fois plus rapide avec crois2 qu’avec crois, on voit bien que le temps passé par les générateurs est dans tous les cas très petit face à la fonction principale, mais le résultat me semble étrange, auriez une idée sur ce qui provoque cela ?

from math import factorial

fact = {n:factorial(n) for n in range(10)}

#Premier générateur en 2 fonctions utilisant des listes    
def nxc(lst):
   lst.append(0)
   lst[0] += 1
   i = 0
   while lst[i] == 10:
       i += 1
       lst[i] += 1
   if i != len(lst)-1: lst.pop()
   v = lst[i]
   for j in range(i): lst[j] = v
   return lst

def crois2(n):
   val, num = [0],0
   while num < n:
       val = nxc(val)
       num = int(''.join(map(str, val)))       
       yield num
       

#2eme générateur n'utlisant que des entiers.    
def crois(lim,start=0):
   n, i = start, 0
   while n < lim:
       yield n
       n = n +1
       r = n%10
       while r==0: (n, r), i = divmod(n, 10), i + 1
       while i: n, i = n * 10 + r, i - 1
   
#Fonctions principales    
def chaine(n):
   def suiv(i):
       s = 0
       while i:
           i, r = divmod(i,10)
           s += fact[r]
       return s
   val, ch = suiv(n), {n}
   while val not in ch:
       ch.add(val)
       val = suiv(val)
   return len(ch)
   
def pb74(n=200, gen=crois):
   lval, lch = 0 ,0
   for i in gen(n):
       ls = chaine(i)
       if ls > lch:
           #print(i, ls)
           lval, lch = i, ls
   return lval, lch
  

Si @entwanne a raison et que crois2 ne génére que 56 valeurs et crois en génère 100 pour un même n c’est normal que quand tu utilises crois2 avec pb74 ça soit plus rapide.
Ensuite en ignorant le premier point , il est possible que python puisse optimiser , et qu’il arrive pour une raison ou une autre (par exemple à cause de la position de ton yield dans ta boucle while ) qu’il arrive à optimiser ton générateur créé avec crois2 mais pas celui créé avec la fonction crois .Après je ne suis pas un expert et je connais pas les optimisations que python peut faire c’est juste une intuition .

Merci entwanne, je viens de me rendre compte que je comparais les temps avec une mauvaise version de crois2, le fait de commencer à 1 ou 0 ne change pas le résultat de pb74, mais la ligne 22 de nxc devient num = int(''.join(map(str, val[::-1]))), maintenant si je compare les temps j’obtient des résultats plus logiques: (j’ai à chaque fois ≅20ms d’écart en faveur de crois entre boucles seules ou entre les 2 appels de pb74)

%timeit for i in crois(5_000_000): pass
5.09 ms ± 69.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit for i in crois2(5_000_000): pass
24.5 ms ± 259 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)


%timeit pb74(5_000_000, crois)
348 ms ± 9.21 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit pb74(5_000_000, crois2)
371 ms ± 3.95 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Morale: faire attention quand on copie/colle l’historique d’une console Ipython pour reprendre du code.