De nombreuses tâches de programmation peuvent se faire de plusieurs façons, mais l'une de ces façons peut être plus rapide qu'une autre. Concevoir des programmes rapides fait partie de l'art et de la science de la programmation informatique. Nous regardons quelques exemples dans cet exercice.
Partie 1: Ne pas recalculer la même chose deux fois
La suite de Fibonacci est une séquence simple et fascinante de nombres. Vous commencez avec deux nombres, 1 et 1. Ensuite, la règle est : pour obtenir le nombre suivant, ajouter les deux précédents. Par conséquent, le prochain nombre est 1 + 1 = 2. Cela donne les trois premiers termes,
1, 1, 2
et le quatrième terme est 1 + 2 = 3, alors nous avons 2 + 3 = 5, et ainsi de suite:
1, 1, 2, 3, 5, 8, 13, ...
La suite de Fibonacci a été inventée pour parler de populations de lapins, et elle a aussi été reliée à l'architecture des plantes. Voici un extrait d'une série vidéo (en anglais) impressionnante sur les nombres de Fibonacci:
La définition des nombres de Fibonacci se prête naturellement à une fonction récursive. Le prochain exercice définit une fonction Fibonacci(n) pour donner le nième terme dans la liste ci-dessus (à partir de n = 1).
Cependant, cette fonction récursive devient trop lente pour calculer les termes suivants de la suite. Appuyez sur Entrez instructions de test et taper print(Fibonacci(80)). Lorsque vous testez, vous obtenez "Time Limit Exceeded" (délai maximal dépassé).
Pourquoi est-ce que ça va si lentement? La fonction n'a ni instruction complexe, ni boucle, juste une addition. Mais la lenteur s'avère être liée au nombre d'appels totaux pour la fonction. Si nous appelons Fibonacci(3), la fonction récursive est appelée trois fois au total: l'appel initial, puis deux appels récursifs. Si nous appelons Fibonacci(4), la fonction récursive est appelée à cinq reprises: l'appel initial, les trois fois dont nous venons de parler pour n = 3, et un appel récursif de plus pour n = 2. Calculer Fibonacci(5) génère un total de neuf appels, et Fibonacci(6) génère un total de 9 + 5 + 1 = 15 appels. Le nombre d'appels devient vite très grand quand n grandit!
En première approximation, Fibonacci(n+2) nécessite au moins deux fois plus d'appels que tous les appels récursifs de Fibonacci(n), puisque Fibonacci(n+2) appelle Fibonacci(n) une fois directement et indirectement par l'intermédiaire de l'appel récursif à Fibonacci(n+1). De sorte que le temps de calcul est proportionnel à une fonction exponentielle au moins aussi grande que (√ 2)n. C'est trop lent! Par exemple, Fibonacci(80) nécessite plus de 240=1099511627776 appels récursifs.
Ce raisonnement met en évidence le problème conceptuel sous-jacent : l'appel à Fibonacci(n) se fait à deux reprises et le recalcul du résultat à partir du début la deuxième fois est un gaspillage. Nous devrions arriver à une approche où l'on ne perd pas de temps à recalculer la même chose encore et encore.
La solution
Essayons de faire quelque chose en Python plus semblable à l'introduction. Nous avons commencé par écrire 1, 1. Puis nous avons continué à étendre la séquence en ajoutant les deux derniers éléments. Un tel programme est donné ci-dessous, mais vous devez le déchiffrer.
Il y a encore des possibilités d'amélioration, puisque nous n'avons pas besoin de recalculer la totalité du tableau à chaque nouvel appel, mais la solution est déjà correcte, car elle fonctionne rapidement, même sur les grandes valeurs de n!
Partie 2: Ne calculez pas des choses inutiles, même une seule fois
Notre second exemple concerne la vérification pour un nombre du fait qu'il soit premier, ce qui est important en cryptographie, donc au niveau de la sécurité informatique. Un nombre est premier s'il a uniquement deux diviseurs distincts: 1 et lui-même. Les premiers nombres premiers sont 2, 3, 5, 7, 11, 13, 17, 19, 23. (Par exemple, 21 n'est pas premier car 3 et 7 sont des diviseurs, en plus de 1 et 21.)
Comment peut-on vérifier si un nombre est premier en Python? Nous avons vu plus tôt comment tester la divisibilité :
N % D == 0 # a la valeur True si D est un diviseur de N, et False sinon
Donc, en testant tous les diviseurs possibles, nous arrivons au programme suivant.
Il fonctionne! Mais il est hélas trop lent pour un grand nombre. Tape entrée et taper testePremier(324635459). Il dépasse les limites en temps. Essayez avec quelques valeurs : pour des nombres premiers supérieurs à environ 10000000 le code provoque toujours un dépassement de temps de calcul, car la boucle de vérification de la divisibilité s'exécute seulement environ 10 millions de fois par seconde. Si nous voulons vérifier des nombres plus grand encore, nous aurons besoin d'une idée plus efficace. Mais voyez que le code fonctionne également pour quelques grands nombres comme un billion (1000000000000)!
Avons-nous vraiment besoin de vérifier tous les nombres compris entre 2 et N-1, pour vérifier si N est premier? Indice
L'idée, et un argument
Si vous lisez la suggestion et expérimentez, vous remarquez sans doute que lorsque N n'est pas premier, le programme trouve habituellement un facteur très faible par rapport à N. Par exemple, testePremier(34827948723948723984729834) fonctionne assez rapidement, même si son entrée est gigantesque, puisque trouver le diviseur D = 2 est immédiat.
Peut-être que nous n'avons pas vraiment besoin de vérifier tous les facteurs possibles. Y aurait-il une limite au plus petit nombre de facteurs à vérifier, avant que nous puissions être sûrs que N est un nombre premier ? Heureusement, oui! En fait, on peut dire que si N n'est pas premier, l'un de ses diviseurs est au plus sqrt(N). Pourquoi cela? Eh bien, si N n'est pas premier, alors il a un diviseur A. Avoir un diviseur signifie qu'il y a un autre nombre B tel que :
A * B == N
Maintenant, si A ≤sqrt(N) ou B ≤ sqrt(N) , alors nous sommes heureux: nous avons trouvé un facteur de N qui est petit, comme nous le voulions. Mais en réalité, ce sont les seules possibilités. Supposons l'inverse, nous obtenons alors la contradiction :
N = A * B > sqrt(N) * sqrt(N) = N
ce qui est impossible.
Super! Alors maintenant, nous allons mettre en œuvre en Python cette nouvelle idée. La meilleure façon de changer l'ancienne approche est d'ajouter un test dans la boucle for : une fois D > sqrt(N) (ou de manière équivalente D * D > N), nous pouvons simplement sortir de la boucle par un break et interrompre les essais.
Le programme fonctionne maintenant sur les nombres premiers gigantesques!
Exercice final
Dans cet exercice, nous combinons le calcul sur les nombres premiers de la seconde moitié de cette leçon avec l'approche fondée sur une liste de la première moitié. Ici le code doit remplir un tableau de longueur 1000001 afin que estPremier[N] prenne la valeur True si N est un nombre premier, et False sinon, pour tout N jusqu'à un million (estPremier[0] et estPremier[1] doivent être False, par convention).
Cliquez ici pour un indice. C'est un gros!
 | Ceci est le dernier exercice du site Web «Cercles Informatiques». Félicitations à ceux qui ont essayé toutes les leçons! Voir la page de ressources pour avoir des suggestions sur ce qu'il faut apprendre par la suite. Amusez-vous bien, bonne chance, et bon codage ! |
