Structure de données
Un autre élément qui peut impacter les performances d'un programme, ce sont les structures de données utilisées. Il est très important de choisir, voire de développer, la bonne structure de données pour le problème à résoudre. Il est également important de connaitre les possibilités offertes par le langage de programmation.
Python implémente plusieurs structures de données nativement, dont les chaines de caractères, les listes, les tuples, les ensembles et les dictionnaires avec des opérations spécifiques associées. D'autres sont également disponibles dans le module collections de la librairie standard.
Structure native
Supposons, par exemple, que l'on souhaite trouver les éléments qui sont communs à deux listes de nombres. L'approche la plus directe consiste à parcourir une des listes et de vérifier, pour chacun de ses éléments, s'il se trouve également dans l'autre liste. On pourrait, par exemple, écrire la fonction suivante :
Une autre manière de procéder consiste à utiliser le type set, qui représente des ensembles, et l'opérateur & qui permet de calculer l'intersection de deux ensembles, car c'est exactement ce que l'on cherche (en supposant que s'il y a des doublons dans les listes, cela ne nous intéresse pas de les avoir dans le résultat). On peut alors plutôt écrire la fonction suivante :
La seconde fonction est un peu plus rapide que la première. En effet, on passe de 27 ms à 18 ms pour calculer l'intersection de deux listes de cent-mille éléments, soit une diminution de temps de 33 %. En effet, l'opérateur & est optimisé pour le calcul de l'intersection d'ensembles.
Module collections
Le module collections contient des structures de données spécialisées à utiliser comme alternatives aux structures de données natives. Par exemple, on peut utiliser des deque (double-ended queue), des files à deux bouts, lorsque l'on veut une séquence avec la possibilité d'ajouter et de retirer des éléments devant et derrière. Utiliser cette structure de données sera beaucoup plus rapide que d'utiliser une listet les méthodes insert et append.
Voici deux fonctions qui permettent d'ajouter les éléments d'une liste de données devant ou derrière selon qu'ils sont négatifs ou positifs :
La seconde fonction est beaucoup plus rapide que la première. En effet, on passe de 742 ms à 15 ms pour traiter une liste de cent-mille éléments, soit une diminution de temps de 98 %.