Timeit¶
De deux fonctions similaires, le module timeit permet de déterminer laquelle est la plus rapide. Souvenez-vous de la fonction factorielle que nous avons écrite précédemment, alors que nous avions remarqué que Python disposait déjà de sa propre fonction factorielle dans le module standard math. Y a-t-il une différence de rapidité entre ces deux fonctions ? Le module timeit va nous aider à en savoir plus. Par exemple, timeit peut nous indiquer la durée d'exécution de chaque fonction :
from math import factorial
%timeit factorial(20)
Le signe pourcentage (%) placé devant l'appel de timeit est un exemple concret de fonction magique IPython, que nous ne traiterons pas ici, une sorte de Mojo que IPython ajoute aux fonctions pour qu'elles s'exécutent mieux dans l'environnement IPython. Pour en savoir plus, consultez le tutoriel IPython.
En tout cas, la fonction timeit évalue l'opération à 1 000 000 de boucles, puis nous informe que le meilleur temps moyen parmi trois mesures est de 478 nanosecondes par boucle – pour calculer \(20!\) tout de même ! En comparaison :
def fact (n):
if n <= 0:
return 1
return n*fact(n-1)
%timeit fact(20)
La fonction factorielle que nous avons écrite est presque 8 fois plus lente. Cela est essentiellement dû au fait que la fonction factorielle standard est écrite en C, puis appelée depuis Python, alors que notre version est entièrement écrite en Python. Si Python est particulièrement pratique à utiliser, sa souplesse et son ergonomie ont toutefois un coût en temps machine. En comparaison, le code C est plus rude à mettre en œuvre, mais sa compilation en code machine s'avère redoutable. Si vous voulez optimiser votre code sans trop d'effort, écrivez-le avec un langage comme Python, mais déléguez les parties les plus lentes à un langage comme C, puis appelez ces fonctionnalités C depuis Python. Nous aborderons quelques techniques en ce sens dans cette rubrique.
Profilage¶
Le profilage de code vient en complément de timeit en décortiquant le temps d'exécution de diverses instructions à l'intérieur de la procédure mesurée.
Supposons que nous voulions créer une liste d'entiers pairs. Notre première tentative donne ceci :
def evens(n):
"Return a list of even numbers below n"
l = []
for x in range(n):
if x % 2 == 0:
l.append(x)
return l
Ce code est-il suffisamment rapide ? Analysons-le avec le profileur Python :
import cProfile
cProfile.run('evens(100000)')
Tout cela semble correct, 0,083 secondes n'est pas un délai si énorme ; toutefois, en y regardant de plus près, on s'aperçoit que les appels à append() grèvent environ 20 % du temps total. Pouvons-nous faire mieux ? Essayons avec la technique de liste en compréhension.
def evens2(n):
"Return a list of even numbers below n"
return [x for x in range(n) if x % 2 == 0]
import cProfile
cProfile.run('evens2(100000)')
En remplaçant notre code par une liste en compréhension, nous avons augmenté la vitesse d'exécution.
Toutefois, il semble que la fonction range() prenne encore beaucoup de temps. Peut-on s'en passer ? Oui, en utilisant le générateur xrange() :
def evens3(n):
"Return a list of even numbers below n"
return [x for x in xrange(n) if x % 2 == 0]
import cProfile
cProfile.run('evens3(100000)')
C'est là que le profilage s'avère utile. Notre code a été amélioré d'un facteur 3 avec juste quelques modifications triviales. Nous n'aurions jamais songé à faire ces modifications si nous n'avions pas un outil de profilage aussi efficace. Imaginez un instant ce que vous pourriez faire avec des programmes plus sophistiqués.
Autres méthodes d'optimisation¶
Lorsque nous avons comparé nos fonctions factorielles ci-dessus, nous avons remarqué que les fonctionnalités écrites en C sont souvent plus rapides, car mieux optimisées. Une fois que nous avons identifié un goulet d'étranglement dans un programme, nous pouvons le remplacer par une version plus rapide écrite en C. On parle alors d'extension de Python. Vous trouverez une documentation intéressante à ce sujet. Cette façon de faire peut vite devenir fastidieuse, surtout si vous avez de nombreuses fonctionnalités à réécrire en C. Heureusement, il existe d'autres options.
Le logiciel SWIG (Simplified Wrapper and Interface Generator) permet de générer des interfaces avec non seulement Python, mais aussi Matlab™, Perl, Ruby et plein d'autres langages. SWIG peut analyser les en-têtes C d'un projet donné, puis générer les dépendances Python qui lui serviront d'interface. Utiliser SWIG s'avère substantiellement plus simple que d'écrire les fonctionnalités en C.
Le projet Cython comprend – entre autres – un langage d'extension de Python similaire au C. On peut, par exemple commencer par écrire une fonction en Python, puis la compiler sous forme de librairie partagée (DLL, SO) qui peut ensuite être exploitée par des versions plus rapides des fonctionnalités. On peut ensuite ajouter des typages de données statiques plus quelques restrictions pour optimiser davantage le code. Cython est généralement plus facile à mettre en œuvre que SWIG.
Pour finir, PyPy est sans doute le moyen le plus facile d'obtenir du code rapide. PyPy compile du Python en un sous-ensemble du langage appelé RPython, qui peut être compilé et optimisé efficacement. D'après certains tests, PyPy peut être jusqu'à 6 fois plus rapide que le Python standard.
Jeu : trouver des nombres premiers¶
Le site Projet Euler propose des énigmes de programmation qui auraient sans doute intéressé Euler. Le problème n°7 pose la question suivante :
Sachant que le 6ème nombre premier de la liste 2, 3, 5, 7, 11, 13, … est 13, quel est le dix-mille-unième (10001e) nombre premier ?
Pour résoudre ce problème, nous avons besoin d'une très longue liste de nombres premiers. Pour commencer, nous allons écrire une fonction basée sur le crible d'Ératosthène pour générer tous les nombres premiers inférieurs à n :
def primes(n):
"""\
From python cookbook, returns a list of prime numbers from 2 to < n
>>> primes(2)
[2]
>>> primes(10)
[2, 3, 5, 7]
"""
if n==2: return [2]
elif n<2: return []
s=range(3,n+1,2)
mroot = n ** 0.5
half=(n+1)/2-1
i=0
m=3
while m <= mroot:
if s[i]:
j=(m*m-3)/2
s[j]=0
while j<half:
s[j]=0
j+=m
i=i+1
m=2*i+3
return [2]+[x for x in s if x]
number_to_try = 1000000
list_of_primes = primes(number_to_try)
print list_of_primes[10001]
Vous pourriez penser que Python n'est pas un choix idoine pour un tel calcul, mais même en termes de temps d'exécution, il n'a vraiment pas fallu attendre très longtemps :
cProfile.run('primes(1000000)')
Moins d'1/3 de seconde pour générer la liste de tous les nombres premiers inférieurs à un million (1 000 000). Ce serait sympa de pouvoir remplacer la fonction range() par xrange() comme précédemment, mais dans le cas ici présent, nous avons réellement besoin d'une liste et non d'un compteur.
