Ico Chamois d"or
Ico Polémiquons
Ico Le saviez-vous ?
Ico Dossier
Ico Club de lecture
Ico Le Petit Geste du Jour
Ico Réseau
Ico Messagerie
Ico Navigateur
Ico Système
Ico Multimedia
Ico Divers

Résultat de votre recherche


1 2 3
La Programmation Responsable (5) : les structures de données tu maîtriseras
Date 07/12/2017
Ico Dossier
Comms Aucun commentaire


"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.


Alors, attention tout de même, tout ce qui brille n'est pas or, et tous les langages qui proposent des structures associatives ne les implémentent pas forcément de manière efficace. Aux Souris Vertes, par exemple, on se gausse régulièrement, mais gentiment, du gros éléphant PHP, un des langages pourtant les plus utilisés au monde, qui propose des tableaux associatifs qui ne sont efficaces ni comme tableaux, ni comme structure d'association. Une belle prouesse !


Halte au maintien de l'ordre

Il existe évidemment des milliards de millions d'autres structures de données qui peuplent l'univers de l'informatique moderne. Parmi celles-ci, il y en  qui nous laissent franchement perplexes aux souris vertes, à savoir celles qui maintiennent un ordre naturel des éléments : une liste ou un tableau triés, une map ordonnée (comme une table de hachage dont on peut énumérer les clés dans l'ordre croissant), etc.

Entendons nous bien, le fait d'avoir des données triées permet d'accélérer notablement certaines opérations, comme le fait de trouver un élément en log(N) par exemple au lieu de N essais. Mais, généralement, le fait de devoir maintenir l'ordre à l'insertion et la suppression de valeurs coûte bien plus cher que le fait de tout ranger sans se poser de question et de retrier ensuite. Donc, à moins d'avoir absolument besoin de l'ordre des éléments entre deux insertions, on sera bien inspiré de se tenir loin de ces structures qui ont l'air toutes bien rangées, mais sont sous-optimales pour pratiquement toutes les opérations (insertion, suppression, récupérer une valeur, etc).


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.


Les langages les mieux conçus passent généralement les types primitifs (entiers, chaînes de caractères, etc) par valeur, et les objets plus complexes par référence, mais certains ont le mauvais goût de tout passer par valeur si on ne leur dit rien, et alors là bonjour les dégâts : dès que j'appelle une fonction, c'est recopie à gogo, donc grosse perte de temps et de mémoire. Pour ceux-là, on forcera systématiquement le code à passer nos structures de données par référence. Et si cela n'est pas disponible, fuyez le langage en question comme la peste !



Nous voici au bout de notre exploration curieuse et étonnée des structures de données en mémoire. Nous espérons n'avoir pas trop fatigué les lecteurs avec ces considérations qui peuvent avoir l'air de détails microscopiques , mais qui sont essentielles à nos yeux pour réduire le gaspillage informatique planétaire. Les souris sont déjà en train de courir dans le jardin, aussi je tire ma révérence en vous laissant vous délasser l'esprit sur un petit haïku final :

"Dans son écorce
Le chêne
Garde la mémoire de mon regard"

Midoriro no Mausu (la Souris Verte)

>Voir le billet et ses commentaires...
 

La Programmation Responsable (3) : de déléguer la programmation tu éviteras
Date 18/11/2017
Ico Dossier
Comms Aucun commentaire

La programmation façon souris verte


"Elles sont amaigries
Les mains qu’il joint
Lui pour qui je joins les miennes"

Yamaguchi Seishi (1901-1994)


Suite de notre palpitant dossier, nous prenons un peu de hauteur aujourd'hui jusqu'à nous élever dans la stratosphère de la pensée militante, pour dénoncer un fait social proprement scandaleux, inique et révoltant, rien de moins. A n'en pas douter, aucun domaine de l'activité humaine ne saurait être épargné par le phénomène moderne de la sous-traitance, qui sous ses dehors débonnaires d'efficacité industrielle et de ravissement béat du consommateur devant l'écrasement sans fin des prix, cache dans son arrière-boutique les violations de droits humains et de l'environnement qui permettent qu'un produit que personne ne saurait fabriquer de ses seules mains en moins de quelques décennies soit offert contre une poignée d'euros.


Fort heureusement éloignés de ces sombres vicissitudes, nos chers lecteurs-programmeurs n'en sont pas encore rendus à faire travailler des enfants ou à pulvériser des tonnes de produits toxiques pour gagner leur pain à la sueur de la main sur le clavier. Ouf. On notera cependant que la situation sociale dans les métiers de l'informatique n'est pas exempte des meilleures pratiques de précarisation ordinaire, avec de gentilles sociétés informatiques qui se dotent de conventions sociales dignes d'un roman de Dickens, et entretiennent une pratique décomplexée de l'exploitation du jeune diplômé à faire pâlir de jalousie les agences d'intérim. Le recours croissant à de la sous-traitance dans des pays à bas coût, qu'il faut bien aider les pauvres, pour de la production de code ou pour de l'assistance informatique à distance, achève de nous peindre un monde de l'informatique où il fait bon faire carrière.


Mais foin de tout cela, car je me fais rappeler à l'ordre par les souris qui se désolent de mes disgressions sur ces réalités sordides, alors que le sujet de notre article est d'un tout autre ordre, et qu'il serait temps de retrouver l'humeur pimpante et légère qui sied à un article écrit par de mignonnes petites souris vertes. De quoi parlons-nous réellement aujourd'hui, d'ailleurs ? Ah oui, c'est vrai, nous devions lancer un appel solennel et unanime à faire-le-soi-même son propre code avec ses petits doigts potelés, au lieu que de sans arrêt le déléguer à autrui qui l'avions écrit pour nous. Bon, cette introduction étant décidément sans espoir, et devant l'air navré des souris qui voient leur beau propos partir en sucette verbale, changeons vite de paragraphe pour nous racheter une conduite et un style, et rentrer dans le vif du sujet. En avant, marche !



