BROADCASTS.com

Published: March 13, 2016, 1:45 p.m.

b'

Bonjour, bienvenue dans cet \\xe9pisode 8 sur les algorithmes de recherche\\net de tri de donn\\xe9es, ins\\xe9parable de cet autre sujet : les structures de donn\\xe9es.

\\n\\n

Pour moi, une grande partie du travail de codeur (mais pas que de codeurs),\\nsurtout d\\xe9butant (mais pas que), c\\u2019est de rentrer des informations,\\npuis chercher des informations.

\\n\\n

Il y a beaucoup \\xe0 dire, j\\u2019ai \\xe9crit de quoi faire deux \\xe9pisodes, il y\\nen aura s\\xfbrement un troisi\\xe8me dans les m\\xeames lignes plus tard.

\\n\\n

Ranger et chercher

\\n\\n

Les deux sont tr\\xe8s li\\xe9s : jeter tous vos livres n\\u2019importe o\\xf9 est une\\nm\\xe9thode de rangement incroyablement rapide, mais la recherche est\\nincroyablement inefficace.

\\n\\n

Ranger tous vos livres par titre demande du travail, mais revenir chercher\\nun livre par la suite est tr\\xe8s rapide, si on se rappelle du titre bien s\\xfbr.

\\n\\n

Autre avantage : si vous n\\u2019avez pas le livre, vous voyez qu\\u2019il manque l\\xe0\\no\\xf9 l\\u2019ordre alphab\\xe9tique l\\u2019aurait plac\\xe9 : inutile de le chercher ailleurs,\\nvous savez que vous ne le poss\\xe9dez pas ou l\\u2019avez pr\\xeat\\xe9 en ce moment.

\\n\\n

L\\u2019alternative, sans rangement, aurait \\xe9t\\xe9 de regarder chacun de vos\\nlivres, et de vous rendre compte tout \\xe0 la fin que vous ne l\\u2019avez pas.\\nC\\u2019est tr\\xe8s inefficace et frustrant.

\\n\\n

C\\u2019est pour cela que chacune des m\\xe9thodes n\\u2019est pas objectivement\\nmeilleure ou moins bonne, mais les papiers scientifiques sur les\\nstructures de donn\\xe9es ou algos de tri vont chercher \\xe0 les \\xe9valuer en\\nterme de meilleur cas, pire cas, et cas moyen.

\\n\\n

Explorer le probl\\xe8me

\\n\\n

Un l\\xe9ger probl\\xe8me toutefois, une s\\xe9rie de plusieurs tomes a rarement des\\ntitres en ordre alphab\\xe9tique, et vous devrez donc \\xe9parpiller la s\\xe9rie dans\\nvotre biblioth\\xe8que.

\\n\\n

Nouveau probl\\xe8me, nouvelle solution.\\nOn tente un truc un peu plus malin : trier par nom d\\u2019auteur.

\\n\\n

C\\u2019est un avantage int\\xe9ressant dont se servent les librairies et les\\nbiblioth\\xe8ques : ranger par auteur permet souvent d\\u2019avoir des livres\\nc\\xf4te \\xe0 c\\xf4te qui soient probablement int\\xe9ressants pour l\\u2019acheteur ou le\\nlecteur, ne serait-ce que par th\\xe8me proche ou pour ranger une s\\xe9rie\\nensemble.

\\n\\n

Chaque auteur \\xe9crit plusieurs livres, enfin on l\\u2019esp\\xe8re pour eux. Il\\nfaut donc un autre crit\\xe8re d\\xe9terminant pour classer entre eux les\\nlivres de l\\u2019auteur : alphab\\xe9tique ou date casserait l\\xe0 aussi des\\ns\\xe9ries (pour les auteurs qui \\xe9crivent plusieurs s\\xe9ries en parall\\xe8le),\\n\\xe0 vous de voir.

\\n\\n

Au pire, on vous force \\xe0 reparcourir la section des livres d\\u2019un auteur\\ndu d\\xe9but \\xe0 la fin pour savoir si le magasin poss\\xe8de bien tel ou tel\\nexemplaire. On a perdu le c\\xf4t\\xe9 imm\\xe9diat et infaillible de l\\u2019ordre\\nalphab\\xe9tique pur, mais on a gagn\\xe9 quand m\\xeame puisqu\\u2019on a restreint\\ncette phase p\\xe9nible \\xe0 la section d\\u2019un auteur.

