Que ayez eu un prof à l’ancienne durant vos études, où que vous vous soyez plongé dans des documents traitant d’optimisation, vous êtes peut être un jour tombé sur ces fameuses notations : O(n), O(1), O(log(n)), etc.
Qu’est-ce que cela signifie-t-il donc, alors, hein ?
C’est une manière de décrire l’ordre de grandeur de temps que va prendre un algo pour s’exécuter pour un nombre “n” d’éléments.
Par exemple, si je fais ceci en Python :
elements = [1, 2, 3]
for x in elements:
print(x)
## 1
## 2
## 3Ici, j’ai 3 éléments, donc n = 3. Mon algorithme va tous les utiliser une fois, mais pas plus d’une. Il va donc faire un nombre d’opérations proportionnel au nombres d’éléments. On note ce type de comportement O(n). Cela signifie que le temps de traitement de mon code suit à peu près “n”.
Je dis à peu près car le nombre d’éléments n’est pas uniquement ce qui va rentrer en compte. La taille des éléments, l’état de la machine au moment de l’exécution et tout un tas d’autres paramètres vont être des facteurs. Mais, globalement, je peux donner une évaluation convenable du temps que le code va prendre en notant le temps de traitement d’un seul élément, et en le multipliant par le nombre total d’éléments.
La notation O(truc), que l’on prononce “Oh de truc”, sert juste à indiquer quel type de comportement un algo a : est-ce qu’il prend du temps par rapport au nombre d’éléments ? Si oui à quel point ?
“A quel point” est une question importante, car si mon algo est celui ci:
elements = [1, 2, 3]
for x in elements:
print()
for i in elements:
print(i, end="")
## 123
## 123
## 123Alors, si n est grand, non seulement ma première boucle s’allonge, mais ma seconde boucle s’allonge aussi car j’affiche TOUS les éléments pour CHAQUE élément. Mon temps d’exécution dépend alors de “n” multiplié par lui-même : n X n. En effet, si j’ai 2 éléments, je vais faire 2 x 2 = 4 print(), si j’en ai 3, je vais faire 3 x 3 print(), etc.
Bien sûr, je pourrais faire des choses beaucoup plus compliquées qu’un print(), mais ça n’a pas d’importance. On en mesure pas le temps de tout le programme, seulement l’efficacité d’un algorithme. Ici, cela dépend du nombre d’éléments fois lui-même, soit au carré. On le note O(n²).
Il existe tout un tas de ces notations. Par exemple, 0(1) signifie un temps “constant”, c’est un abus de langage pour dire que le temps que met l’ago à s’effectuer ne dépend pas du nombre d’éléments.
Par exemple :
elements = [1, 2, 3]
print(elements[0])
## 1
Afficher le premier élément prend un temps du même ordre de grandeur – car c’est ça l’important, l’ordre de grandeur – si il y a 1 ou 10000 éléments. On note donc cet algo O(1).
Il y a des cas plus complexes. Imaginez celui-ci :
import random
number = random.randint(0, 100)
print("Choosing: %s" % number)
smallest = 0
biggest = 100
guess = 50
while guess != number:
if number >= guess:
smallest = guess
else:
biggest = guess
guess = (biggest - smallest)//2 + smallest
print("New guess: %s" % guess)
print("Last guess: %s" % guess)
## Choosing: 69
## New guess: 75
## New guess: 62
## New guess: 68
## New guess: 71
## New guess: 69
## Last guess: 69Dans cet exemple, le nombre d’opérations dépend du nombre d’éléments “n” (ici 100) mais on divise l’interval de recherche par deux à chaque tour de boucle. On note cette complexité O(log n), puisque la fonction log illustre bien le concept d’avoir une mi-molle sur la fin de son algo :)
Il y a aussi l’inverse :
elements = [1, 2, 3, 4, 5]
copies = []
for x in elements:
print()
for i in copies:
print(i, end="")
copies.extend(elements)
## 12345
## 1234512345
## 123451234512345
## 12345123451234512345Ici on augment la charge à traiter à chaque tour de boucle, et cette augmentation dépend du nombre d’éléments “n”. On parle d’une augmentation exponentielle de la charge de travail et on le note O(en).
A quoi ça sert ?
Essentiellement à avoir une idée d’où on met les pieds. Si vous lisez une doc, et qu’on vous dis “cet algo met un temps O(log(n))”, vous savez que même sur un grand ensemble de données, le traitement ne sera pas trop agressif. Si plus tard vous rencontrez des problèmes de perf, ce ne sera pas le premier endroit à regarder.
Par contre si vous lisez qu’un algo est O(n!) – là on tape dans les factoriels, c’est énorme – alors au premier ralentissement il faut jeter un coup d’œil sur ce bout de code.
C’est aussi utile pour comparer l’efficacité de deux implémentations.
Imaginez la structure suivante :
class Examen:
"""C'est un exemple pédagogique, ne faites pas ça chez vous les enfants"""
def __init__(self):
self.notes = []
def ajouterNote(self, note):
self.notes.append(note)
def moyenne(self):
total = 0
for note in self.notes:
total += note
return total / len(self.notes)Récupérer la moyenne est une opération O(n). En revanche, si on a :
class Examen:
def __init__(self):
self.notes = []
self.moyenne = None
def ajouterNote(self, note):
if self.moyenne is None:
self.moyenne = note
else:
self.moyenne = (len(self.notes)*self.moyenne + note) / (len(self.notes)+1)
self.notes.append(note)Là, récupérer la moyenne devient une opération O(1), on a déchargé et réparti le calcul sur l’ajout des notes. Selon que l’application va lire souvent la moyenne ou non, l’un ou l’autre algo est préférable, et la notation Big O va donner une idée duquel utiliser si on est face à la doc et pas au code, qui est généralement vachement plus compliqué que ça.
Bon, ok, dans la VVV, aucune de ces deux solutions n’est un problème, on s’en branle. Mais sur des algos plus riches, sur du matos plus limité, ou un jeu de données plus grand, c’est important. Ainsi, la doc de redis donne la notation Big O de toutes les commandes.
En Python, qui est quoi ?
Parcourir un itérable, c’est généralement du O(n), en tout cas pour les listes, les tuples, les dicos, les strings et les sets. Ajouter un élément ou en retirer un, c’est du O(1). Récupérer leurs tailles, c’est du O(1) aussi (elle est mise en cache), donc vous pouvez y aller avec len().
En revanche, l’opérateur in a un temps moyen de O(n) pour les strings, les tuples et les listes (il doit parcourir l’itérable jusqu’à trouver l’élément), et un temps de O(1) pour les sets et les dicos. Ces derniers utilisent des hash, rendant la recherche très très rapide. C’est pour cela qu’on vous dit d’utiliser la bonne structure de données pour le bon usage.
Attention cependant, c’est de l’optimisation de poil de cul, mais c’est pour la culture, O(1) ne veut pas dire “plus rapide que O(n)”. O(1) veut juste dire que le temps est indépendant du nombre d’éléments. Ainsi :
1 in [1, 2, 3] sera beaucoup plus rapide que 1 in [1, 2, 3..., 1000].
Et :
1 in {1, 2, 3} prendra un temps similaire à 1 in {1, 2, 3..., 1000}
Mais :
1 in {1, 2, 3} peut tout à faire être plus lent que 1 in [1, 2, 3]
Par contre, il est presque certain que :
1 in {1, 2, 3..., 1000} est BEAUCOUP plus rapide que 1 in [1, 2, 3..., 1000]
De plus, il y énormément de structures de données dans la stdlib Python, toutes avec des capacités différentes. Heapq assure que votre structure de données est toujours ordonnées pour un coût de O(log n) à l’insertion. Les deques sont très rapides comme FIFO/LIFO (O(1)), mais récupérer une donnée au milieu est une opération O(n). Certaines opérations, comme retirer un élément d’un type list sont étonnamment coûteuses ((O(n) dans le cas du del).
Voici quelques notations de la doc de Python.
La théorie, la pratique, et la mauvaise foi
La notation O est une bonne indication pour faire un choix d’algo ou pour commencer ses recherches de goulot d’étranglement dans un code.
Néanmoins, c’est la performance sur la papier. En pratique, on peut obtenir des résultats un peu différents, voir carrément surprenant. Il peut y avoir de multiples causes :
- L’implémentation ne se comporte pas comme prévu. CPython et Jython n’ont pas les mêmes perfs pour les mêmes choses. Jython n’a pas de GIL.
- Vous avez oublié un paramètre. Un accès disque ou un accès réseau au mauvais endroit, et bam, votre évaluation est à revoir.
- Les données de la vie réelle ont généralement des tendances. Par exemple elles sont souvent un peu triées plutôt que complètement en bordel. C’est pour cette raison que Python utilise Timsort.
- Le matos ne fait pas ce que vous croyez. Les processeurs / cartes graphiques actuels sont devenus incroyablement efficaces à certaines opérations réputées lentes
- Votre machine ne fait pas que faire tourner votre algo. Il y a d’autres processus, avec des conséquences.
Donc si les perfs sont importantes, comme toujours en informatique, on a le dernier mot en mesurant soi-même.