Surtout ne fais rien, je m'en occupe pour toi


Cette belle proposition est le mantra de l'informatique moderne. Tout est donc organisé pour qu'aujourd'hui le développeur écrive de moins en moins de code, et passe donc ses journées à se gratter la tête pour comprendre comment réutiliser du code écrit par d'autres, ou à comprendre comment appeler le gentil service web qui est censé lui répondre en une nano seconde ce qu'il aurait mis trois jours à calculer par lui-même. Ce qui lui prendra parfois 5 jours d'analyse, allez comprendre.


Les promesses implicites qui justifient la multiplication de ces pratiques sont les suivantes :

- ceci permet de gagner du temps et de ne pas "réinventer la roue" à chaque petit problème qu'on rencontre

- ceci permet de bénéficier de code efficace, robuste et ultra-validé

- ceci permet de faire du code plus simple à maintenir sur la durée : le Gentil Développeur dont je reprends le code maintient sa petite fonctionnalité de son côté, je n'ai qu'à maintenir les 3 lignes de code qui l'appellent du mien, et en plus je bénéficie de toutes les avancées de son travail gratuitement et sans supplément. Le rêve !


Alors effectivement, si tout ceci était vrai partout et en toutes circonstances, l'équipe des Souris Vertes serait depuis longtemps en train de s'égayer dans les bois plutôt que d'écrire cet article inutile. Malheureusement, comme souvent ces promesses n'engagent que ceux qui y croient, et la réalité quotidienne de la tâche ingrate que l'on appelle "intégration" en informatique, par opposition au développement pur, et qui est un mot délicat pour signifier faire-rentrer-au-chausse-pied-ce -code-pas-de-moi-et-qui-ne-fait-pas-vraiment-ce-que-je-veux, est toute autre.


Permettons nous donc de reprendre un par un les points que nous avons cités, pour en dévoiler la face lunaire sombre et inquiétante.


Promesse 1 : plus de moins de temps


Disons le tout net, le gain de temps effectif est le plus souvent une vaste blague, car généralement plus le code à intégrer est complexe ou dense, plus la phase d'apprentissage pour se l'approprier et lui faire faire ce que l'on souhaite est longue. On peut ainsi passer des jours, des semaines ou même des mois à éplucher une documentation indigente ou à essayer de deviner le comportement de certaines fonctions par essai-erreur, voire en lisant directement le code source. Bref, le gain de temps sera très variable en fonction de la manière dont le code a été conçu et documenté, et de son adéquation à notre besoin initial. Ce qui est certain, en revanche, c'est qu'au lieu de passer vos journées à programmer, vous allez passer vos journées à décortiquer des documentations ou du code structuré de manière peut-être très différente de vos propres habitudes, ou bien à exécuter des bouts de programme dans le brouillard jusqu'à y voir plus clair. Il y en a peut-être qui adorent passer leurs journées de travail à ce genre de sport, personnellement ceci me rend instantanément mort d'ennui et le regard rivé à la fenêtre en regrettant de ne pas être ailleurs avec mes copines souris.


Promesse 2 : on ne va pas réinventer la roue, allons donc


En ce qui concerne ce fameux adage que j'ai moi-même entendu tant de fois s'agissant de produire du code informatique, eh bien personnellement aux souris vertes on ne voit pas trop le problème. Quand bien même on écarterait le fait que bien souvent, c'est une roue carrée ou carrément crevée qu'on essaie de vous refourguer discrètement, il est toujours plus épanouissant pour une personne de savoir inventer une roue par elle-même (vous sauriez le faire, vous ?) que de regarder quelqu'un d'autre le faire à sa place. A vrai dire, quand on regarde la société dans son ensemble, on voit vite que la plupart des gens passent précisément le plus clair de leur temps de travail à faire des choses redondantes ou superflues, la seule manière possible de garantir  qu'autant de gens doivent s'astreindre à pointer 40 heures par semaine alors que des millions de machines font le plus gros du travail à notre place. Le chef de projet qui vous enjoint d'arrêter de programmer vous-même votre petite fonction ne passe-t-il pas son temps à faire exactement la même chose que des milliers d'autres personnes dans le monde sur des projets similaires ? Est-ce qu'on ne pourrait pas factoriser un peu sa fonction inutile, au lieu d'essayer de toujours factoriser le travail du développeur ?


Promesse 3 : testé et approuvé, puis retesté et réapprouvé


Ah, alors là oui, en effet, voici un argument de poids (boum). Quand on sait que tester du code est souvent bien plus long que de l'écrire, et même souvent inversement proportionnellement plus pénible, puisque 30 secondes de négligence d'un développeur peuvent coûter des journées entières de recherche de petite bête dans les rouages, on ne peut qu'être sensible à cette alléchante proposition. Et bien souvent elle sera honorée, si si, à condition tout au moins que l'on se tourne vers du code issu de projets sérieux et qui tiennent la route, car aujourd'hui le premier venu pouvant mettre à disposition de l'univers le moindre fichier qu'il vient d'écrire en 4 secondes sur un coin de table, la circonspection devra être de mise si l'on ne souhaite pas se faire refourguer de la vulgaire camelote encore plus buguée qu'un système d'exploitation grand public dont nous tairons pudiquement le nom.


Promesse 4 : plus rapide que l'éclair, et sans les brûlures


