# Permet de tout executer au lancement du notebook + conserver le notebook actif pendant 2h
from IPython.display import Javascript
from masquer import *
Javascript("""
function repeter(){
IPython.notebook.kernel.execute("a=1");
}
// execute a = 1 en python toutes les 8 minutes pendant 2h
let timerId = setInterval(() => repeter(), 4800);
setTimeout(() => { clearInterval(timerId); alert('fin de cession'); }, 7200000);
// Supprimer la taille limite pour la sortie d'une cellule
IPython.OutputArea.prototype._should_scroll = function(lines) {
return false;
};
IPython.notebook.kernel.execute("url = '" + window.location + "'");
// Exécuter toutes les cellule du notebook
require(
['base/js/namespace', 'jquery'],
function(jupyter, $) {
jupyter.actions.call('jupyter-notebook:run-all-cells-below');
jupyter.actions.call('jupyter-notebook:save-notebook');
Jupyter.actions.call('jupyter-notebook:hide-header')
}
);""")
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
HTML("""<style>
h1 {
font-family: 'Permanent Marker', cursive;
text-align: center;
color: red;
}
ol {
list-style-position: inside;
margin-left: 1em;
list-style-position: outside;
}
h2 {
font-family: 'Permanent Marker', cursive;
color: blue;
}
h3 {
font-family: 'Permanent Marker', cursive;
}
</style>""")
En python par défaut, on ne peut pas réaliser plus de 1000 appels imbriqués sinon on se retrouve avec l'erreur
RecursionError: maximum recursion depth exceeded in comparison
Sous jupyter, cette limite est portée à 3000 par défaut (ce qui permet en réalité d'aller un tout petit peu en dessous).
Ce système est là pour éviter les problèmes de boucle infinie qui peuvent se poser très facilement quand on écrit une fonction récursive et que l'on oublie la condition d'arrêt.
La solution est d'utiliser la fonction setrecursionlimit du module sys Dans la documentation python, on peut lire:
Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python.
The highest possible limit is platform-dependent. A user may need to set the limit higher when they have a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.
On reprend la suite $u_n$ rappelée ci-dessous.
def u(n):
if n == 0:
return 2
else:
x = u(n-1)
return 0.5*(x + 3 / x)
# Question 1.
# Question 2.
La fonction u(n) précédente appelle une seule fois la fonction u(n-1) et ainsi de suite. Le résultat est un appel pour chaque n, avec chaque appel réalisé en temps constant d'où une complexité en O(n) (en gros un temps d'exécution proportionnel à n sur une même machine) comme dans le cas de l'utilisation d'un boucle for pour le calcul.
Si on utilise la fonction u(n) ci-dessous, u(n) appelle deux fois u(n-1) qui appellent chacune deux fois u(n-2) etc... On se retrouve avec $2^n$ appels et donc un temps d'exécution exponentiel! (le temps est proportionnel à $2^n$ et double donc lorsque n augmente de 1. Faison l'expérience:
def u(n):
if n == 0:
return 2
else:
return 0.5*(u(n-1) + 3 / u(n-1))
from time import time
for i in range(25):
t = time()
racinedetrois = u(i)
print(i,time()-t)
0 2.3126602172851562e-05 1 6.4373016357421875e-06 2 5.0067901611328125e-06 3 6.198883056640625e-06 4 9.775161743164062e-06 5 1.9073486328125e-05 6 3.695487976074219e-05 7 7.200241088867188e-05 8 0.00014519691467285156 9 0.0002932548522949219 10 0.0005791187286376953 11 0.0012617111206054688 12 0.0022325515747070312 13 0.0034668445587158203 14 0.006333827972412109 15 0.008409261703491211 16 0.029224634170532227 17 0.03555464744567871 18 0.08672499656677246 19 0.12528204917907715 20 0.2587292194366455 21 0.5444915294647217 22 0.9242415428161621 23 1.5842571258544922 24 3.4333577156066895
De manière générale, une fonction récursive qui s'appelle plus d'une fois donnera une complexité exponentielle, il faudra donc bien y faire attention lors du codage d'un fonction récursive.
La suite de fibonaci est définie par:
$F_0 = 1$
$F_1 = 1$
$F_n = F_{n-1} + F_{n-2}$ $\forall n \in \mathbb{N}, n > 1$
Il est possible de remédier à ce problème de complexité de la fonction récursive en utilisant la mise en cache ou mémoïsation. Il s'agit de stocker dans un tableau la valeur de chaque terme déjà calculé afin d'y accéder rapidement sans le recalculer. Le tableau doit être accessible à tous les niveaux de la pile d'appel.
import sys
sys.setrecursionlimit(10000)
memoire = [1,1]
def F(n):
global memoire
if n < len(memoire):
return memoire[n]
else:
memoire.append(F(n-1) + F(n-2))
return memoire[n]
t = time()
F(5000)
print(time()-t)
6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626
0.00910186767578125
Et l'on peut reprendre les calculs là ou on s'était arrêté car tout est resté en mémoire
t = time()
F(5000)
print(time()-t)
6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626
0.002252817153930664