Bonjour, bienvenue dans cet épisode 8 sur les algorithmes de recherche
et de tri de données, inséparable de cet autre sujet : les structures de données.
Pour moi, une grande partie du travail de codeur (mais pas que de codeurs),
surtout débutant (mais pas que), c’est de rentrer des informations,
puis chercher des informations.
Il y a beaucoup à dire, j’ai écrit de quoi faire deux épisodes, il y
en aura sûrement un troisième dans les mêmes lignes plus tard.
Ranger et chercher
Les deux sont très liés : jeter tous vos livres n’importe où est une
méthode de rangement incroyablement rapide, mais la recherche est
incroyablement inefficace.
Ranger tous vos livres par titre demande du travail, mais revenir chercher
un livre par la suite est très rapide, si on se rappelle du titre bien sûr.
Autre avantage : si vous n’avez pas le livre, vous voyez qu’il manque là
où l’ordre alphabétique l’aurait placé : inutile de le chercher ailleurs,
vous savez que vous ne le possédez pas ou l’avez prêté en ce moment.
L’alternative, sans rangement, aurait été de regarder chacun de vos
livres, et de vous rendre compte tout à la fin que vous ne l’avez pas.
C’est très inefficace et frustrant.
C’est pour cela que chacune des méthodes n’est pas objectivement
meilleure ou moins bonne, mais les papiers scientifiques sur les
structures de données ou algos de tri vont chercher à les évaluer en
terme de meilleur cas, pire cas, et cas moyen.
Explorer le problème
Un léger problème toutefois, une série de plusieurs tomes a rarement des
titres en ordre alphabétique, et vous devrez donc éparpiller la série dans
votre bibliothèque.
Nouveau problème, nouvelle solution.
On tente un truc un peu plus malin : trier par nom d’auteur.
C’est un avantage intéressant dont se servent les librairies et les
bibliothèques : ranger par auteur permet souvent d’avoir des livres
côte à côte qui soient probablement intéressants pour l’acheteur ou le
lecteur, ne serait-ce que par thème proche ou pour ranger une série
ensemble.
Chaque auteur écrit plusieurs livres, enfin on l’espère pour eux. Il
faut donc un autre critère déterminant pour classer entre eux les
livres de l’auteur : alphabétique ou date casserait là aussi des
séries (pour les auteurs qui écrivent plusieurs séries en parallèle),
à vous de voir.
Au pire, on vous force à reparcourir la section des livres d’un auteur
du début à la fin pour savoir si le magasin possède bien tel ou tel
exemplaire. On a perdu le côté immédiat et infaillible de l’ordre
alphabétique pur, mais on a gagné quand même puisqu’on a restreint
cette phase pénible à la section d’un auteur.
Sur les milliers d’ouvrages de la librairie, vous y gagnez :
imaginez la longueur de la section de livres qui commencent par
“Histoire de/des/de la” ou “Méthode de/des/pour” par exemple.
Eh oui : la nature de vos données va donc aussi influer sur le choix
de la structure de données à choisir !
Attention toutefois :
il faudra trouver une astuce quand il y a plusieurs auteurs…
La structure et le besoin
On vient de faire un arbitrage entre la complexité de rangement à
chaque fois qu’on ajoute ou remet un livre dans les étagères, contre
un énorme avantage à la recherche. Si votre problème est rarement
d’ajouter ou ranger des éléments, et plus souvent de rechercher, c’est
un coût qu’il est intéressant de payer.
Mais quand vous faites des logs dans votre application, vous listez
tout ce qui se passe pour, peut-être, y chercher des informations un
jour. On peut alors légitimement choisir l’arbitrage inverse.
Par exemple, les journaux sont un produit radicalement différent d’un
livre : ils contiennent des informations variées d’auteurs variés, et
une bonne partie de ce qu’ils contiennent n’est plus aussi intéressant
au bout d’une semaine, un mois, deux ans… Le rangement de journaux
par date semble être le plus sensé, et empiler vos journaux les uns
au-dessus des autres une méthode tout à fait acceptable.
Conclusion
Bref, ranger et rechercher : l’un impose des contraintes à l’autre, et vice-versa.
Même chose pour la paire structure de données et traitements :
vous rendrez certaines choses possibles ou impossibles, tout en en rendant
d’autres plus simples ou plus compliquées.
C’est pour cela qu’en général aucun code ou aucun algo n’est
mieux qu’un autre, ils sont simplement plus ou moins adaptés, et la
clé est de connaître à la fois la nature des données, les opérations
que l’on veut faire le plus souvent, le moins souvent, et des ordres
de grandeur pour chaque.
Pourquoi cet épisode ?
C’est un sujet beaucoup enseigné en écoles et dans les livres de
programmation, on a du mal à voir le but, et ça en bloque plus
d’un. Heureusement, il y a des chances que vous déléguiez tout ce
travail à la base de données, qui fait cela très bien. Pas
d’inquiétude.
Mais pour les rares fois où c’est votre job de choisir la base de
données la plus adaptée, et pour les cas très fréquents où vous seriez
tentés d’écrire des lignes de code très simples mais qui refont en
moins bien le travail que la base de données aurait pu faire, ça me
semble important voire nécessaire de comprendre ce qu’il y a en dessous.