\\n\\n

Sur les milliers d\\u2019ouvrages de la librairie, vous y gagnez :\\nimaginez la longueur de la section de livres qui commencent par\\n\\u201cHistoire de/des/de la\\u201d ou \\u201cM\\xe9thode de/des/pour\\u201d par exemple.

\\n\\n

Eh oui : la nature de vos donn\\xe9es va donc aussi influer sur le choix\\nde la structure de donn\\xe9es \\xe0 choisir !

\\n\\n

Attention toutefois :\\nil faudra trouver une astuce quand il y a plusieurs auteurs\\u2026

\\n\\n

La structure et le besoin

\\n\\n

On vient de faire un arbitrage entre la complexit\\xe9 de rangement \\xe0\\nchaque fois qu\\u2019on ajoute ou remet un livre dans les \\xe9tag\\xe8res, contre\\nun \\xe9norme avantage \\xe0 la recherche. Si votre probl\\xe8me est rarement\\nd\\u2019ajouter ou ranger des \\xe9l\\xe9ments, et plus souvent de rechercher, c\\u2019est\\nun co\\xfbt qu\\u2019il est int\\xe9ressant de payer.

\\n\\n

Mais quand vous faites des logs dans votre application, vous listez\\ntout ce qui se passe pour, peut-\\xeatre, y chercher des informations un\\njour. On peut alors l\\xe9gitimement choisir l\\u2019arbitrage inverse.

\\n\\n

Par exemple, les journaux sont un produit radicalement diff\\xe9rent d\\u2019un\\nlivre : ils contiennent des informations vari\\xe9es d\\u2019auteurs vari\\xe9s, et\\nune bonne partie de ce qu\\u2019ils contiennent n\\u2019est plus aussi int\\xe9ressant\\nau bout d\\u2019une semaine, un mois, deux ans\\u2026 Le rangement de journaux\\npar date semble \\xeatre le plus sens\\xe9, et empiler vos journaux les uns\\nau-dessus des autres une m\\xe9thode tout \\xe0 fait acceptable.

\\n\\n

Conclusion

\\n\\n

Bref, ranger et rechercher : l\\u2019un impose des contraintes \\xe0 l\\u2019autre, et vice-versa. \\nM\\xeame chose pour la paire structure de donn\\xe9es et traitements :\\nvous rendrez certaines choses possibles ou impossibles, tout en en rendant\\nd\\u2019autres plus simples ou plus compliqu\\xe9es.

\\n\\n

C\\u2019est pour cela qu\\u2019en g\\xe9n\\xe9ral aucun code ou aucun algo n\\u2019est\\nmieux qu\\u2019un autre, ils sont simplement plus ou moins adapt\\xe9s, et la\\ncl\\xe9 est de conna\\xeetre \\xe0 la fois la nature des donn\\xe9es, les op\\xe9rations\\nque l\\u2019on veut faire le plus souvent, le moins souvent, et des ordres\\nde grandeur pour chaque.

\\n\\n

Pourquoi cet \\xe9pisode ?

\\n\\n

C\\u2019est un sujet beaucoup enseign\\xe9 en \\xe9coles et dans les livres de\\nprogrammation, on a du mal \\xe0 voir le but, et \\xe7a en bloque plus\\nd\\u2019un. Heureusement, il y a des chances que vous d\\xe9l\\xe9guiez tout ce\\ntravail \\xe0 la base de donn\\xe9es, qui fait cela tr\\xe8s bien. Pas\\nd\\u2019inqui\\xe9tude.

\\n\\n

Mais pour les rares fois o\\xf9 c\\u2019est votre job de choisir la base de\\ndonn\\xe9es la plus adapt\\xe9e, et pour les cas tr\\xe8s fr\\xe9quents o\\xf9 vous seriez\\ntent\\xe9s d\\u2019\\xe9crire des lignes de code tr\\xe8s simples mais qui refont en\\nmoins bien le travail que la base de donn\\xe9es aurait pu faire, \\xe7a me\\nsemble important voire n\\xe9cessaire de comprendre ce qu\\u2019il y a en dessous.

'