XXVII. Exemples▲
XXVII-1. Suite n-bonacci▲
La suite N‑bonacci est une construction mathématique basée sur la suite de Fibonacci mais avec un nombre N d’éléments de départ ; et où chaque terme sera alors la somme des N termes qui le précèdent.
Par exemple la suite 4‑bonacci partira de 4 chiffres (ex U0=1, U1=1, U2=1, U3=1) et chaque terme suivant sera alors la somme des 4 termes précédents (U4=4, U5=7, U6=13, etc).
Si on prend la suite N‑bonacci, comme référence, alors la suite de Fibonacci est simplement une suite N‑bonacci de rang 2 (une 2‑bonacci).
Petit exemple d’une suite de N‑bonacci où la base de départ est donnée par l’appelant.
XXVII-1-a. En récursif▲
XXVII-1-b. En itératif▲
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
#!/usr/bin/env python3
# coding: utf-8
def n_bonacci(base, n=0):
if n < len(base): return base[n]
for i in range(n - len(base) + 1):
base=base[1:] + (sum(base),)
return base[-1]
# n_bonacci()
if __name__ == "__main__":
for i in range(11):
print(i, n_bonacci((1, 2, 3, 4), i))
# if
XXVII-1-c. Avec une pile▲
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
#!/usr/bin/env python3
# coding: utf-8
def n_bonacci(base, n=0):
res=0
pile=[n,]
while pile:
v=pile.pop()
if v >= len(base):
pile.extend(range(v-1, v-len(base)-1, -1))
else:
res+=base[v]
# while
return res
# n_bonacci()
if __name__ == "__main__":
for i in range(11):
print(i, n_bonacci((1, 2, 3, 4), i))
# if
XXVII-1-d. Sous forme de générateur▲
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
#!/usr/bin/env python3
# coding: utf-8
def n_bonacci(base, n=0):
for i in range(n):
if i < len(base):
yield base[i]
continue
# if
base=base[1:] + (sum(base),)
yield base[-1]
# for
# n_bonacci()
if __name__ == "__main__":
for (i, f) in enumerate(n_bonacci((1, 2, 3, 4), 11)):
print(i, f)
# if
XXVII-2. Tracer le scope local▲
Création d’un objet spécifique avec affichage dans les méthodes __init__() et __del__() pour montrer le mécanisme de création et suppression automatique des variables locales dans une fonction.
2.
3.
4.
5.
6.
# class cTrace()
def __init__(self, n):
print("init:", n)
self.__n=n
def __del__(self): print("del:", self.__n)
# class cTrace
XXVII-2-a. Quand l’objet est stocké dans une variable de la fonction▲
2.
3.
4.
5.
6.
7.
8.
def fct(n):
print("in fct:", n)
var=cTrace(n)
print("out fct:", n)
print(1) # Message témoin
fct("xxx") # Appel de la fonction
print(2) # Message témoin
Résultat :
2.
3.
4.
5.
6.
1
in fct: xxx
init: xxx
out fct: xxx
del: xxx
2
Explications : le premier message « in fct » montre la fonction qui démarre avec son paramètre reçu. Ensuite, elle instancie un objet cTrace qui est récupéré par la variable var. Le message « init » est donc affiché à l'instanciation de l'objet. Puis la fonction se termine et affiche le message « out fct » avant de sortir. Lors de cette sortie, ses variables internes sont alors toutes supprimées ce qui détruit l'objet par ricochet et le message « del » de l'objet est alors affiché à sa destruction. Et tout ceci se passe entre les deux messages témoins.
XXVII-2-b. Quand l’objet est créé à la volée sans être récupéré par une variable▲
2.
3.
4.
5.
6.
7.
8.
def fct(n):
print("in fct:", n)
cTrace(n)
print("out fct:", n)
print(1) # Message témoin
fct("xxx") # Appel de la fonction
print(2) # Message témoin
Résultat :
2.
3.
4.
5.
6.
1
in fct: xxx
init: xxx
del: xxx
out fct: xxx
2
Explications : la différence se fait ici lors de l'instanciation de l'objet. Cette instance n'étant pas récupérée dans une variable, l'objet est alors immédiatement détruit juste après avoir été créé et ce, avant que la fonction ne se termine.
XXVII-3. Tracer le fonctionnement des paramètres par défaut▲
Création d’un objet spécifique avec affichage dans les méthodes __init__() et __del__() pour montrer le mécanisme de création des valeurs par défaut des paramètres d’une fonction.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
#!/usr/bin/env python3
# coding: utf-8
class cTrace:
def __init__(self): print("init: ", self)
def __del__(self): print("del: ", self)
# class cTrace
# Première définition de fonction avec un paramètre ayant l’objet comme valeur par défaut
def fct(n=cTrace()): print("fct:", n)
# Seconde définition de fonction qui va écraser la première
def fct(n=cTrace()): print("fct:", n)
print(1) # Message témoin
fct("essai") # Appel avec argument concret (donc pas d’argument par défaut)
print(2) # Message témoin
fct() # Appel avec argument par défaut
print(3) # Message témoin
… et au résultat :
Explications : le premier message « init » provient de l’objet cTrace() créé lorsque la fonction est définie. On a déjà là la démonstration que l’argument par défaut est créé à la définition de la fonction et non à son appel. Ensuite, le second message « init » provient d’un second objet cTrace() créé lorsque la fonction est de nouveau définie. À ce moment‑là, la première fonction disparait et avec elle les objets qu’elle a créés, d’où le premier message « del ». Viennent ensuite, le message témoin « 1 » puis le message en provenance de la fonction, laquelle affiche le paramètre reçu. Puis s’affichent le second message témoin « 2 » puis de nouveau le message en provenance de la fonction, laquelle affiche cette fois le paramètre par défaut (objet cTrace créé auparavant). Arrive enfin le troisième message témoin « 3 ». Puis le programme s’arrête détruisant alors la fonction fct ce qui détruit par ricochet son argument par défaut.
XXVII-4. Tracer le fonctionnement des fonctions incluses▲
Création d’un objet spécifique avec affichage dans les méthodes __init__() et __del__() pour montrer le mécanisme de création des fonctions incluses mis en œuvre lors de l’appel (et non de l’écriture) de la fonction parente.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
#!/usr/bin/env python3
# coding: utf-8
class cTrace:
def __init__(self): print("init: ", self)
def __del__(self): print("del: ", self)
# class cTrace
# Définition de la fonction parente
def fct():
# Fonction incluse avec un paramètre ayant l’objet comme valeur par défaut
def xxx(t=cTrace()): pass
print("fct")
# fct()
print(1) # Message témoin
fct() # Appel fonction
print(2) # Message témoin
fct() # Appel fonction
print(3) # Message témoin
…et au résultat :
Explications : affichage tout d’abord du message témoin « 1 » puis d’un premier « init » provenant de l’objet cTrace() créé lorsque l’appel de la fonction fct() ce qui entraine la création de la fonction xxx() (qui, elle, n’a pas besoin d’être appelée). Puis exécution du premier « del » lorsque la fonction xxx() est détruite et avec elle ses objets. Puis affichage du message témoin « 2 » puis appel de nouveau à la fonction fct() entrainant la création de la fonction xxx() et de son objet en tant que paramètre par défaut, puis nouvel appel de la fonction fct() entrainant la destruction de son contenu et donc de xxx() et de ses objets par ricochet puis enfin, affichage du message témoin « 3 ».
XXVII-5. Fonction « cmp_to_key() »▲
Reproduction de la fonction cmp_to_key() du module « functools » permettant de passer une fonction comme critère de tri à sorted().
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
# La fonction test va trier alphabétiquement chaque chaîne inversée ("abc" vu comme "cba")
def compare(x, y):
if x[::-1] < y[::-1]: return -1
if x[::-1] > y[::-1]: return 1
return 0
# La fonction cmp_to_key qui convertit une fonction en clef
# Pour cela, elle crée un objet interne contenant tous les opérateurs relationnels
# Chaque opérateur utilisera la fonction à convertir pour faire ses évaluations
# La fonction cmp_to_key n’a plus alors qu’à renvoyer l’objet
# De là, toute comparaison de deux éléments par sort() passera alors par l’objet
def my_cmp_to_key(fct):
class __cFct:
def __init__(self, k): self.__k=k
def __eq__(self, other): return fct(self.__k, other.__k) == 0
def __ne__(self, other): return fct(self.__k, other.__k) != 0
def __lt__(self, other): return fct(self.__k, other.__k) < 0
def __le__(self, other): return fct(self.__k, other.__k) <= 0
def __gt__(self, other): return fct(self.__k, other.__k) > 0
def __ge__(self, other): return fct(self.__k, other.__k) >= 0
return __cFct
>>> auteurs=("Hugo", "Racine", "Balzac")
>>> for x in sorted(auteurs, key=my_cmp_to_key(compare), reverse=True): print(x)
...
Hugo
Racine
Balzac
>>> from functools import cmp_to_key
>>> for x in sorted(auteurs, key=cmp_to_key(compare), reverse=True): print(x)
...
Hugo
Racine
Balzac
XXVII-6. Petit benchmark sur les différentes façon de copier une liste▲
Il a été vu lors du chapitre sur la copie des objets mutables, qu’une liste pouvait être copiée soit par l’opérateur Python slice ([:]), soit par la création d’une nouvelle liste à travers le mot‑clef list(), soit par la méthode copy() de l’objet liste lui‑même. Y a‑t‑il une différence entre ces trois façon de faire ?
Voici un petit exemple de benchmark des trois méthodes…
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
#!/usr/bin/env python3
# coding: utf-8
import random
import timeit
from functools import partial
# Initialisation random
random.seed()
# Les fonctions à tester
fct={
"slice" : lambda l: l[:],
"copy" : lambda l: l.copy(),
"list" : lambda l: list(l),
}
# Les données à traiter
data=list(range(10_000))
# Le nombre de répétitions (les moyennes se feront sur cette valeur)
repeat=20
# Appel des fonctions dans un ordre aléatoire et affichage du chrono
print("start=%d, repeat=%d" % (len(data), repeat))
for (k, v) in random.sample(fct.items(), len(fct)):
t=timeit.Timer(partial(v, data)).repeat(repeat=repeat, number=500_000)
print("%s: min=%f, max=%f, avg=%f" % (k, min(t), max(t), sum(t)/len(t)))
# for
Et (au bout d’environ 12 minutes) un résultat…
À ce qu’il semble, c’est le cast list() qui serait le plus prometteur…
XXVII-7. Petit benchmark sur le append() face aux listes en compréhension▲
Il a été vu lors du chapitre sur les listes en comprehension, qu’en dehors d’une écriture plus concise, son avantage principal était d’éviter la méthode list.append() présentée comme globalement très consommatrice.
Voici un petit exemple de benchmark permettant de comparer les deux écritures…
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
#!/usr/bin/env python3
# coding: utf-8
import random
import timeit
from functools import partial
# Initialisation random
random.seed()
# La fonction qui crée la liste par append()
def fct_append(l):
res=list()
for x in l: res.append(x)
# fct_append()
# La fonction qui passe par les listes en compréhension
def fct_comprehension(l): return list(x for x in l)
# Les fonctions à tester (on évitera la lambda pour être le plus impartial possible)
fct={
"append" : fct_append,
"comprehension" : fct_comprehension,
}
# Les données à traiter
data=tuple(range(50_000_000))
# Le nombre de répétitions (les moyennes se feront sur cette valeur)
repeat=10
# Appel des fonctions dans un ordre aléatoire et affichage du chrono
print("start=%d, repeat=%d" % (len(data), repeat))
for (k, v) in random.sample(fct.items(), len(fct)):
t=timeit.Timer(partial(v, data)).repeat(repeat=repeat, number=20)
print("%s: min=%f, max=%f, avg=%f" % (k, min(t), max(t), sum(t)/len(t)))
# for
Et (au bout d’environ 10 minutes) un résultat…
Là en revanche, les écarts sont clairs et avérés. Près de 18 % plus rapide avec l’écriture en compréhension (ou près de 22 % plus lent avec la méthode list.append())…
XXVII-8. Benchmark sur le map() face aux listes en compréhension▲
Il a été vu lors du chapitre sur les compléments des tuples, listes, ensembles et dictionnaires, qu’il existait une fonction map() permettant de faire traiter tout un itérable par une fonction, la fonction étant alors appliquée sur chaque élément de l’itérable.
Guido Van Rossum, le concepteur de Python, a dit qu’il n’aimait pas la fonction map(), car on peut facilement la remplacer par une liste en compréhension plus rapide et plus lisible. Et beaucoup de sites sur Internet ont repris ces deux arguments.
Sur la lisibilité d’une liste en compréhension face à la fonction map(), cela reste uniquement une affaire de goûts dont on ne peut pas discuter. En revanche, on peut parfaitement discuter de la rapidité.
Toutefois, n’oublions pas qu’on peut faire traiter l’itérable (on dira « liste » pour simplifier) par une fonction lambda ou bien par une fonction déjà existante. De plus, il ne faut pas oublier que la fonction map() peut traiter plusieurs listes en parallèle…
XXVII-8-a. Liste unique▲
Voici un petit exemple de benchmark permettant de comparer les deux écritures quand on traite une liste unique…
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
#!/usr/bin/env python3
# coding: utf-8
import random
import timeit
from functools import partial
# Initialisation random
random.seed()
# Une fonction somme
def somme(x): return x
# Les données à traiter
data=list(range(10_000))
# Les fonctions à tester
fct={
"with_lambda" : {
"map" : lambda l: list(map(lambda x: x, l)),
"comprehension" : lambda l: [x for x in l],
},
"with function" : {
"map" : lambda l: list(map(somme, l)),
"comprehension" : lambda l: [somme(x) for x in l],
},
}
# Le nombre de répétitions (les moyennes se feront sur cette valeur)
repeat=20
# Appel des groupes
print("start=%d, repeat=%d" % (len(data), repeat))
for (k, v) in fct.items():
# Appel des fonctions du groupe dans un ordre aléatoire et affichage du chrono
for (kk, vv) in random.sample(v.items(), len(v)):
t=timeit.Timer(partial(vv, data)).repeat(repeat=20, number=10_000)
print("%s (%s): min=%f, max=%f, avg=%f" % (kk, k, min(t), max(t), sum(t)/len(t)))
# for
# for
Et (au bout d’environ 4 minutes) un résultat…
XXVII-8-b. Deux listes▲
Voici un petit exemple de benchmark permettant de comparer les deux écritures quand on traite deux listes en parallèle. Mais dans le cas de la compréhension, il faudra associer les listes au travers de la fonction zip()…
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
#!/usr/bin/env python3
# coding: utf-8
import random
import timeit
from functools import partial
# Initialisation random
random.seed()
# Une fonction somme
def somme(x, y): return x+y
# Les données à traiter
data=list(range(10_000))
# Les fonctions à tester
fct={
"with_lambda" : {
"map" : lambda l: list(map(lambda x, y: x+y, l, l)),
"comprehension" : lambda l: [x+y for (x, y) in zip(l, l)],
},
"with function" : {
"map" : lambda l: list(map(somme, l, l)),
"comprehension" : lambda l: [somme(x, y) for (x, y) in zip(l, l)],
},
}
# Le nombre de répétitions (les moyennes se feront sur cette valeur)
repeat=20
# Appel des groupes
print("start=%d, repeat=%d" % (len(data), repeat))
for (k, v) in fct.items():
# Appel des fonctions du groupe dans un ordre aléatoire et affichage du chrono
for (kk, vv) in random.sample(v.items(), len(v)):
t=timeit.Timer(partial(vv, data)).repeat(repeat=20, number=10_000)
print("%s (%s): min=%f, max=%f, avg=%f" % (kk, k, min(t), max(t), sum(t)/len(t)))
# for
# for
Et (au bout d’environ 8 minutes) un résultat…
XXVII-8-c. Trois listes▲
Voici un petit exemple de benchmark permettant de comparer les deux écritures quand on traite trois listes en parallèle (avec bien entendu toujours cette association au travers de la fonction zip())"…
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
#!/usr/bin/env python3
# coding: utf-8
import random
import timeit
from functools import partial
# Initialisation random
random.seed()
# Une fonction somme
def somme(x, y, z): return x+y+z
# Les données à traiter
data=list(range(10_000))
# Les fonctions à tester
fct={
"with_lambda" : {
"map" : lambda l: list(map(lambda x, y, z: x+y+z, l, l, l)),
"comprehension" : lambda l: [x+y+z for (x, y, z) in zip(l, l, l)],
},
"with function" : {
"map" : lambda l: list(map(somme, l, l, l)),
"comprehension" : lambda l: [somme(x, y, z) for (x, y, z) in zip(l, l, l)],
},
}
# Le nombre de répétitions (les moyennes se feront sur cette valeur)
repeat=20
# Appel des groupes
print("start=%d, repeat=%d" % (len(data), repeat))
for (k, v) in fct.items():
# Appel des fonctions du groupe dans un ordre aléatoire et affichage du chrono
for (kk, vv) in random.sample(v.items(), len(v)):
t=timeit.Timer(partial(vv, data)).repeat(repeat=20, number=10_000)
print("%s (%s): min=%f, max=%f, avg=%f" % (kk, k, min(t), max(t), sum(t)/len(t)))
# for
# for
Et (au bout d’environ 12 minutes) un résultat…
XXVII-8-d. Conclusion▲
Il semble que l’utilisation de la fonction map() sera plus rapide d’environ 40 % face à la liste en compréhension quand le traitement se fait via une fonction déjà existante ; en opposition au traitement fait par une lambda dans lequel là la liste en compréhension sera plus rapide d’environ 70 %. Peut‑être (juste une hypothèse) parce que dans la fonction map(), la lambda est redéfinie à chaque itération…
Cependant, quand le traitement s’intensifie pour devoir opérer sur plusieurs listes, l’avantage de la liste en compréhension dans le cadre de la lambda diminue assez drastiquement (il passe à environ 30 % pour deux listes et à environ 20 % pour trois listes) tandis que l’avantage du map() utilisant une fonction déjà existante diminue moins (il passe à environ 30 % pour deux listes et reste à cette valeur pour trois listes). Probablement cette perte drastique de performances dans l’écriture en compréhension est‑elle due à l’introduction de la fonction zip() nécessaire à la jointure des listes.
Toutefois, n’oublions pas aussi l’avantage de la fonction map() en cas de listes de taille inégale. Dans ce cas elle s’adapte automatiquement à la liste la plus longue en complétant les listes plus courtes par autant de None que nécessaire. L’adaptation de ce fonctionnement dans une écriture en compréhension sera plus ardue et nuira certainement à la lisibilité de l’ensemble sans même parler des baisses de performances que cela pourra entraîner.