Nous bouleversons aujourd'hui la mise en page de notre superbe blog pour proposer un article en forme de bouée de sauvetage à nos lecteurs désespérés. Que sont devenus, en effet, ces magnifique Résumés Pour les Fatigués de la Lecture (RPFL pour les intimes) qui ornaient si délicatement notre tout premier dossier ? Et comment nos lecteurs pourraient-ils ne pas se noyer devant cette avalanche de conseils qu'ils ne savent par quel bout attraper, sans une lumière leur montrant le bout du tunnel, à quelques pas à peine ?
Alors, aujourd'hui, pour bien commencer l'année et rien que pour vous, nous allons sélectionner les 5 mesures que, s'il fallait n'en garder que 5 (remarquez que ça tombe bien, quand même, si on voulait en garder 6 ça ne marchait déjà plus), eh bien il faudrait les garder, justement. Un concentré de nos Petits Gestes les plus essentiels, avec un maximum de pulpe au fond et plein de belles vitamines pour l'hiver.
Avant d'aligner notre hit-parade et de briser le suspense haletant qui place la foule au bord de l'apoplexie, il nous faut confesser un péché inavouable à nos chers lecteurs. En effet, un de mes amis, qui a le bonheur de travailler dans le milieu du journalisme, m'a révélé une fois la botte secrète de l'article qui percute et fait venir des millions de lecteurs instantanément : précisément celui qui décline les 10 raisons de, les 50 les plus, les 20 mesures qui, etc. Apparemment ce type d'article bien polissé où tout est ordonné et compté fait le bonheur du badaud qui se promène nonchalamment sur l'internet mondial.
Si aux Souris Vertes nous aimons l'ambiance confinée de nos soirées de lectures intimes partagées avec nos fidèles lecteurs, et si nous ne souhaitons pas franchement faire exploser l'audience de notre site pour ensuite nous retrouver à inonder tous les médias de la terre de notre discours il est vrai si pertinent, nous avons décidé de tenter l'expérience, pour voir si la Loi de l'Article Vendeur se vérifie. Sachant qu'en plus ceci nous permet de recaser des dessins et du contenu tout prêt, autrement dit de ne pas nous fouler plus que de raison, et qu'au demeurant ce rappel salutaire pourra peut-être contribuer à sauver un ou deux phoques au passage, pourquoi bouder notre plaisir ?
Allez, c'est parti pour le Top 5 des actions tellement vertes qu'on a du mal à les distinguer de l'herbe du champ voisin.
Geste n°1 : je baisse dare-dare les réglages d'images de mes appareils numériques
"Brume matinale
Est-ce une flaque que je vois
Ou mon ombre ?"
Midoriro no Mausu (la Souris Verte)
Eh oui, voici donc le grand vainqueur de notre superbe palmarès, l'action élue la plus utile de toutes celles énumérées par les Souris Vertes, excusez du peu. Non pas que l'on manque de choix en la matière, mais le réglage par défaut des appareils numériques joue dans la cour des grands, voire carrément dans la salle des profs, en terme de gaspillage éhonté de ressources numériques. C'est qu'en effet notre petit clic a la puissance de l'aile du papillon qui va déverser une tornade d'octets inutiles sur l'ensemble du monde numérique, qu'on en juge plutôt :
- mon petit, ou minuscule, ou gros, ou super énormément géant, appareil numérique fait travailler son processeur à grand coup de traitement d'image dispendieux pour nous fournir cette superbe photographie en 112 millions de milliards de pixels. Et en plus, au passage, il sature sa propre carte mémoire pour la stocker, sympa.
- nous engorgeons la bande passante des réseaux numériques pour transférer la grosse image vers le partage Cloud, le site web, voire les boîtes de messagerie (horreur ! vous cumulez deux anti-gestes écologiques en un seul, voir ci-dessous) de notre choix.
- nous saturons les espaces de stockage où nous avons envoyé notre photo ingénue, qui ne se doute pas un instant de tout le mal qu'elle fait subir à la planète.
- nous faisons travailler inutilement le processeur de toutes les machines qui cherchent à afficher notre image et doivent la recadrer car ils ne disposent pas d'un écran de sortie de douze mètres de largeur (la taille réelle d'un affichage confortable de votre image).
Et quand on sait que les photos constituent le type de contenu le plus échangé à travers les réseaux (chiffre de l'Institut Statistique des Souris Vertes), comme en atteste la paille des 200 millions de photos postées chaque jour sur FesseBouc, bonjour l'odeur, il est grand temps pour toi, ami lecteur, de te précipiter sur l'ensemble de tes appareils numériques pour baisser d'urgence la résolution de tes images et de tes vidéos. Et bravo pour ce geste salutaire, les éléphants d'Afrique applaudissent de la trompe !
Geste n°2 : je me soigne sur l'envoi de pièces jointes dans les mails
"Elle semble si lourde
Sur la petite tortue
Sa carapace"
Midoriro no Mausu (la Souris Verte)
Ah, les pièces jointes. Autant vous dire qu'aux Souris Vertes, la réception d'une pièce jointe bien volumineuse nous fait à peu près le même effet qu'à certains le crissement des ongles sur une surface lisse, et qu'il nous faut généralement un petit exercice de respiration profonde pour absorber le choc de cette Pollution Numérique Majeure. Nous avons déjà consacré un article magistral à la question, qui figurera prochainement dans les manuels scolaires d'éducation civique, aussi nous n'allons pas détailler tous les arguments imparables qui font de la pièce jointe l'invention la moins écologique du web, mais rappelons à toutes fins utiles que :
- la pièce jointe pèse une fois et demi plus lourd que votre fichier de départ, car elle doit être encodée sous forme de texte dans le message.
- que les pièces jointes multiplient la taille des mails par Beaucoup, disons 1000 en moyenne, par rapport à un message en pur texte.
- que le, ou les, destinataires, ne peuvent pas choisir de ne pas récupérer la pièce jointe sur leur compte de messagerie.
Pour toutes ces belles raisons, il va nous falloir nous soigner et arrêter d'envoyer des pièces jointes dans les mails, ainsi que supprimer dès que possible toutes celles qui traînent dans nos propres boîtes de messagerie. Alors effectuons au plus vite ces Petits Gestes avec grâce et élégance, olé !
Geste n°3 : j'éteins ma box nom di diou
"Les yeux fermés
Je vois encore
La caresse du soleil"
Midoriro no Mausu (la Souris Verte)
Au hit-parade des gros vilains, la box internet trône en bonne place magré son apparence parfaitement inoffensive. En effet, ce petit objet qui passe le plus clair de son temps à regarder le plafond, le rebord de l'étagère ou l'arrière du bureau, et sans doute à deviser doctement et à élaborer des théories philosophiques profondes dans la langue des box internet, ne semble pas affublé de gros besoins ni nécessiter une attention quelconque de notre part. Mais ceci ne l'empêche pas de nous réclamer une alimentation électrique permanente, quand bien même nous serions au fond du jardin ou en train de dormir, par exemple, autrement dit à des moments où nos besoins en connexion réseau vers l'internet mondial sont inexistants.
Et, vu que l'ensemble des habitants du monde civilisé déploie sa propre mini box personnelle, avec souvent très obligeamment son petit réseau wifi qui rajoute un peu d'ondes au tableau, toute cette activité joyeuse de veille silencieuse de nos boîboîtes finit par représenter plus d'1% de notre consommation électrique totale. Dit comme cela, ça n'a peut-être pas l'air impressionnant, mais c'est que vous n'avez pas en tête l'ordre de grandeur de l'énormitude de notre consommation totale. Sans essayer de rapporter tout cela à la consommation de la proverbiale ménagère et du foyer moyen, estimons grossièrement qu'il faut plus d'une demi centrale nucléaire françoise pour ce petit service que nous utilisons au mieux quelques heures par jour.
Autrement dit, on met vite un interrupteur sur notre petite box, et on lui coupe la chique au minimum du soir au matin. Et pan dans les dents !
Geste n°4 : j'arrête le streaming tout de suite et pour de vrai
"Ce tronc d'arbre
Au milieu du courant
Je l'ai pris pour un homme"
Midoriro no Mausu (la Souris Verte)
Ah, le streaming, encore un cas d'école, enfin à l'école des cancres de l'écologie numérique, plus près du radiateur que du tableau. Pour les non anglophones, la traduction exacte du dictionnaire de l'Académie Française est "n.m., dérivé de l'anglais 'streaming' (se prononce strimminngueu). Consommation forcenée de bande passante réseau à travers une lecture en temps réel de contenu multimédia sur des serveurs distants". Comme toujours, revenir aux sources et à la définition exacte de notre phénomène nous permet de comprendre tout le danger qu'il fait courir aux dauphins.
C'est pourquoi on ne cherchera pas à sauver l'importune méthode de diffusion de contenu, et on s'abstiendra tout de suite et pour l'éternité de :
- poster des vidéos ou sons sur des plateforme de diffusion de contenu mondialement mondialisées, et même sur celles qui seraient plus confidentielles
- consommer des vidéos ou des sons en lignes, d'où qu'ils viennent, sauf en cas de force majeure, par exemple si votre maison va exploser et que vous avez sous la main une vidéo qui montre comment faire pour éteindre le robinet de gaz.
Geste n°5 : j'utilise le mode avion et je prends les transports en commun
"Cette fourmi
Qui monte sur ma chaussure
Pour dominer l'univers"
Midoriro no Mausu (la Souris Verte)
Dernier geste simplissime mais non moins bénéfique pour vous, vos proches et les petits oiseaux, prendre la bonne habitude d'utiliser le mal-nommé "mode avion" des téléphones portables, tablettes et autres objets connectés. Il faut savoir qu'il n'y a pas que le pilote d'avion qui pourrait trouver à redire à toutes les ondes que vous envoyez gentiment à travers votre petit récepteur, notre Agence Nationale de l'Etude des Gros Problèmes Sanitaires Liés aux Pratiques Sociales, dont le sigle est l'ANSES, allez comprendre, nous signale timidement que ceci pourrait bien être dommageable pour le développement du cerveau chez l'enfant, rien que ça. On imagine que les effets sur le reste du monde vivant, humains adultes compris, doivent être d'une innocuité telle qu'on ne les détecteraient pas même avec notre plus grand téléscope spatial si on décidait de s'intéresser un peu sérieusement à la question.
Mais passons, car ce n'est pas même le risque de perdre la moitié de nos neurones ou de développer un cancer de l'hypothalamus qui doit nous inciter à utiliser le fameux mode flouf flouf (=bruit d'hélice chez les souris vertes), mais bien son bilan écologique incroyable : il vous permet en un tour de main d'économiser des milliers de cycles de votre batterie, en plus d'avoir l'heureux effet de vous couper un peu du tumulte du monde moderne ultra-connecté qui ne cesse de vous solliciter. Ainsi vous retrouvez un peu de calme, votre petit appareil s'essoufle moins, et vous pourrez continuer à vivre en harmonie pour de nombreuses années supplémentaires. N'est-ce pas tout simplement formidable ? Allez, vite, on le fait ce petit geste !
Bon, eh bien c'est terminé pour notre super meilleur absolu du top plus fort de tous nos Petits Gestes, autant dire la crème de l'écume du petit lait de tout le blog. Mais espérons que ceci vous a donné l'envie, non seulement de réaliser ces petites actions simples mais si utiles pour notre belle planète, mais aussi d'aller vous jeter à corps perdu dans tous les autres gestes, articles, vils pamphlets polémiques et trésors divers qui parsèment notre magnifique collection au fier logo de petit muridé vert pomme.
Et pour les lecteurs occasionnels et de passage, on se retrouvera lors d'un prochain palmarès, au choix, des 3 plus beaux dessins, des 10 meilleurs haïkus, des 20 titres les plus cocasses, ou encore des 50 expressions les plus incongrues. Vivement la suite !
"Un bébé moineau
Saute avec curiosité
Pour regarder mon coup de pinceau"
Mizuhara Shuoshi (1892-1981)
"Placardée sur la porte d'entrée
La photo
Du chat qui n'est jamais revenu"
Midoriro no Mausu (la Souris Verte)
"J’ai manqué mon coup
La tête du clou
Est toute tordue"
Nakatsuka Ippekiro (1887-1946)
Hum, bon d'accord, on n'arrête pas de recycler le même dessin sur notre dossier, et alors ? Il faut dire que les titres de nos palpitants articles ne se prêtent pas facilement à une illustration imagée, surtout pour qui dessine avec le talent artistique d'un enfant de 3 ans ayant enfilé une bonne paire de moufles.
Bref, passons ces trivialités car on ouvre aujourd'hui un article excessivement important voire, nous n'avons pas peur de le dire, au moins aussi vital, indispensable et crucial que tous les autres mais même presque plus. Et, pour couronner le tout, il constitue un prolongement renversant à la fois de notre article sur l'algorithmique, non n'ayez pas peur, et de notre dernier article sur la base de données. Rappelez-vous, nous y avions énoncé, en effet, qu'il s'agissait autant que faire se peut de travailler en mémoire, et non à grand coup d'appels débridés à une base de données sympathique mais pas très véloce.
Et justement, aujourd'hui, nous regardons comment stocker efficacement des données en mémoire. Car la mémoire, certes, c'est rapide, mais il y a bien des manières de rendre un programme qui s'exécute entièrement dans cette belle zone nimbée aussi alerte qu'un hippopotame au sortir du déjeuner. Et, une fois de plus, c'est l'algorithmique qui va nous aider à faire la part des choses et à devenir le Programmeur Responsable de nos rêves.
Allez, n'introductions pas davantage car le fer est chaud et nous aussi, autant le battre sans tarder. En voiture ! Je précise que la voiture est à pédale, on ne va pas commencer à émettre des particules fines dans ce bel article aux éclats verdoyants d'automne, quand même. Aïe ! Ca y est, je me fais mordiller la cheville par les souris qui souhaitent qu'on en vienne au fait. On y va, on y va !
Et le menteur, mon cher Ouètsonne
Première révélation qui ne bouleversera pas ceux qui ont lu notre dernier article, nos données doivent être bien organisées pour s'adapter au contexte dans lequel on souhaite ensuite les récupérer. Ce n'est pas parce qu'on va travailler en mémoire que tout ce qu'on peut imaginer est efficace. A vrai dire, aucune structure de données n'est parfaite à tout point de vue, ça serait trop facile, c'est pourquoi il nous faut convoquer un peu nos connaissances en algorithmique et distinguer les opérations élémentaires suivantes :
- je souhaite accéder à une donnée précise dans mon gros paquet
- je souhaite ajouter une donnée à mon gros paquet
- je souhaite retirer une donnée à mon gros paquet
- je souhaite savoir si une valeur donnée appartient à mon gros paquet
- je souhaite énumérer toutes les données de mon gros paquet
Eh bien, c'est à peine pensable, mais il se trouve qu'AUCUNE, non, pas même une seule nulle part dans la galaxie, structure de données n'est parfaitement efficace pour toutes ces opérations. C'est bien la raison du pourquoi du fondement de cet article, en vérité, car il va nous falloir systématiquement faire des choix qui vont favoriser certaines opérations au détriment d'autres. C'est pourquoi tout Programmeur ResponsableTM se doit de connaître sur le bout des doigts une panoplie de structures de données, avec leurs avantages et leurs inconvénients, et d'être capable d'analyser son besoin pour choisir la plus adaptée au moment d'écrire ses milliers de lignes de code.
Le drame pour notre planète, mais qui en voit d'autres de toute manière, est que le choix systématique d'une structure de données pas du tout adaptée produit une pollution toute silencieuse : la machine ne crie pas, ne fume pas, le programme s'exécutera très bien, souvent même raisonnablement vite vu la puissance des processeurs, même ceux qui équipent les barrières de péage, donc personne ne s'aperçoit de ce gâchis constant d'instructions et de cycles machines, à part à la fin des fins l'ours polaire qui doit se déplacer de plusieurs dizaines de kilomètres supplémentaires chaque année pour trouver de la banquise.
Mais nous comptons bien que nos lecteurs aguerris et amateurs de gentilles souris vertes ne s'en laisseront pas conter et feront bien vite tous les efforts nécessaires, quand bien même ils ne recevraient pas de récompense du chef de l'Etat et d'acclamations de la foule en délire pour leur petite contribution stoïque à l'écologie numérique.
Or donc, comme nous le disions, aucune structure de données ne sera efficace pour toutes nos petites opérations élémentaires, et leur degré d'inefficacité se mesure grâce à la complexité propre à chacune de ces opérations, et là vous comprenez que vous avez bien fait de vous farcir notre bel article sur l'algorithmique sans vous assoupir.
Prenons par exemple le fait de trouver une donnée dans notre gros paquet de N données. Supposons que l'on a vraiment rangé tout ça en désordre complet, il nous faudra de l'ordre de N opérations (en général un peu moins, disons N/2 en moyenne, mais l'ordre de grandeur reste le même) pour aller retrouver notre petit copain, en gros on va les énumérer jusqu'à trouver la bonne. Si on a fait un petit effort, par exemple trié à l'avance nos données, on peut s'en sortir avec de l'ordre de log(N) opérations, ce qui est déjà nettement mieux, n'est-ce pas. Rappelons à toutes fins utiles, et sans frimer excessivement nos cours de maths de terminale, que log(10000)=4log(10), par exemple, soit au lieu de 10 000 essais, on en fait une dizaine environ. C'est mieux, non ? Mais toujours plus fort de café, si on a choisi une structure vraiment adaptée, on peut extraire notre donnée en une seule opération. Une seule ! Autrement dit ça vaut quand même bien le coup de choisir, non ?
Alors il se trouve que la plupart des programmeurs ne connaissent que le tableau, qui est une structure bien sympathique, mais qui offre précisément la complexité la moins bonne quand il s'agit d'aller chercher une valeur précise, même si elle a plein de qualités par ailleurs concernant les autres opérations. Bref, les tableaux sont certainement surutilisés (une souris me demande si ça existe, je suis sûr que l'Académie Française se hâtera de nous corriger, voire de l'inclure lors de sa prochaine session , si ça n'est pas le cas), et il serait bien temps de diversifier un peu notre palette en la matière.
Une petite remarque supplémentaire avant de décrire un peu le choix pléthorique au supermarché des structures de données : il faut savoir que toute structure de données n'est concrètement implémentée, à la fin des fins, qu'avec une combinaison de deux structures élémentaires, à savoir les tableaux et les listes chaînées. Couplée à quelques variables bien choisies, et parfois à des fonctions algorithmiques redoutables (comme les fonctions de hachage, par exemple), ces objets sympathiques nous permettent de construire des structures de données nettement plus complexes et adaptées à des situations très diverses. Cela dit, à moins d'utiliser un langage qui n'offre aucune structure de données un tant soit peu élaborée, et il y en a, ou d'avoir un besoin très spécifique en la matière, on aura rarement à implémenter soi-même ses propres structures de données complexes en partant de petits tableaux ou de listes chaînées.
Dernier point, enfin, la complexité en nombre d'opérations n'est pas nécessairement le seul critère qui entre en jeu quand il s'agit de choisir une structure de données, la place qu'elle occupe en mémoire peut également être décisive si vous stockez vraiment une grosse quantité de données. En règle générale, la différence n'est pas suffisamment importante d'une structure à l'autre pour que l'on prenne la peine de s'en soucier (les performances avant tout, n'est-ce pas), mais dans les situations extrêmes de beaucoup beaucoup d'octets à manipuler, on devra commencer à prendre des pincettes. Mais c'est également dans ce cas qu'on finira peut-être par développer ses propres structures de données aux petits oignons, si on en est là. Dans tous les cas, la structure de données qui occupe le moins de place en mémoire est le tableau, eh oui, bravo à lui. Comme quoi c'est tout de même un camarade bien gentil, malgré ses quelques défauts par ailleurs.
Tu les ranges tes données ?
Allez, il est temps de nous lancer dans un grand top 50, mais avec moins d'entrées au hit-parade quand même, des structures de données élues plus vertes de tous les temps par SourisMag. Bon, à vrai dire il existe tout un tas de structures très exotiques que nous garderons sous silence (arbres de plein de variétés, graphes, etc), pour nous contenter des structures les plus simples et les plus fréquemment utilisées. Nous allons également discuter des points forts et des points faibles de chacune, histoire de bien comprendre ce qui doit guider nos choix.
1 - Il est beau mon tableau
On commence par celui que nous connaissons tous, la structure universelle que même le VisualBasic de tonton doit savoir manipuler (enfin je dis ça, je m'avance peut-être), à savoir le tableau. Simple, élégant de bon, goût, le tableau est une structure formidable quand elle est implémentée par une vraie série de cases contigues en mémoire, jugez plutôt :
Plein d'avantages :
- c'est la structure la plus économe en mémoire
- c'est la structure la plus rapide à énumérer. Il ne faut qu'une seule opération pour passer d'un élément au suivant, et si en plus le tableau est tout entier dans le cache processeur ou dans la page de mémoire vive courante, on vole à la vitesse du vent
- c'est aussi la structure la plus efficace pour atteindre un élément donné si on connaît sa position : une seule opération, là encore, avec la même remarque que précédemment si le tableau est déjà chargé en mémoire
Mais des inconvénients :
- atteindre un élément dont on connaît la valeur, mais pas la position, demande d'énumérer tous les éléments. Coût de l'opération : de l'ordre de N instructions pour un tableau de taille N.
- c'est une des structures qui a le plus fort coût à l'insertion d'un élément. Si on l'ajoute à la fin et qu'on a alloué la place mémoire pour l'élément en trop, aucun problème. Par contre, ajouter un élément ailleurs nous oblige à décaler tous les éléments. Si jamais on a plus de place pour mettre un élément en plus, il faut allouer un tableau plus grand et tout recopier, bonjour le nombre d'opérations. Dans tous les cas l'insertion d'un élément coûte l'ordre de grandeur du nombre de valeurs dans le tableau.
- la suppression d'un élément est encore pire, sauf si là encore c'est le dernier. Dans tous les autres cas, c'est recopie de tous les éléments vers la gauche, sans possibilité de désallouer la mémoire inutilisée, sauf à tout recopier ailleurs, et là encore on paie environ N éléments en ordre de grandeur pour un tableau de taille N, sans compter la mémoire dépensée le temps de réaliser la copie. Eh oui ma bonne dame.
2- La liste déchaînée
Autre candidat bien sympathique parmi les structures toutes élémentaires, qu'on peut réimplémenter soi-même dans son salon sans risquer d'affreux plantages De La Mort, j'ai nommé la liste chaînée, sous vos applaudissements. Elle est toute simple : chaque élément contient une valeur, et un pointeur vers l'élément suivant. Facile, non ?
Des avantages à gogo :
- une efficacité redoutable pour énumérer tous les éléments, par petits sauts de puce de pointeur en pointeur. Pas tout à fait aussi véloce que le tableau, mais l'ordre de grandeur pour atteindre chaque élément depuis le précédent est d'une opération aussi.
- c'est une structure pas totalement, mais quand même relativement, efficace pour l'insertion d'un élément, où qu'il soit. En fait, il faudra compter de sauter jusqu'à l'élément où vous voulez ajouter un copain, donc plus il est loin du début, plus vous payez. Une seule instruction si vous insérez systématiquement en début de file, mais de l'ordre de N instructions si jamais vous allez n'importe où, c'est moins super.
- même chose pour la suppression, opération élémentaire, qui ne demande que de localiser l'élément en question.
Mais aussi des inconvénients quand même :
- on l'a déjà dit, atteindre un élément donné, par sa position comme par sa valeur, nécessite de suivre toute la liste, donc un ordre de grandeur de N opérations. Bof bof.
- cette structure occupe davantage de place en mémoire que le tableau, puisqu'en plus de la valeur on stocke l'adresse de l'élément suivant. Pas forcément énorme, mais ça peut commencer à saler l'addition si on a vraiment une grosse structure à maintenir.
Il existe une variante tout aussi rigolote, appelée la liste doublement chaînée, où, pour chaque élément, on stocke un pointeur vers l'élément précédent en plus du suivant. Dans ce cas on peut parcourir facilement la liste dans les deux sens, et insérer aussi facilement en début qu'en fin de liste. Pratique, mais là encore il y a un surcoût en mémoire.
3- En file indienne
Ah ah, ici on commence à rencontrer des structures un peu plus élaborées qui vont nous servir dans des situations très pratiques. Reconnaissons-le franchement, si on utilise des tableaux de manière courante, on ne va pas souvent sortir des listes chaînées de notre chapeau, sauf pour un exercice scolaire de programmation. Par contre la file, ça oui, on en voit partout et tout le temps. Dès qu'on fait communiquer deux machines/programmes/souris entre elles/eux, on a besoin d'une petite file : une structure où on empile d'un côté, et on dépile de l'autre, comme ça on prend toujours les éléments dans leur ordre d'arrivée, et on évite de mettre un joyeux désordre dans notre communication.
Alors, en fait la file en tant que telle peut être implémentée de plein de manières, mais si vous avez bien suivi ce qui précède, vous voyez que la plus efficace de loin est la liste doublement chaînée, puisque les opérations que l'on privilégie sont l'insertion en début et la suppression en fin de file. On peut s'en sortir aussi avec un tableau de taille variable, mais c'est à condition de connaître à l'avance la taille maximale du nombre d'éléménts qu'on peut mettre dans notre structure.
Pourquoi elle est gentille :
- insérer et supprimer un élément aussi bien en début qu'en fin de file ne nous coûte qu'une seule instruction machine, formidable.
- récupérer tous les éléments un à un à la suite est très efficace, même si ça n'est généralement pas pour cela qu'on choisit une file.
Pourquoi elle est méchante :
- l'insertion ou la suppression en milieu de file est totalement prohibée. Elle serait théoriquement possible, mais avec un surcoût non négligeable, et de toute manière c'est en contradiction flagrante avec la finalité même de la structure, donc souvent cette opération n'est même pas disponible.
- aller inspecter la file pour voir si une valeur précise y est stockée demande d'énumérer tous les éléments, donc de l'ordre de N instructions pour une file de taille N. Et là encore, cette possibilité n'est pas toujours offerte à l'utilisateur sympathique.
4- Remonté comme une pile
Autre structure à inclure dans sa petite besace, largement sous-estimée et trop peu utilisée à notre goût, la pile est votre amie dès lors qu'il s'agit ranger nos éléments pour ressortir toujours du tas le dernier déposé. Notez bien la différence avec la file, qui elle prend toujours l'élément le plus ancien encore disponible.
Par ailleurs, la pile est absolument indispensable dès que vous faites des parcours d'arbres en profondeur, ce que vous faites, si si, dès que vous parcourez une arborescence de fichiers. Si vous ne vous en rendez pas compte la plupart du temps, c'est que vous utilisez la pile d'appels de votre langage de programmation, en lieu et place de la votre propre.
Disons le franchement, elle regorge de qualités :
- l'insertion et la récupération d'un élément est simplissime, une seule minuscule instruction
- c'est une structure excessivement économe en mémoire, en tout cas quand elle est correctement implémentée
- l'énumération (enfin, le dépilement) de tous les objets dans la pile est très efficace
Mais elle a quand même quelques défauts :
- impensable d'insérer ou de retirer un élément ailleurs qu'au début, sans quoi elle perd tout son intérêt
- savoir si une valeur est présente dans la pile nécessite d'en énumérer tous les éléments un à un, donc de l'ordre de N instructions. Et encore, ceci n'est pas toujours possible sans dépiler puis réempiler tout le bazar.
5- Tout en gros tas
Moins connu du grand public, et très honnêtement assez difficile à trouver sur le marché aux structures incluses dans les librairies courantes, le tas est pourtant bien pratique dans certaines situations. Il faut dire aussi que son nom n'est pas très vendeur non plus, aux souris vertes on l'appelle souvent le Gros Tas, même si on a beaucoup d'affection pour lui.
Alors, le tas sert à entasser, eh oui, toutes nos petites données en leur accolant un poids. Plus la donnée pèse lourd, plus elle part au fond du tas. Et on peut ainsi récupérer en une seule instruction la donnée la plus légère, puis la suivante, etc. Il existe une variante également où c'est le plus lourd que l'on ressort à chaque fois ; bon, même si ça n'est pas disponible il suffit d'affecter l'opposé de nos poids pour que ça fasse la même chose, remarquez bien.
Une formidablitude non démentie :
- il faut une seule opération pour obtenir le minimum (ou le maximum) de notre structure. Attention cependant, comme l'insertion d'un élément n'est pas la plus économe, construire un tas juste pour trouver le minimum de N valeurs est moins efficace que d'énumérer simplement les valeurs en gardant la plus petite.
- l'énumération des valeurs successives ne coûte rien, et en prime on vous les renvoie dans l'ordre croissant des poids. Le tas fait donc partie des structures optimales pour trier des données, et est utilisé par un certain nombre d'algorithmes de tri
- voir si une valeur existe dans le tas est très rapide, de l'ordre de log(N) opérations pour un tas de taille N.
- l'insertion et la suppression d'une valeur est également relativement efficace, de l'ordre de log(N) opérations
Mais pas que non plus :
- ben, en fait, on pourrait remettre ici tous les points précédents : insertion, suppression, lecture d'une valeur, sont efficaces, c'est vrai, mais il existe des structures bien plus rapides pour chacune des ces opérations. Le tas est plutôt bon partout, mais il n'excelle nulle part.
En pratique, il n'y a pas de mystère, si le tas n'est pas utilisé de manière courante, c'est qu'il ne se démarquera de ses petits copains que dans des cas très spécifiques, et que pour l'écrasante majorité des cas il y aura toujours une structure plus adaptée. Mais ça reste souvent un bon deuxième choix si aucune implémentation d'une structure que vous souhaitiez n'est disponible.
6- En finesse mais à la hache
Nous avons gardé le meilleur pour la fin. Il existe toute une classe de structures qui s'appuient sur des fonctions de hachage pour vous offrir une efficacité redoutable sur certaines opérations très courantes. La structure algorithmique sous-jacente s'appelle une table de hachage, mais elle permet d'implémenter dictionnaires, ensembles, tableaux associatifs et sans doute encore d'autres structures que nous oublions au passage.
Le principe est toujours le même : grâce aux fameuses fonctions de hachage sorties du cerveau brumeux de mathématiciens déchaînés, nous sommes en mesure d'accéder à une valeur donnée de notre ensemble en une seule opération. Oui, une seule, et ceci quel que soit l'élément et quelle que soit la taille de votre ensemble. Vous pouvez vous pincer, vous ne rêvez pas. Alors, tout ceci n'a pas que des avantages, ça serait trop facile, et il va falloir payer du gros coût à la sortie sur certaines opérations. En général, nous utilisons ces structures pour stocker des ensembles (clé, valeur), on donne la clé et on retrouve la valeur en une seule opération rapide comme l'éclair.
Que de délices nous attendent :
- nous venons de le dire, une seule opération pour l'accès à un élément donné en connaissant uniquement sa clé associée.
- une seule opération aussi pour insérer et supprimer une clé de notre paquet
- une seule opération pour répondre à la question : ma clé est-elle dans mon gros tas ? Du coup c'est très utile pour dédoublonner des valeurs dans un ensemble : on pose tout dans notre dictionnaire / ensemble / table de hachage, et à l'arrivée l'ensemble des clés ne contient que des valeurs uniques.
Mais attention l'addition est parfois salée :
- commençons tout de suite par ce qui fâche, à savoir l'énumération des éléments qui est tout simplement misérable. Nous trouvons ici de très loin la structure la plus lente pour énumérer les éléments les uns après les autres, un phénomène dont bien peu de programmeurs semblent avoir conscience, qui mettent tout ce qu'ils ont sous la main dans une table de hachage uniquement pour la parcourir entièrement à la fin. Croyez-moi, la différence avec un tableau est tout simplement abyssale si la structure est de grande taille.
- la structure demande plus de place en mémoire que la plupart des autres structures élémentaires énumérées ici. Bon, rien d'incroyable non plus, surtout si elle est bien implémentée, mais dans certains langages où ça n'est pas le cas, la place occupée en mémoire peut devenir assez vite gênante.
- les opérations élémentaires demandent en moyenne une instruction, c'est vrai, mais il s'agit tout de même d'un calcul de hash qui est nettement plus qu'un simple accès à un élément dans un tableau par sa position. Donc une GROSSE instruction, quand même, et qui sollicite gentiment le processeur au passage.
- dernier point, si les hashs sont mal distribués, c'est-à-dire si la fonction de hachage utilisée ne se comporte pas très bien avec les données que vous stockez, eh bien là les ennuis commencent sérieusement et la structure devient aussi gracile qu'un éléphant cherchant à faire du skateboard. Le risque est minime tant que la taille de la structure reste limitée, mais si vous commencez à y jeter plusieurs millions d'entrées, il va sans doute falloir y regarder de plus près sur la manière dont la structure est implémentée dans les coulisses.
Mais cette dernière remarque est finalement valable pour n'importe quelle structure : si vous dépassez une taille critique, disons plusieurs centaines de milliers d'entrées, vous pourrez rarement vous contenter de l'implémentation standard à portée de main, et il vous faudra sans doute, soit la paramétrer finement, soit en modifier le code, soit carrément repartir de zéro pour écrire la votre à la place.
Soigner son langage
Bien, nous en avons terminé de notre petit tour d'horizon des plus belles structures de données de la collection automne-hiver de l'année. Nous ne pouvons que vous inviter à découvrir par vous-même tous les autres trésors que nous n'avons pas abordés ici, sachant que plus vous choisirez une structure adaptée à vos besoins, plus votre code sera performant et votre impact en mémoire ou en stockage limité.
Mais, en pratique, on ne peut pas non plus occuper son temps éveillé à implémenter des structures de données, donc on est bien souvent contraint de s'appuyer sur celles qui sont disponibles de base dans le langage de programmation que nous utilisons. Arrivé à ce point de notre réflexion, on se rendra vite compte que tous les langages ne sont pas équivalents, non non non, et que s'il faut un critère pour les discriminer, au-delà des Super Benchmarks De La Mort qui vous démontrent que X lave plus blanc car il calcule des fractales à la vitesse du son, on sera bien inspiré de regarder si ledit langage possède des structures de données bien implémentées et adaptées à toutes les situations.
En général, quel que soit le langage utilisé, on essaiera d'avoir au minimum deux structures toujours sous le coude : un bon vieux tableau, ou liste, pour les traitements qui demandent des énumérations fréquentes, et une table de hachage, ou équivalent, pour tout ce qui demande des accès par valeur, ou du dédoublonnage. Muni de ces deux outils de base, et en choisissant systématiquement celui qui va le mieux, nous sommes déjà en mesure d'écrire du code quasi optimal dans toutes les situations courantes. Si en plus, on a gardé en tête les conseils de notre dernier article, et qu'au lieu de spammer notre base de données, on monte en mémoire une structure qui nous permet de les interroger de la manière la plus efficace possible tout au long de l'exécution de notre programme, on aura largement mérité d'encadrer notre diplôme de Programmeur Responsable (TM) au-dessus du canapé de notre salon.
Mais t'arrêtes donc de recopier, toi ?
Une dernière remarque, et après promis on s'arrête là pour aujourd'hui, car les souris piétinent d'impatience à mes côtés, il y a une chose qu'il faut absolument contrôler lorsque vous utilisez un langage de programmation, c'est la manière dont sont passés les paramètres des fonctions. Il y a en fait deux possibilités :
- les paramètres sont passés par référence, c'est-à-dire qu'on vous donne un pointeur sur l'objet que vous aviez passé, et que votre fonction peut le modifier à loisir, vous récupérez ensuite l'objet modifié
- les paramètres sont passés par valeur, autrement dit vous en avez une copie toute neuve dans votre fonction que vous pouvez triturer à l'envi, l'appelant n'en saura rien, le coquin.
Aucune des deux méthodes n'est universellement satisfaisante, car parfois vous aimeriez bien que la fonction appelée n'aille pas mettre en bazar tout ce que vous lui envoyez, et en même temps si vous avez une structure géante, vous ne voulez pas forcément la recopier entièrement de fonction en fonction.
"Dans son écorce
Le chêne
Garde la mémoire de mon regard"
Midoriro no Mausu (la Souris Verte)