Ah c'est ici que le bât blesse, qu'il érafle, égratigne voire meurtit profondément notre petit programmeur confiant. Il est évident qu'avec tout le temps investi par d'autres sur ce code que j'essaie de reprendre, il va être d'une efficacité redoutable, bien plus rapide que ce que j'aurais pu écrire avec mes dix doigts tout seul dans ma cave.


Malheureusement, lorsqu'il (ou ils, parfois un petit code cache une armée de programmeurs tapis derrière les tapis...de souris) a écrit son code magique, notre ami anonyme n'avait aucune idée du contexte dans lequel vous alliez vouloir vous en servir. Autrement dit, à moins que vous ne repreniez un morceau de code qui fasse exactement, mot pour mot et à la virgule près ce que vous souhaitiez, eh bien il sera sous-optimal pour votre besoin. Très souvent, le problème vient justement du fait que le programme veut traiter tous les cas qu'il imagine que les gens vont rencontrer, donc il devient générique, complexe et bourré de traitements inutiles pour l'utilisation très limitée que vous vouliez en faire.


Supposons par exemple que vous aimeriez trouver une petite librairie qui permette d'appliquer une rotation sur une image au format JPEG (je ne vous demanderai pas pourquoi vous cherchez quelque chose d'aussi tordu, à chacun ses loisirs). Il est probable que vous allez trouver tout un tas de librairies de traitement d'image qui permettent de faire plein de belles choses, dont justement la rotation. Et probablement elles traiteront tous les formats d'images disponibles dans l'univers. C'est très bien, seulement la rotation que vous souhaitiez appliquer consiste peut-être en 5 lignes de code, quand vous allez reprendre des dizaines de milliers de lignes de code qui ne vous serviront à rien, et appliquer une méthode dont vous ne maîtrisez pas les performances et la consommation de ressources. Faut-il alors utiliser la Super Librairie ? Nous laissons cette discussion pour le dernier paragraphe passionnant de cet article. 


Gardons tout de même bien en tête que le seul code vraiment optimal ne peut être écrit que par quelqu'un qui connaît toutes les contraintes et le contexte d'exécution, autrement dit vous, cher programmeur-lecteur. Et il y a dans la jungle informatique des bêtes féroces qu'il faudra absolument éviter de croiser, car elles vont plomber votre empreinte écologique programmatique à jamais, j'ai nommé les Gros Frameworks Qui Font le Café (alors qu'en plus en général on voulait seulement un petit chocolat). Ces bases de code tentaculaires sont généralement des monstres écrits pour garantir que le programmeur qui chausse du 47 ne programme pas trop Avec Ses Pieds, et donc lui imposer plein de contraintes et d'outils tout faits, résultat c'est le framework lui-même qui se charge de mettre les performances par terre au lieu du développeur qu'on pressentait peu scrupuleux.


De deux choses l'une : soit vous vous dites que vous savez programmer, et vous n'avez pas besoin d'un framework De La Mort. Même si vous programmez en équipe, deux ou trois conventions décidées ensemble suffiront à garder la cohérence de votre projet, sachant une fois encore que le framework n'a aucune idée de ce que vous allez programmer et donc ne vous aidera pas franchement à structurer le code intelligemment. Soit vous pensez que vous programmez comme un manche, et ce n'est pas le plus beau framework de la terre qui va vous sauver ; dans ce cas restez loin du clavier et allez plutôt faire un peu de jardinage, vous ferez moins de mal à la planète.



Promesse 5 : il n'y a plus qu'à le regarder grandir


Voilà, vous avez repris le petit, ou gros, ou Super Gros, bout de code qui vous manquait, et maintenant vous êtes sûr qu'en plus vous êtes tranquille pour les 10 prochaines années, le projet va suivre les évolutions et vous bénéficierez des nouveautés neuves gratuitement et sans aucun effort. Hum. Ceci, encore une fois, est vrai dans le monde enchanteur de Oui-Oui, mais un peu moins dans la forêt vierge des projets informatiques modernes. Car en effet, il n'est pas rare de rencontrer l'un des trois événements qui déciment nos attentes en la matière :

- les gens désertent, le projet s'arrête, plus d'évolution de rien du tout, vous voilà marron si jamais les besoins continuent d'évoluer (comme une évolution du standard JPEG pour reprendre notre petit exemple, même si c'est tout de même assez peu probable).

