100 fois plus de données : quel coût pour les algorithmes de tri ?

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Aujourd'hui, on fait une exploration approfondie d'un article super intéressant qui s'appelle « Trier, pas si simple ».

Intervenant 20:09

Oui, c'est un très beau sujet. Parce que le tri, on a l'impression que c'est évident.

Intervenant 10:13

Bah oui, imaginez devoir trier tout le linge d'une ville entière, ranger ses propres chaussettes après une lessive. Bon, ça prend deux minutes. On repère la plus petite, on la met au début et puis voilà, c'est réglé.

Intervenant 20:23

C'est ça. Mais des millions de vêtements empilés sur une place publique.

Intervenant 10:27

Ouais, par où on commence en fait ? Donc bon, décortiquons tout ça. On va essayer de comprendre la mécanique invisible et la rigueur mathématique qui s'activent en coulisses chaque fois qu'on ordonne des données, que ce soit des nombres, des listes de clients ou un dictionnaire.

Intervenant 20:40

Et la méthode qu'on choisit pour attaquer cette montagne de données, ça change absolument tout. En informatique, pour mesurer l'efficacité d'un algorithme de tri, on utilise un concept, c'est la complexité temporelle. Ok,

Intervenant 10:52

donc on mesure le temps avec un chrono ?

Intervenant 20:55

En seconde ? Ah non, pas du tout. On ne compte pas en seconde parce que ça, ça dépendrait de la puissance de votre ordinateur. On compte en nombre d'opérations mathématiques. On regarde comment ce nombre explose quand la quantité de données, qu'on appelle souvent la lettre N, augmente.

Intervenant 11:10

D'accord. Donc si N, c'est ma montagne de linge, on essaie de prédire la charge de travail si la montagne devient, je ne sais pas, 100 fois plus grosse.

Intervenant 21:20

Exactement. Et l'outil mathématique pour modéliser ça, c'est la notation de Landau. C'est souvent exprimé avec un grand O.

Intervenant 11:27

Ah oui, le fameux grand

Intervenant 21:28

O. Voilà. Prenons un algorithme de base. On dit que sa complexité est en grand taux de n². Ça veut dire que si on multiplie la quantité de données par 100, le temps de calcul, lui, il n'est pas multiplié par 100, il est multiplié par 100².

Intervenant 11:45

Attends, 100 au carré, ça fait 10 000.

Intervenant 21:48

C'est ça, 10 000.

Intervenant 11:49

Ah ouais. Donc passer de quelques secondes à plusieurs heures, juste parce qu'on a ajouté des données, c'est...

Intervenant 21:56

C'est énorme. On comprend vite qu'il faut de meilleures stratégies pour les bases de données mondiales. D'où l'importance de ce que l'article appelle un algorithme en grand taux de N log N.