Algorithme ou plusieurs façons de résoudre un problème 🇫🇷¶
Pour savoir pourquoi j’écris ces tutos, voir ici.
Tout comme la série sur les mathématiques, cette série de tutoriels se veut une introduction aux algorithmes et aux structures de données. Elle vise les étudiants en sciences humaines et sociales mais pas seulement car je pense que l’apprentissage par les exemples peut être bénéfique à tous ceux qui aiment coder et une approche top-down.
Un exemple simpliste¶
Considérons d’abord un exemple simple conçu à des fins d’illustration.
Un jour, vous avez besoin d’une fonction filtrant tous les nombres pairs plus petits que \(n\).
Maintenant, quelqu’un vous propose deux options (algorithmes). Naturellement, chaque option (algorithme) comprend un ensemble d’étapes.
[51]:
%%time
temp_l = []
def print_evens_fast(n):
i = 0
while i < n:
if i % 2 == 0:
temp_l.append(i)
i += 2
print_evens_fast(50)
CPU times: user 24 µs, sys: 0 ns, total: 24 µs
Wall time: 27.9 µs
[52]:
%%time
temp_l = []
def print_evens_slow(n):
i = 0
while i < n:
if i % 2 == 0:
temp_l.append(i)
i += 1
print_evens_slow(50)
CPU times: user 27 µs, sys: 1 µs, total: 28 µs
Wall time: 30 µs
Quel temps faut-il faire¶
Dans la sortie ci-dessus, vous devriez surtout vous focaliser sur le wall time. En gros, wall time, aussi appelé real, représente le temps réel écoulé, alors que les valeurs user et sys représentent le temps d’exécution du CPU. Pour plus de détails cliquez ici.
Il ne suffit pas d’un loop¶
Comme vous le voyez, l’exécution de print_evens_fast est légèrement plus rapide que la seconde. Cependant, la différence semble insignifiante. Si vous avez l’esprit critique, vous objecterez, à juste titre, qu’un seul essai est tout à fait sujet au hasard.
Une astuce pratique serait d’utiliser la commande magique timeit%% dans Ipython. Dans ce cas, je vais utiliser r1 n100, ce qui signifie 1 essai de 100 boucles.
[54]:
%%timeit -r1 -n100
temp_l = []
def print_evens_fast(n):
i = 0
while i < n:
if i % 2 == 0:
temp_l.append(i)
i += 2
print_evens_fast(50)
4.07 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 100 loops each)
[55]:
%%timeit -r1 -n100
temp_l = []
def print_evens_slow(n):
i = 0
while i < n:
if i % 2 == 0:
temp_l.append(i)
i += 1
print_evens_slow(50)
6.65 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 100 loops each)
La même conclusion s’impose.
L’un des principaux inconvénients du présent exemple est son aspect artificiel et les avantages insignifiants du choix d’un algorithme légèrement plus rapide.
Vous pourriez vous demander si de telles “astuces” sont vraiment utiles/nécessaires dans des scénarios de la vie réelle ?
Un exemple de la vie réelle¶
Prenons un autre exemple, cette fois-ci beaucoup plus pratique.
Les sites web utilisent souvent des ID pour gérer les clients. Chaque jour, certains ID sont utilisés et d’autres sont libérés. Lorsqu’un client tente d’acquérir un nouvel ID, nous voulons toujours lui attribuer le plus petit disponible.
Alors comment trouver le plus petit ID libre, en l’occurrence 10, dans la liste suivante ?
[18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6]
L’approche la plus intuitive serait une recherche par force brute.
Cependant, cet algorithme ne convient pas lorsque la base de données est grande. Par exemple, essayons une liste de 50000 ids.
[80]:
%%time
def brute_force(lst):
i = 0
while True:
if i not in lst:
print(f"The user can use the free id {i}")
break
i = i + 1
import random
# reproductibility
random.seed(0)
nb_ids = 50000
lst = list(range(nb_ids))
lst_shuffled = random.sample(lst, len(lst))
print(f"the first 6 ids of the shuffled list is {lst_shuffled[:6]}")
nb_removed = random.randrange(nb_ids)
lst_shuffled.pop(nb_removed)
brute_force(lst_shuffled)
the first 6 ids of the shuffled list is [25247, 49673, 27562, 2653, 16968, 33506]
The user can use the free id 34838
CPU times: user 9.42 s, sys: 10.2 ms, total: 9.43 s
Wall time: 9.44 s
9,44 s, c’est beaucoup de temps. Si un utilisateur doit attendre 9,44 s avant de se voir attribuer un ID. Il y a de fortes chances pour qu’il soit parti depuis longtemps avant que le processus ne soit terminé.
Maintenant si nous utilisons un autre algorithme basé sur le fait que :
Pour une série de n nombres \(x_1, x_2, ..., x_n\), certains des \(x_i\) doivent être en dehors de l’intervalle [0, n) s’il existe des nombres libres, sinon la liste est exactement une permutation de \(0, 1, ..., n-1\) et \(n\) doit être renvoyé comme le nombre libre minimum.
Traduisons le théorème ci-dessus en python：
[87]:
%%time
def min_free(lst):
n = len(lst)
a = [0]*(n+1)
for x in lst:
if x < n:
a[x] = 1
print(f'The id {a.index(0)} can be used.')
min_free(lst_shuffled)
The id 34838 can be used.
CPU times: user 4.44 ms, sys: 203 µs, total: 4.64 ms
Wall time: 4.51 ms
Comme vous pouvez le constater, la version min_free renvoie le même identifiant, mais ne prend que 4,51 ms. Notez que, étant donné l’énorme écart, nous pouvons nous épargner l’exécution de plusieurs boucles.
Quantifier la vitesse et l’espace de mémoire (complexité en espace)¶
Il reste un problème mineur. N’est-il pas fastidieux d’exécuter le programme à chaque fois ou même plusieurs fois pour avoir une idée de la vitesse ? En outre, les performances peuvent différer de manière assez significative en fonction de la configuration de l’ordinateur.
Heureusement, On a trouvé une façon plus facile et plus objective de quantifier le temps, appelée notation Big O (en fait, elle quantifie la complexité en temps d’un algorithme).
Pour ce cas particulier, la complexité en temps de l’algorithme de force brute est de \(O(n^2)\) et celle de l’autre algorithme de \(O(n)\).
Cependant la plus rapide utilise plus de mémoire (considérez la liste a mise de côté pour enregistrer l’état des nombres), nous disons que la complexité en temps est \(O(n)\).