In [1]:
%pylab inline
Welcome to pylab, a matplotlib-based Python environment [backend: module://IPython.zmq.pylab.backend_inline]. For more information, type 'help(pylab)'.
. . .
x
Calcul des premiers termes des suites u et v
In [2]:
def u(n):
if n==0 : return 1
return u(n-1)+u(n-1)
def v(n):
if n==0 : return 1
return 2*v(n-1)
for i in range(8) :
print '%3d %3d' %(u(i), v(i))
1 1 2 2 4 4 8 8 16 16 32 32 64 64 128 128
. . .
x
Calcul de u(26) et v(26) : affichage du temps
In [3]:
import time
start = time.time()
v(26)
print time.time() - start
0.000134944915771
. . .
In [4]:
start = time.time()
u(26)
print time.time() - start
21.0937569141
. . .
x
Courbes des temps de calculs
In [5]:
def temps(f,L):
tps=[]# contiendra une liste de temps de calcul
for j in L:
start = time.time()
f(j)
dureeCalcul=time.time() - start # dureeCalcul=temps de calcul de f(j)
tps.append(dureeCalcul)
return tps
X=range(10,23)
Yu=temps(u,X)# liste des temps de calcul de u(10), u(11), u(12), ..., u(22)
Yv=temps(v,X)# liste des temps de calcul de v(10), v(11), v(12), ..., v(22)
axis([min(X),max(X),-0.05*(max(Yu)-min(Yu)),max(Yu)])# paramètres d'ouverture pour fenêtre graphique
plot(X,Yu,'r--') # rouge tireté
plot(X,Yv,'b*')# bleu étoilé
show()
. . .
x
Pour comprendre ce qui distingue les deux fonctions
In [6]:
c=[]
c.append("\033[01;31m{0}\033[00m")
c.append('\033[1;36m{0}\033[00m')
c.append('\033[1;32m{0}\033[00m')
c.append('\033[1;34m{0}\033[00m')
c.append('\033[1;46m{0}\033[00m')
c.append('\033[1;32m{0}\033[00m')
c.append('\033[1;33m{0}\033[00m')
c.append('\033[1;34m{0}\033[00m')
c.append('\033[1;35m{0}\033[00m')
c.append('\033[1;38m{0}\033[00m')
c.append('\033[1;41m{0}\033[00m')
c.append('\033[1;43m{0}\033[00m')
nb=len(c)
def uu(n,color=-1):
if n==0 : return 1
else:
print c[color].format('++'*(n**2)+"appel de u({}) (premier terme)".format(n-1))
y=uu(n-1,(color+1)%nb)
print c[color].format('--'*(n**2)+"sortie de u({}) (premier terme)".format(n-1))
print c[color].format('++'*(n**2)+"appel de u({}) (second terme)".format(n-1))
y+=uu(n-1,(color+1)%nb)
print c[color].format('--'*(n**2)+"sortie de u({}) (second terme)".format(n-1))
return y
def vv(n,color=-1):
if n==0 : return 1
else:
color=(color+1)%nb
print c[color].format('++'*(n**2)+"appel de v({})".format(n-1))
y=2*vv(n-1,color)
print c[color].format('--'*(n**2)+"sortie de v({})".format(n-1))
return y
vv(4)
print "\n\n\n\n\n"
uu(4)
++++++++++++++++++++++++++++++++appel de v(3) ++++++++++++++++++appel de v(2) ++++++++appel de v(1) ++appel de v(0) --sortie de v(0) --------sortie de v(1) ------------------sortie de v(2) --------------------------------sortie de v(3) ++++++++++++++++++++++++++++++++appel de u(3) (premier terme) ++++++++++++++++++appel de u(2) (premier terme) ++++++++appel de u(1) (premier terme) ++appel de u(0) (premier terme) --sortie de u(0) (premier terme) ++appel de u(0) (second terme) --sortie de u(0) (second terme) --------sortie de u(1) (premier terme) ++++++++appel de u(1) (second terme) ++appel de u(0) (premier terme) --sortie de u(0) (premier terme) ++appel de u(0) (second terme) --sortie de u(0) (second terme) --------sortie de u(1) (second terme) ------------------sortie de u(2) (premier terme) ++++++++++++++++++appel de u(2) (second terme) ++++++++appel de u(1) (premier terme) ++appel de u(0) (premier terme) --sortie de u(0) (premier terme) ++appel de u(0) (second terme) --sortie de u(0) (second terme) --------sortie de u(1) (premier terme) ++++++++appel de u(1) (second terme) ++appel de u(0) (premier terme) --sortie de u(0) (premier terme) ++appel de u(0) (second terme) --sortie de u(0) (second terme) --------sortie de u(1) (second terme) ------------------sortie de u(2) (second terme) --------------------------------sortie de u(3) (premier terme) ++++++++++++++++++++++++++++++++appel de u(3) (second terme) ++++++++++++++++++appel de u(2) (premier terme) ++++++++appel de u(1) (premier terme) ++appel de u(0) (premier terme) --sortie de u(0) (premier terme) ++appel de u(0) (second terme) --sortie de u(0) (second terme) --------sortie de u(1) (premier terme) ++++++++appel de u(1) (second terme) ++appel de u(0) (premier terme) --sortie de u(0) (premier terme) ++appel de u(0) (second terme) --sortie de u(0) (second terme) --------sortie de u(1) (second terme) ------------------sortie de u(2) (premier terme) ++++++++++++++++++appel de u(2) (second terme) ++++++++appel de u(1) (premier terme) ++appel de u(0) (premier terme) --sortie de u(0) (premier terme) ++appel de u(0) (second terme) --sortie de u(0) (second terme) --------sortie de u(1) (premier terme) ++++++++appel de u(1) (second terme) ++appel de u(0) (premier terme) --sortie de u(0) (premier terme) ++appel de u(0) (second terme) --sortie de u(0) (second terme) --------sortie de u(1) (second terme) ------------------sortie de u(2) (second terme) --------------------------------sortie de u(3) (second terme)
Out[6]:
16
. . .
x
Courbes des nombres d'opérations
In [7]:
def opu(n):
if n==0 : return 0
return 1+2*opu(n-1)
def opv(n):
if n==0 : return 0
return 1+opv(n-1)
for i in range(10) :
print '%3d %3d' %(opu(i), opv(i))
0 0 1 1 3 2 7 3 15 4 31 5 63 6 127 7 255 8 511 9
. . .
In [8]:
X=range(10,23)
Yopu=[opu(x) for x in X]
Yopv=[opv(x) for x in X]
axis([min(X),max(X),-0.05*(max(Yopu)-min(Yopu)),max(Yopu)])# paramètres d'ouverture pour fenêtre graphique
plot(X,Yopu,'r--',X,Yopv,'b*')
show()
. . .
x
Décompte des opérations par la machine
In [16]:
def NbOpU(n):
l=[0]
def u(n):
if n==0 :
return 1
else :
y=u(n-1)+u(n-1)
l[0]+=1
return y
u(n)
return l[0]
def NbOpV(n):
l=[0]
def v(n):
if n==0 :
return 1
else :
y=2*v(n-1)
l[0]+=1
return y
v(n)
return l[0]
. . .
In [17]:
print NbOpU(4)
print NbOpV(4)
15 4
. . .
x
Estimation du temps de calcul de u(27) à partir de celui de u(22).
x
Temps de calcul de u(22)
In [9]:
start = time.time()
u(22)
tempsu22=time.time() - start
print tempsu22
1.23486089706
. . .
x
Estimation d'un temps pour u(27)
In [10]:
tempsu22*2**5
Out[10]:
39.51554870605469
. . .
x
Mesure expérimentale du temps pour le calcul de u(27)
In [11]:
start = time.time()
u(27)
tempsu27=time.time() - start
print tempsu27
42.5974290371
. . .
x
Temps linéaire pour la suite v
x
vraiment linéaire ?
In [12]:
X=range(10,22)
Y=temps(v,X)
plot(X,Y,'b*')
show()
. . .
x
plus convaincant
In [13]:
import timeit
def tempsAvecCalculsRepetes(L):
tps=[]# contiendra une liste de temps de calcul
for j in L:
timeit.timeit(number=100000000)
t = timeit.Timer(stmt="v(%d)"%j, setup="from __main__ import v")
tps.append(t.timeit() )
return tps
X=range(10,22)
Y=tempsAvecCalculsRepetes(X)
plot(X,Y,'b*')
show()
. . .
In [13]:
. . .