- pire, les gens se disputent et le projet continue, mais un autre groupe décide de faire un nouveau développement (ce qu'on appelle un branchement, ou un fork, "Si t'es pas content tu forkes", comme on dit dans le milieu). Que faire ? Qui a raison ? Qui est vilain ? Un vrai casse-tête.

- le pire du pire, tout d'un coup le ou les programmeurs décident que rien ne va plus et changent tout le fonctionnement de leur code, aucune compatibilité gardée, bref votre intégration part illico à la poubelle, et il vous faut remettre le métier sur son ouvrage à un moment où vous auriez bien d'autres choses à faire. Ah mais vraiment je vous jure.


Il faut donc un minimum de circonspection quand on choisit d'intégrer du code de projets externes, même s'ils présentent toutes les garanties de sérieux et d'intégrité, comme en atteste la destinée chaotique de projets open-source phares comme OpenOffice, Mysql, ou Gnome. Et on pourrait multiplier les exemples à l'envi.



Coder ou ne pas coder, telle est la question


"Dilemme de la proie

Fuir

Ou se cacher ?"


Midoriro no Mausu (la Souris Verte)

Bien bien, rendus à ce point de notre discussion, il est temps de se demander sans détour : faut-il, oui ou zut, utiliser du code écrit par d'autres, intégrer des applications tierces, utiliser des librairies externes ? Alors ? Les souris ? Ah, je vois qu'on a une réponse à ma droite : oui et non. Euh, super, merci les souris vraiment. Qu'est-ce que je vais écrire aux lecteurs qui défaillent d'impatience, avec ça ? D'accord, on me précise la réponse, on peut réutiliser du code dans les cas suivants :

- le projet donne les garanties de sérieux et de stabilité qui ne nous demanderont pas d'y remettre un jeton toutes les 2 semaines

- le code n'est pas trop complexe à utiliser, et est suffisamment documenté pour notre usage

- notre besoin de performance n'est pas énorme, en particulier nous ne souhaitons pas faire 10 millions de rotations d'images JPEG par seconde avec la librairie Lambda que nous avons trouvée

- le code que nous avons trouvé constitue une fonctionnalité simple et bien délimitée, il ne cherchera pas à faire le café à notre place


Il faut surtout savoir doser son effort : inutile de mettre de l'enjeu à recoder tout un truc compliqué s'il existe déjà par ailleurs et que vous n'en faites qu'une utilisation très anecdotique. Il existe même quelques cas où, très honnêtement, il serait suicidaire de se lancer dans une réimplémentation personnelle de certains algorithmes, sauf si vous aimez vous lancer des défis : toutes les librairies cryptographiques, les prises en charge de protocoles tordus dont la définition fait 2500 pages, etc.


En revanche, il reste un cas où il faudra presque toujours y aller par vos propres petits moyens personnels et à la lampe torche, c'est si votre code est destiné à être utilisé de manière intensive et qu'il constitue le maillon faible des performances de toute votre application. Comme dit précédemment, si vous devez implémenter 10 millions de rotations d'images JPEG par seconde, il n'y a pas, il va falloir vous retrousser les manches, et faire votre code de manipulation d'images aux petits oignons pour que pas un octet ne dépasse du processeur. Mais, franchement, n'est-ce pas ce qui rend la programmation si passionnante ? Qui pourrait préférer passer ses journées à réutiliser des API GoogleBook toutes faites au lieu de répondre à cet appel du monde sauvage de la programmation débridée ?



Bien programmer sa conclusion


Vous l'avez compris, aux Souris Vertes nous sommes loin de trancher systématiquement en faveur du code tout-fait-tout-prêt à être enfourné au micro-ondes, ou du code super custom fait par nos petits doigts agiles. N'en déplaise aux tenants de la solution de facilité de ne pas se poser de questions, il faudra toujours se la poser, la question, éventuellement revenir sur ses propres choix, et user de tact et de raffinement pour construire le meilleur compromis possible sans sacrifier la banquise au passage. En particulier, essayer d'enrayer un peu le report systématique de certains framework ou librairies ultra-gourmands mais que tout le monde se refile comme si c'était l'évangile ferait du bien aux ours polaires.


A vous de jouer maintenant ! Cela dit, si vous restez sur votre faim de vrais conseils de programmation concrets qui vous parlent de votre quotidien au moins autant que l'édition régionale du journal télévisé, ne vous éloignez pas trop, car lui suite de notre dossier promet de décoller vers des sommets vertigineux en la matière. On se retrouve dès que vous aurez retrouvé votre plus belle combinaison spatiale, et qu'on aura de notre côté fini de tailler nos crayons de couleur. A suivre !

>Voir le billet et ses commentaires...
 

La Programmation Responsable (2) : de ricaner en cours d'algorithmique tu arrêteras
Date 04/11/2017
Ico Dossier
Comms Aucun commentaire


"Devrait-on rire ou pleurer

Quand ma belle-de-jour

Se fane ?"


Matsuo Bashõ (1644-1695)


On entame aujourd'hui notre belle croisière dans les eaux de la programmation estampillée souris verte, et sans se prélasser sous les cocotiers, on franchit tout de suite le Cap Horn en bravant la tempête, et en attaquant de front et par vent de face le sujet le plus austère de tout le dossier, j'ai nommé l'Algorithmique. Rien qu'à lire ce mot, je vous vois plisser des yeux, mais qu'est-ce que c'est que ce truc ? C'est bien simple, sa seule mention fera sortir aussitôt de la salle tout étudiant en informatique qui n'est pas assoupi, ainsi sans doute que des hordes entières de lycéens qui sont désormais sommées de se farcir une version édulcorée de cette matière peu réjouissante.


Car oui, bien qu'on nous rebatte les oreilles à longueur de journal télévisé sur les merveilles réalisées par les incroyables algorithmes qui changent le monde, il ne se trouve pas grand monde en vérité pour défendre cette science des algorithmes qui exerce le même entrain guilleret qu'une marche funèbre sous un crachin hivernal. Les algorithmes changent peut-être le monde (inutile de me mordiller l'orteil, chère souris sous le bureau, nous remettrons la discussion de ce point à un autre article percutant, pour aujourd'hui on tient notre cap), mais c'est avant tout en distillant un ennui profond à notre jeunesse désabusée. Et alors ? L'informatique n'est-elle pas censée être ludique ? Où sont les couleurs qui clignotent, les rires qui fusent, les images qui percutent ?


Eh bien non, c'est malheureux, vraiment, mais l'algorithmique appartient à la face cachée théorique de l'informatique, avec par exemple la logique qui est une autre matière qui fait bien mal au slip, pour le dire poliment, mais qu'on passera sous silence pour ne pas achever de terroriser nos lecteurs. Donc, effectivement, on ne s'amuse pas autant en cours d'algorithmique qu'à programmer Lance Ton Pingouin sur son téléphone mobile, et pourtant c'est un prérequis fondamental à tout programmeur digne de ce nom, c'est-à-dire tout programmeur qui souhaite maîtriser la Programmation ResponsableTM et sauver la planète tous les jours devant son clavier.


Allez, on plonge tout nu dans le grand bain glacé, puisque c'est pour notre bien et celui de l'humanité. Snif.



Avoir le sens du algorithme


Mouais, les souris, on nous enjoint d'aller en cours (un scandale !), mais encore faudrait-il nous dire ce qu'on est censé y apprendre, vu que le prof a l'air de débarquer directement de l'espace et de parler dans un patois martien que même les petits hommes verts (tiens, tiens, nos copains de l'autre bout du système solaire seraient-ils des écologistes convaincus ?) doivent avoir du mal à suivre. On y vient, justement. L'algorithmique est la science des algorithmes. Donc on y apprend des algorithmes. Et voilà ! Bon, ne partez pas, on va essayer d'en dire un peu plus quand même.


Tout d'abord, qu'est-ce qu'un algorithme ? Bigre, la souris verte à lunettes a levé le doigt avant même que je n'aie commencé à formuler ma question. Quelle fayote celle-là, vraiment. Allez, on lui laisse la parole : "un algorithme est une séquence ordonnée d'instructions dans un langage compréhensible par un humain, ou une souris". Pas mal, même si on aura du mal à garantir que TOUS les humains (ou toutes les souris aussi d'ailleurs) seront capables de le lire, puisqu'il faut tout de même maîtriser un minimum le vocabulaire utilisé pour décrire les instructions, qui peut être assez spécialisé.


En tout cas il y a quelques caractéristiques de notre algorithme qu'il faut souligner :

- il doit être sans ambiguité, donc si deux personnes le mettent en oeuvre, le résultat doit être rigoureusement le même.

- les instructions sont bien des notions élémentaires manipulables par un être humain, pas par une machine, donc il y a un certain niveau d'abstraction par rapport à la programmation, pas question de sombre manipulation d'octet ou d'adressage mémoire ici.


A vrai dire, que vous soyez chamois d'or de la programmation acrobatique ou simple citoyen, vous avez déjà eu maille à partir avec pas mal d'algorithmes dans votre vie, et tel monsieur Jourdain qui fait de la prose sans s'en rendre compte, vous mettez en oeuvre des algorithmes quasi quotidiennement, en ignorant simplement de le savoir. Suivre une recette de cuisine, participer à un exercice incendie, même conduire en respectant le code de la route, tout cela peut plus ou moins être associé à la mise en oeuvre d'algorithmes dans des domaines divers. Pour rester dans un domaine un poil plus scientifique, l'addition posée que vous avez apprise à coup de baguette sur les doigts dans votre enfance est un bel exemple d'algorithme mathématique. Si vous appliquez à la lettre les instructions, vous réalisez votre opération sans faillir, que vos nombres aient 2 chiffres ou bien 300.


On voit tout de suite une des raisons de la désaffection pour la matière pointer son nez : l'application d'un algorithme est totalement mécanique, et on ne pourra pas se féliciter de bien d'autre chose que d'être un gentil petit robot si on le met en oeuvre avec brio. C'est d'ailleurs la raison pour laquelle on cherche à déléguer un maximum de ce travail fastidieux à nos amis les ordinateurs. Bien que la répétition de certaines tâches ait une vertu pédagogique indéniable, et soit partie intégrante de l'apprentissage, il est clair que si l'on reste strictement cantonné à l'exécution d'algorithmes, on va vite sombrer dans une déprime et une apathie généralisées. Non, l'intérêt de l'algorithmique est de concevoir des algorithmes, ce qui est une autre paire de manches et nous fait tout de suite basculer du côté de l'intuition et de la créativité les plus débridées.


Et à vrai dire, même si tu te cures le nez en affichant un air de profond ennui devant nos propos, cher lecteur-programmeur, de l'algorithmique tu en fais, en fis et en feras que tu le veuilles ou non. Car qu'est-ce que c'est finalement que d'écrire un programme informatique, sinon enchaîner une série d'algorithmes qui résolvent chacun à leur manière un petit problème isolé ? Je dois isoler une valeur au milieu d'un gros tas de données ? Je dois traiter une information en provenance d'un utilisateur ? Je dois calculer comment afficher correctement un texte à l'écran ? Que des algorithmes, tout cela. Les seules questions qui se posent sont : est-ce que j'écris mes propres algorithmes, ou est-ce que j'utilise ceux des autres ? Est-ce que je maîtrise leur impact en terme de temps de calcul et de ressources machine utilisées ?



Ne soyons pas trop décomplexés


Avec toutes ces belles considérations, on n'a pas encore vraiment dit ce que l'on apprenait concrètement dans notre cours de gymnastique algorythmique  (sans les collants ridicules, vous voyez qu'il y a du bon dans cette matière tout de même). En général, on étudie des classes d'algorithmes existants de plus en plus complexes, et si tout va bien on apprend comment concevoir les nôtres. On commence par exemple par trier des tableaux dans tous les sens (une grande joie du programmeur débutant, l'équivalent du rite initiatique dans les sociétés traditionnelles), et quand on devient Jedi on peut étudier les algorithmes super monstrueux utilisés par GoogleBook pour coloniser l'internet mondialisé.


Mais surtout, surtout, surtout, on apprend à évaluer les performances d'un algorithme, et c'est bien ce à quoi nous voulions en venir, la compétence clé du Programmeur Responsable qui a son petit badge couleur éméraude. Ce que nous enseigne l'agorithmique, c'est que toute méthode doit être évaluée non par le temps qu'elle prend (qui dépend de conditions locales d'exécution qui peuvent varier), le nombre de litres de pétrole qu'elle consomme ou son signe zodiacal, mais par sa complexité, qui est un ordre de grandeur du nombre d'instructions réalisées en fonction de la taille des entrées de ladite méthode. Et oui, les souris, je sais bien que c'est formulé de façon aussi claire que le fond du ruisseau saturé de boues d'épandage qui court à côté de notre jardin. On va tâcher de prendre un exemple pour éviter de se fouler le néo-cortex.


Attention, cependant, rien à voir avec la soi-disant complexité du monde réel qu'on invoque à toutes les sauces pour nous demander poliment de passer notre chemin et nous signifier de laisser penser les éditorialistes parisiens à notre place, ici il s'agit d'une théorie tout ce qu'il y a de plus sérieux et et scientifique. La complexité ne désigne pas les profondeurs insondables d'une pensée qui nous échappe, pauvres mortels débiles que nous sommes, mais la complexité en nombre d'étapes de calculer un résultat pour une machine qui ne dispose que d'opérations élémentaires pour le mener à bien.


Avant d'aller plus loin, je sens qu'il est urgent d'opérer une petite pause contemplative salutaire, méditons donc un instant sur un petit haïku : 

"Si difficile

De dire ce que voit

Cette souris tournée vers moi"


Midoriro no Mausu (la Souris Verte)


Notre vraiment super exemple


Ouf. Puisque nous voici à nouveau frais, dispos, et prêts à en découdre avec les concepts les plus tarabiscotés, revenons à nos moutons virtuels et à notre fameuse complexité, et prenons un exemple issu de la Vraie Vie, comme on dit dans les salons. Donnons nous par exemple la tâche bien utile de dénombrer les feuilles d'un arbre. Pours nos lecteurs qui passent trop de temps devant un écran à coder et ne savent pas ce qu'est un arbre, nous les enjoignons à sortir prendre un peu l'air jusqu'à apercevoir un grand truc marron en bas, et vert au dessus qui semble pousser dans le sol, ou à tout le moins à se renseigner sur internet.


Bon, comptons donc. Ca paraît bête, comme cela, mais déjà trouver une méthode qui permette de le faire sans se tromper n'est pas si aisé, vu que vous avez pu remarquer qu'un arbre n'a pas forcément une structure bien régulière, qu'il y a des feuilles dans tous les sens, et en plus s'il y a du vent au secours. Si l'on suppose que l'on a quand même accès à toutes les feuilles, quitte à se munir d'une échelle bien costaude, il va falloir se débrouiller pour ne pas perdre le fil et ne pas compter les mêmes feuilles plusieurs fois.


Une bonne idée pour ce faire nous est donnée par le professeur Souriso lui-même, qui adore ce genre d'expérience : on compte une feuille, puis on fait une petite marque (discrète et qui partira à l'eau de pluie, hein, on n'est pas des sauvages) pour ne pas la compter à nouveau. On continue à énumérer les feuilles de l'arbre jusqu'à ce que toutes les feuilles soient marquées, et zou, on a notre total.


C'est formidable, mais il ne vous aura pas échappé que ceci risque de prendre un certain temps, voire un temps certain, et de vous faire mourir d'épuisement avant d'arriver même à la moitié du quart du dixième de votre tâche. Peut-on optimiser un peu notre algorithme, avant d'y passer notre vie ? Cest là que le Programmeur Lambda, celui qui n'a pas suivi de cours d'algorithmique ou y a trop roupillé pour en avoir retiré quelque chose d'utile, va se tourner vers la solution standard de l'informatique en panique : on offre une paire de lunettes à la personne qui fait le décompte, ou bien on lui donne une échelle plus longue, ou même une paire de jumelles si on ne compte pas à la dépense. Bref, on augmente le matériel. Pour un vrai programme informatique on mettra plus de mémoire, un plus gros disque, du SSD, etc. Super, mais vous voyez qu'au lieu d'y passer 107 ans, notre fidèle collaborateur en passera 105 ou 106, bref c'est bien gentil de votre part mais ça ne résout strictement rien.


Qu'à cela ne tienne, on va sortir les grands moyens et paralléliser les calculs, on va mettre non pas une, mais deux personnes qui comptent. Et bim ! C'est aussi une très belle promesse, mais il faut compter que les deux personnes vont se marcher un peu sur les pieds, donc on n'ira pas strictement deux fois plus vite. Mais même comme ça, on mettra 50 ans environ, c'est mieux mais pas franchement jouable quand vos crédits de recherches sont alloués sur 10 mois. Et même en mettant 10 personnes en même temps, bof bof, vous restez toujours avec le même ordre de grandeur, donc si c'était franchement impossible ça deviendra juste-un-peu-moins-impossible mais toujours pas raisonnablement réalisable. Donc ici encore, la fameuse méthode de la parallélisation, si souvent dégainée pour se sortir d'une ornière informatique, outre qu'elle demande un doigté particulier dans la manière de programmer sans se prendre des problèmes de processus concurrents à tous les étages, ne fera jamais gagner significativement en performance.


Deux solutions s'offrent alors à nous : soit on renonce à notre projet, en le repoussant à une époque où la technologie viendra nous aider à le résoudre en un temps raisonnable (avec un ordinateur quantique, pourquoi pas ? On peut toujours rêver), soit on sort une feuille blanche, sa plus belle plume et on change d'algorithme pour réduire sa complexité.


Ici, une suggestion tout à fait passionnante d'une souris débrouillarde nous permet de nous sortir d'affaire : on simplifie le problème, en fait on ne veut pas vraiment le nombre exact de feuilles dans notre arbre, une bonne estimation nous suffira. Nous allons donc estimer le nombre de feuilles sur une branche, et simplement compter le nombre de branches au lieu du nombre de feuilles. Et il y en a beaucoup beaucoup moins, c'est l'affaire d'une heure tout au plus. Et voilà comment un travail qui aurait pu nous prendre jusqu'à l'extinction du soleil est terminé en une petite après-midi de travail, sieste incluse.


Dans notre petit exemple, nous sommes passé d'une complexité qui était proportionnelle au nombre de feuilles dans l'arbre, à une complexité proportionnelle au nombre de branches dans l'arbre. Alors ici c'était facile, mais il n'est pas toujours facile de calculer la complexité d'un algorithme, et encore moins de la faire baisser ; surtout quand ledit algorithme avance masqué dans plusieurs milliers de lignes de code qui semblent parler d'autre chose que de ce que vous raconte le prof martien.


Mais une valeur sûre pour repérer de la complexité sauvage et déchaînée est de repérer de multiples structures de boucles imbriquées dans un programme. Pour chaque niveau de boucle, hop, un ordre de grandeur supplémentaire. Et se souvenir aussi que le meilleur endroit pour améliorer les performances est TOUJOURS au milieu du code et de la logique qu'il déroule, et non dans les solutions de facilité de toujours plus de matériel, ou encore de programmes tiers censés booster les performances, comme des systèmes de cache tout-terrain qui ne savent pas sur quoi ils travaillent, et n'amélioreront donc jamais la complexité intrinsèque d'une méthode.



Savoir s'abstenir de ne pas faire


S'il y a une chose que nous enseigne l'algorithmique et qui doit nous marquer à vie, c'est que ce n'est pas parce que l'on sait écrire un programme qui résout une certaine tâche que l'on est capable de le mettre en oeuvre. Je peux écrire un programme qui sait calculer la factorielle d'un nombre à 130 chiffres, qui fera les mêmes trois lignes que pour la factorielle de 5, mais il n'a aucune chance d'aller jusqu'au bout, vu qu'il lui faudra réaliser plus d'opérations qu'il n'y a d'atomes dans l'univers.


Aussi, si on me demande d'écrire un tel programme, je me dois de refuser car ce serait un gaspillage de ressources éhonté pour un résultat qui n'a aucune chance d'aboutir. Et toi aussi, ami programmeur, refuse de mettre en oeuvre des méthodes à la complexité trop élevée : soit tu trouves une meilleure façon de procéder, soit on dit au client, tant pis, il n'a qu'à se trouver des besoins plus modestes auxquels l'informatique saura répondre sans y sacrifier l'énergie d'une supernova.


Précisons tout de même que toutes ces considérations ne s'appliquent que lorsque l'on traite un volume conséquent de données ; en fonction du type de traitement que l'on cherche à faire, on commencera à se poser de sérieuses questions de complexité au-delà de 1000 à 10000 entrées à gérer d'un coup. En deçà, on peut bien se permettre de privilégier une programmation simple, naturelle et sans nécessité de stockage massif de boîtes d'aspirine sous le bureau.


Et dans le cas où il nous faut optimiser les performances d'une application, on procèdera toujours dans l'ordre d'efficacité croissant, en appuyant d'abord là où ça peut faire le plus de différence :

1 - on étudie complexité générale du ou des algorithmes sous-jacents, et on essaie d'améliorer cela. Plus facile à dire qu'à faire, n'est-ce pas.

2 - on applique les formidables conseils qui vont suivre dans ce dossier, et on optimise donc en particulier les appels aux bases de données, aux disques, etc.

3 - on utilise un système de cache ou des outils d'optimisation de code écrits par d'autres. Si on est en rendus là, c'est que soit on est désespéré, soit on a déjà atteint un niveau d'optimisation tellement énorme qu'on ne peut plus rien faire simplement au niveau du code.

4 - on rajoute des ressources matérielles, et, si on le peut, on parallélise les étapes qui prennent le plus de temps. Ca c'est la solution qui apporte le moins de gain pour le plus de ressources consommées, autant dire qu'on ne la dégainera qu'à bon escient.



Une lueur d'espoir au fond du tunnel


Bon, disons le tout net, il est bien difficile de comprendre quel algorithme vous mettez en oeuvre quand vous programmez au quotidien, même si vous faites à votre insu des parcours d'arbres ou de graphes, des tris de tableaux, etc. Autrement dit, à moins que vous n'ayez une application très spécialisée qui fait du calcul intensif De Maboul, par exemple une méthode d'apprentissage sur un grand nombre de données, vous aurez peu de chances d'arriver à utiliser directement les notions algorithmiques chèrement  apprises. Il n'en reste pas moins qu'elles sont essentielles pour donner des points de repère, et surtout pour vous faire sentir à quel point la méthode de programmer tout ce qui vous vient à l'esprit sans jamais analyser le nombre d'opérations en jeu est délétère, et à l'origine d'une part non négligeable de ces superbes applications Programmées Avec Les Pieds (TM) qui font tant ramer nos belles puces de silicium.

Mais, pour être tout à fait honnête, vous vous en sortirez très bien sans un doctorat en algorithmique si vous mettez en oeuvre les petites astuces et mises en garde qui vont suivre dans cet épatant dossier. Alors surtout ne ratez pas la suite !

D'ici là, nous avons tous gagné le droit à une bonne promenade automnale sous les feuilles d'arbre qui tombent (non non, vous n'êtes pas obligé de les compter). Youpi !









>Voir le billet et ses commentaires...
 

1 2 3

Infos blog

Des Souris Vertes

Derniers billets

Le Petit Geste du Jour   05/01/2018
Les 5 gestes totalement vraiment incontournables de l'écologie numérique
Le Petit Geste du Jour   22/12/2017
Le Petit Geste de Noël : je ne renouvelle pas ma panoplie numérique
Dossier   16/12/2017
La Programmation Responsable (6) : des sites webs écologiques tu concevras
Dossier   07/12/2017
La Programmation Responsable (5) : les structures de données tu maîtriseras
Dossier   28/11/2017
La Programmation Responsable (4) : de spammer ta base de données tu cesseras
Dossier   18/11/2017
La Programmation Responsable (3) : de déléguer la programmation tu éviteras
Dossier   04/11/2017
La Programmation Responsable (2) : de ricaner en cours d'algorithmique tu arrêteras
Le Petit Geste du Jour   24/10/2017
Le Petit Geste Du Jour : je nettoie ma boîte de messagerie
Dossier   16/10/2017
La Programmation Responsable (1) : Ce dossier tu liras
Réseau   05/10/2017
Mes données dans le cloud : écologique ou pas ?
Dossier   26/09/2017
Au secours, mon ordi est lent ! (8) : J'apprends à reconnaître et changer le matériel
Le Petit Geste du Jour   10/09/2017
Le Petit Geste De La Rentrée : j'arrête le streaming
Divers   25/05/2017
Les souris vertes s'invitent à la radio
Le Petit Geste du Jour   20/05/2017
Le Petit Geste Du Jour : je change les réglages de mon appareil photo
Dossier   11/05/2017
Au secours, mon ordi est lent ! (7) : Je réinstalle mon système tout seul comme un grand
Le Petit Geste du Jour   06/05/2017
Le Petit Geste Du Jour : j'écris un haïku pour me détendre
Divers   14/04/2017
Cultiver l'attente...
Club de lecture   25/03/2017
Les souris vertes ont lu pour vous : la convivialité d'Ivan Illich
Le Petit Geste du Jour   09/03/2017
Le Petit Geste Du Jour : j'enlève la signature automatique des messages
Polémiquons   27/02/2017
L'inquiétant mariage de la science et du numérique
Dossier   17/02/2017
Au secours, mon ordi est lent ! (6) : J'adapte mon système à mes besoins
Club de lecture   12/02/2017
Les souris vertes ont lu pour vous : une question de taille, d'Olivier Rey
Le saviez-vous ?   21/01/2017
Le saviez vous ? La voiture est un ordinateur sur roues
Dossier   10/01/2017
Au secours, mon ordi est lent ! (5) : J'apprends à ne pas perdre mes données
Dossier   30/12/2016
Au secours, mon ordi est lent ! (4) : Je nettoie Windows à grands jets
Polémiquons   23/12/2016
Le Petit Geste de l'Année : je ne commande rien d'électronique au père noël
Le Petit Geste du Jour   11/12/2016
Le Petit Geste Du Jour : j'utilise un bloqueur de publicités
Dossier   27/11/2016
Au secours, mon ordi est lent ! (3) : J'apprends à ne pas polluer mon ordinateur
Dossier   14/11/2016
Au secours, mon ordi est lent ! (2) : Je dégage l'antivirus à coup de pied
Dossier   05/11/2016
Au secours, mon ordi est lent ! (1) : les souris vertes à la rescousse
Le Petit Geste du Jour   23/10/2016
Le Petit Geste Du Jour : j'utilise le mode avion même à pied
Système   16/10/2016
L'ordinateur portable est-il plus écologique ?
Le Petit Geste du Jour   02/10/2016
Le Petit Geste Du Jour : je gère la durée de vie de ma batterie
Club de lecture   17/09/2016
Les souris vertes ont lu pour vous : l'âge des low tech, de Philippe Bihouix
Système   21/08/2016
J'apprends à gérer mes mots de passe
Le Petit Geste du Jour   08/08/2016
Le Petit Geste Du Jour : j'arrête d'inclure les messages quand je réponds
Polémiquons   30/07/2016
Ecole et numérique font-ils bon ménage ?
Le Petit Geste du Jour   19/07/2016
Le Petit Geste du Jour : j'arrête d'écrire mes mails en HTML
Chamois d"or   10/07/2016
Le saviez vous ? Il est possible d'être informaticien sous Windows sans se pendre
Messagerie   04/07/2016
L'incarnation du mal : la pièce jointe dans les mails
Le Petit Geste du Jour   26/06/2016
Le Petit Geste Du Jour : Je réduis la luminosité de mon écran
Divers   18/06/2016
Stop à l'imprimante jetable
Dossier   12/06/2016
Grandeurs du monde numérique (6) : Réseaux en folie
Le Petit Geste du Jour   05/06/2016
Le Petit Geste du Jour : j'éteins ma box quand je ne m'en sers pas
Le saviez-vous ?   31/05/2016
Le saviez-vous : Google n'est pas le seul moteur de recherche ?
Dossier   25/05/2016
Grandeurs du monde numérique (5) : Dans la jungle des écrans
Le Petit Geste du Jour   20/05/2016
Le Petit Geste du Jour : je mets mes sites favoris... en favoris
Le Petit Geste du Jour   15/05/2016
Le Petit Geste du Jour : je change la page de démarrage de mon navigateur
Dossier   14/05/2016
Grandeurs du monde numérique (4) : Les spectaculaires performances des jeux vidéos
Le saviez-vous ?   12/05/2016
Le saviez-vous : à quoi sert l'économiseur d'écran ?
Dossier   08/05/2016
Grandeurs du monde numérique (3) : Monsieur Herz mesure la solitude du processeur
Dossier   06/05/2016
Grandeurs du monde numérique (2) : Octets et compagnie, les rois du stockage
Dossier   05/05/2016
Grandeurs du monde numérique (1) : c'est gros, c'est petit ?
Divers   04/05/2016
Les souris partent à l'aventure


MP  Mighty Productions
> Blogs
> Des Souris Vertes
 
RSS       Mentions légales       Comms  Haut de la page