Un rappel sur les algorithmes de tri

Un historique de toutes nos réunions

Table des matières

mercredi 10 octobre 2018

La voix du secrétaire (Jean)

Présents à la réunion, en fonction de la disposition autour de la table :

Emmanuel,
moi,
Sylvain,
Richard,
et Laurent (R).

Nous avons mangé des nems au poulet, un bo-bun, du saumon, de l'andouillette, du canard confit, un burger, une crème brûlée, des fondants au chocolat et un café gourmand. Nous avons bu un mojito, un panaché, un Orangina, un diabolo-menthe et du rosé.

Nous avons parlé de Perl, Internet informatique et points divers.

Perl

Ce soir, nous sommes peu nombreux à la réunion. C'est vrai qu'il n'y a pas eu de message de rappel. C'était déjà le cas pour la réunion IRC de la semaine précédente, il n'y a pas eu de message sur la liste adhérents pour rappeler la réunion et donner un ordre du jour. Du coup, il n'y a pas eu de discussion parmi les quelques personnes qui ont pensé à se connecter. Laurent (R) a pensé à la réunion pendant la journée, puis il a eu d'autres sujets d'occupation et à l'heure dite il a oublié. Il s'en est souvenu à 22h30 et il s'est dit que c'était trop tard. Effectivement, à cette heure nous avions clos la réunion.
Learning Perl 6 est enfin sorti. Nous avons tous reçu nos exemplaires électroniques. En revanche, pour les exemplaires papier, brian d foy est en rupture de stock et il en a envoyé seulement une partie. J'en ai bénéficié car, selon Emmanuel, je devais être parmi les premiers souscripteurs et brian d foy envoie les livres dans l'ordre des souscriptions. Notons que j'avais droit également mois après mois aux brouillons du livre, mais je n'en ai ouvert aucun.
brian d foy a envoyé un message à tous les souscripteurs qui ont eu un exemplaire électronique ou papier, pour dire en substance :
Vous avez très certainement tous lu le livre. Alors maintenant, je vous demanderai de donner votre avis sur les sites, O'Reilly, Amazon, etc.
Désolé, mais je n'ai pas encore commencé. J'ai une file d'attente importante de livres à lire et surtout, j'avais un livre de 900 pages en cours et je voulais le finir avant d'en entamer un nouveau. Laurent a commencé à le lire et il a été un peu déçu par la présentation de certains sujets comme le parallélisme.
À mon travail, j'ai une machine Windows sur laquelle j'ai, bien sûr, installé Cygwin. J'ai le paquet Cygwin pour Perl 5, mais je n'ai pas trouvé de paquet pour Perl 6. J'ai téléchargé et installé le paquet Windows natif au cas où. Puis j'ai pu constater qu'en créant le bon alias ou en ajoutant le bon répertoire au $PATH, je pouvais utiliser perl6 depuis le shell Cygwin. Il y a un hic, toutefois. Il y a longtemps, j'ai écrit un programme qui cherche un fichier texte dans une liste de répertoires, sur ma machine et sur les serveurs du réseau. Cela donne à peu près ceci :
```
my $fic = $ARGV[0];
my @rep = qw(  c:/rep1a/rep1b
               //serveur2/partage/rep2a/rep2b
               //serveur3/partage3/rep3a/rep3b
               c:/rep4a/rep4b/rep4c
);
my $fichier;
my $trouve = 0;
for my $rep (@rep) {
  $fichier = "$rep/$fic";
  if (-e $fichier) {
    $trouve = 1;
    last;
  }
}
```
Je l'ai traduit en Perl 6, ce qui donne :
```
my Str $fic = @*ARGS[0];
my @rep = <  c:/rep1a/rep1b
             //serveur2/partage/rep2a/rep2b
             //serveur3/partage3/rep3a/rep3b
             c:/rep4a/rep4b/rep4c
>;
my Str $fichier;
my Int $trouve = 0;
for @rep -> $rep {
  $fichier = "$rep/$fic";
  my IO::Path::Win32 $iopath .= new($fichier);
  if $iopath.e {
    $trouve = 1;
    last;
  }
}
```
Je n'ai aucun problème pour traiter les fichiers locaux que l'on trouve dans c:/rep1a/rep1b ou dans c:/rep4a/rep4b/rep4c mais lorsque les fichiers se trouvent sur le réseau dans //serveur2/partage/rep2a/rep2b ou dans //serveur3/partage3/rep3a/rep3b, mon programme Perl 6 ne les trouve pas. J'ai essayé plusieurs variantes, en remplaçant les « / » par des « \ » ou des « \\ », en jouant sur les types IO::Path::Win32 ou IO::Spec::Win32 mais rien n'y fait. Pourtant, la documentation de Perl 6 utilise un nom UNC comme exemple, laissant supposer que cela devrait fonctionner.
Sylvain reprend le sujet traité le mois dernier sur les questions et les remarques de ses stagiaires ou étudiants venant de Java et découvrant Perl. C'est ainsi qu'il a découvert que les programmeurs Java sont très attachés à leurs prototypes de fonctions. D'autre part, pour les paramètres d'une fonction, ils ne connaissent que le passage par position. Pour les fonctions recevant une douzaine de paramètres, certains programmeurs écrivent un paramètre par ligne, avec un commentaire en fin de ligne pour ne pas perdre le fil. Ils sont alors ébahis lorsqu'ils découvrent qu'en Perl 5 on peut passer un hachage ou une référence de hachage, ce qui permet de faire en quelque sorte un passage de paramètre par nom et de s'affranchir de l'ordre des paramètres lors de l'appel de la fonction.
Un autre point, c'est la détection du code mort. En Java, lorsqu'un return n'est pas suivi immédiatement d'une fin de bloc, mais qu'il y a d'autres instructions, le compilateur signale ces instructions comme étant du code mort et provoque une erreur de compilation. En Perl, ce n'est pas une raison pour arrêter la compilation, qui continue et est suivie par l'exécution. Pour éviter le problème du code mort, une idée consiste à ne pas mettre de point-virgule à la fin de l'instruction return. De la sorte, si l'on ajoute par inadvertance du code à la suite de cette ligne, cela provoquera une erreur de syntaxe. Un autre moyen de détecter en Perl 5 du code mort consiste à passer le programme dans B::Deparse et de comparer avec le source initial. [ Et pour les petits futés qui lisent ce compte-rendu, il était clair lors de la réunion que Sylvain excluait de la discussion les if et les unless postfixés, du genre :
```
  return 0 if $annee %   4 != 0;
  return 1 if $annee % 100 != 0;
  return 0 if $annee % 400 != 0;
  return 1;
```
]
Un des outils pous l'analyse d'un programme pour détecter les erreurs est le contrôle de type, destiné à éviter par exemple que l'on fournisse un entier là où l'on attend une chaîne de caractères. Ce contrôle de type peut être étendu dans certains langages, dont Perl 6, pour préciser que la routine attend « un entier entre 1 et 5 ». On peut même envisager que le contrôle de type aille plus loin. Soit la routine suivante :
```
sub addition(Int $x where 1 ≤ * ≤ 5, Int $y where 1 ≤ * ≤ 5) {
  return $x + $y;
}
```
alors le compilateur saura que le résultat est de type Int et que sa valeur est comprise entre 2 et 10 inclus, ce qui peut affiner les tests ultérieurs dans le reste du programme.
Le modèle objet de Perl 6 apporte un certain nombre de nouveautés, comme les rôles, qui sont des groupes de méthodes qui s'ajoutent aux méthodes fournies par la classe d'un objet. Une particularité : si deux méthodes provenant de deux rôles différents portent le même nom et si un objet est instancié avec ces deux rôles, alors le programme plantera à cause du conflit de nom entre les deux rôles. Il n'y a pas d'effet de masquage et d'occultation comme c'est le cas avec l'héritage multiple.
Si le modèle objet de Perl 6 est intéressant, celui de JavaScript est encore plus inhabituel. C'est un modèle objet sans classe. Un objet est instancié en fournissant la valeur de ses attributs et en fournissant les méthodes qu'il supporte. Ensuite, il est possible d'instancier un autre objet en « recopiant » le premier tout en alimentant ses attributs avec des valeurs différentes des attributs de l'objet pris pour modèle. Les deux objets ont alors quand même les mêmes méthodes, un genre d'héritage qui se manifeste d'objet à objet et non pas de classe à classe.
L'un des avantages importants de Perl 5, peut-être même le plus important, c'est la rétro-compatibilité d'une version mineure à l'autre (et même entre la version 4 et la version 5). Si quelqu'un a une bibliothèque de code de 90 000 lignes qui fonctionne depuis une décennie ou deux et s'il n'y a aucun bug ni aucune faille de sécurité connue, alors pourquoi changer ces 90 000 lignes ? Du coup, le développement de Perl 6 remet en cause cette attitude et le responsable de cette bibliothèque pourrait être amené à penser :
S'il faut tout réécrire pour passer de Perl 5 à Perl 6, alors autant tout réécrire en passant de Perl 5 à R ou à Python.
Donc, il se pourrait que Perl 6, ou le discours autour de Perl 6, favorise ou provoque un déclin de Perl, tant Perl 5 que Perl 6. Quant à réutiliser les modules Perl 5 dans des programmes Perl 6, il paraît que c'est possible mais j'ai essayé, je n'ai pas réussi. On peut espérer que le développement de nouvelles versions mineures de Perl 5 continuera longtemps et permettra à Perl 5 de garder sa place au soleil.
Ironiquement, Python souffre du même problème. Emmanuel, qui contribue au projet Fedora, a vu passer l'information disant que la maintenance de Python 2 s'arrêterait complètement en 2020, y compris les mises à jour de sécurité. Donc il faut que tous les paquets Fedora utilisant Python 2 soient revus pour utiliser Python 3 avant cette date. Et nombreux sont les contributeurs concernés qui déclarent qu'ils ne sont pas intéressés par une réécriture en Python 3, certains préférant même basculer vers un autre langage de programmation.
De passage à Glasgow au mois d'août, j'ai pu me procurer le livre de Laurent sur la programmation fonctionnelle en version papier. Je l'ai lu et j'avais l'intention de faire des commentaires que j'aurais transmis à Laurent. Hélas, pris par d'autres priorités, je n'ai pas pu mettre ces réflexions par écrit. Remarquons toutefois que le livre est bien plus facile à suivre que Higher Order Perl par Mark-Jason Dominus, ainsi que je l'ai dit précédemment.
Nous avons évoqué un programme de résolution de sudoku par une méthode originale, mais je ne me souviens plus laquelle. J'ai enchaîné en mentionnant un exposé d'Abigail où il expliquait comment résoudre un sudoku avec des expressions régulières. Quelqu'un ayant suggéré que cela devait être performant, j'ai cité la remarque d'Abigail concernant un sudoku 9×9,
Don't do this at home.
Cela nous a rappelé qu'Abigail était déjà connu pour avoir trouvé comment tester si un nombre supérieur ou égal à deux est premier en utilisant une expression régulière. Cela donne :
```
say "$n est premier" if ('1' x $n) !~ /^(11+)\1+$/;
```
Si vous voulez chercher à comprendre comment cela fonctionne, essayez plutôt avec cette version étendue :
```
if (('1' x $n) =~ /^(11+)\1+$/) {
  say "$n est divisible par ", length($1);
}
else {
  say "$n est premier";
}
```

Internet

Récemment, la Mairie de Paris a diffusé un clip vidéo servant de publicité contre ceux qui urinent n'importe où. Nous nous demandons comment classer cette vidéo avec un tel mauvais goût. Cela me rappelle avoir lu une information décrivant une peinture spécialement prévue pour provoquer un éclaboussement lorsqu'elle reçoit de l'eau ou une solution aqueuse.
Après avoir évoqué le salon OVH qui dure une seule journée, avec une keynote le matin et des exposés et des ateliers l'après-midi seulement, nous avons comparé les solutions d'hébergement par OVH avec celles d'Online. En gros, OVH a pour clients cibles des entreprises plutôt importantes, tandis que Online convient mieux pour les petites entreprises. À noter qu'avec Online, si vous avez réservé un serveur physique et non une simple machine virtuelle, vous pouvez éventuellement avoir l'accès physique à votre serveur. Comme cela, ai-je ajouté, on peut appliquer un autocollant au serveur.

Informatique

Nous avons parlé d'algorithmes de tri, tant pour des objets physiques que pour des données informatisées. Par exemple, le spaghetti sort, qui est un tri en O(n). Cela n'a rien à voir avec les goto, c'est un algorithme pour trier des objets filiformes, rectilignes et rigides comme des spahettis qui sortent de la boîte avant cuisson. Le tri consiste à tenir dans la main une poignée de spaghettis posés verticalement sur la table, à extraire du faisceau le spaghetti le plus long et à itérer le processus. La règle de O(n.log(n)) ne s'applique pas, parce que le fonctionnement de la vision humaine fait que de nombreuses comparaisons se font en parallèle.
De même, pour trier des cartes à jouer, la plupart des gens utilisent un tri par insertion ou éventuellement par sélection, qui est en O(n²) pour des données informatisées, mais en O(n) pour des objets physiques comme des cartes à jouer. Une fois, une seule fois, j'ai voulu trier des cartes avec un tri à bulles, le plus célèbre des tris en O(n²). J'ai craqué avant la fin du tri.
Pour trier des copies d'examen par ordre alphabétique des noms d'étudiant ou par ordre numérique des notes, il existe le tri par tas. Ici, le mot « tas » est au pluriel et ce tri n'a rien à voir avec le heapsort. On peut trouver des points communs avec le quicksort de Hoare et avec le merge sort. Dans un premier temps, on passe en revue toutes les copies, faisant un premier tas avec les noms en qr/^[ABC]/, un deuxième tas avec qr/^[DEF]/ et ainsi de suite. Dans un deuxième temps il faut trier chaque tas séparément (tri par sélection ou par insertion comme pour des cartes à jouer) et dans un troisième on fusionne les tas triés simplement en les empilant.
Laurent se demande à quoi est due la popularité du tri à bulles. Si l'on se contente d'un tri quadratique, le tri par insertion et le tri par sélection sont beaucoup plus simples et beaucoup plus naturels.
Et il y a les tris « pour rire », comme le bogosort. Ce tri consiste à mélanger les données en utilisant un générateur de nombres aléatoires correct, sans biais, puis à tester si le résultat obtenu est trié. Dans l'affirmative, on quitte la boucle, dans la négative on itère le processus. [ ce tri est en O(nⁿ) mais Randal Munroe a montré qu'on pouvait l'optimiser en O(n.log(n)) ]
Et il y a le sleepsort, que j'ai découvert dans un des livres d'Andrew Shitov. Cet algorithme traite les tableaux de valeurs entières positives pas trop grandes. Il passe en revue chaque élément du tableau et pour chacun, il démarre un fil d'exécution asynchrone (thread) avec :
```
{
  sleep @tabl[$i];
  say @tabl[$i];
}
```
Certes, comme il n'y a pas de garantie sur la durée réelle d'exécution d'un sleep, il est possible que le tableau ne soit pas parfaitement trié. Il suffit alors de refaire une passe et le tableau sera presque certainement trié.
Nous avons évoqué l'affaire des composants intrus dans les cartes-mères de Supermicro. Cette histoire n'est pas claire du tout. Une hypothèse serait que le composant ne serait pas destiné à faire fuiter des données, mais à attendre qu'on lui donne l'ordre de griller la carte-mère où il est installé.
Pour écrire des applications pour Android, la tendance est en ce moment d'utiliser Rust. Pourtant, Android c'est Google et il nous semblait que le langage de choix de Google est Go. Est-il sur la touche ? Non, Go continuera d'exister pour les autres projets de Google, mais les applications Android utiliseront Rust.
Nous avons appris que Microsoft rejoignait l'Open Invention Network.
Une autre nouvelle concernant Microsoft, c'est la dernière mise à jour de Windows qui détruit des fichiers. Évidemment, c'est gênant.
Même sans détruire des fichiers, les mises à jour de Windows peuvent gêner les utilisateurs. Nous citons le cas d'une équipe de basket qui a perdu un match à domicile, parce que le système d'affichage du stade était géré par un ordinateur sous Windows et parce que cet ordinateur a installé une mise à jour juste avant le début de la rencontre. La mise à jour a pris du temps et a fait commencer le match avec 25 minutes de retard. Or dans le règlement, si le retard dépasse 15 minutes, l'équipe extérieure peut poser une réclamation et obtenir la victoire sur tapis vert. C'est ce qui s'est passé ce jour-là à Paderborn.
Certes, à Paderborn il n'y a pas eu de morts. [ Pas plus que lors de la présentation d'Olivier sur la programmation shell à Albi en 2008 (que nous n'avons pas cité cette fois-ci, mais que nous avions déjà mentionnée précédemment). ] Mais que dire des mises à jour sur des systèmes critiques, comme ceux que l'on trouve dans les salles d'opération des hôpitaux ? [ Certains hôpitaux prennent soin de désactiver les mises à jour automatiques de Windows pour de tels équipements, mais comme le montre ce fil de discussion sur le Forum sur les Risques Technologiques, cela provoque d'autres problèmes. Il faut garder à l'esprit que le résultat est un compromis, pas une solution miracle. ]
Nous avons parlé des évolutions de version de Windows, 3 → 95 → 98 → etc jusqu'à → 10. Le point le plus marquant pour un utilisateur basique est l'évolution du graphisme de l'interface utilisateur. On remarque un curieux changement de sens dans l'évolution de ces interfaces utilisateurs.
- Avant Windows, à l'époque de Xerox et des premiers Macintosh, nous avions des icônes 2D en noir et blanc, franchement austères.
- Avec Windows 3 (peut-être 1 et 2 également), sont apparues les icônes en couleurs, mais c'était toujours des pictogrammes 2D avec la même philosophie que les panneaux de circulation routière : favoriser la rapidité de lecture sans se préoccuper de la valeur artistique.
- Ultérieurement, dès Windows 95 je pense, nous avons eu des icônes 3D, représentant par exemple les répertoires par des chemises en carton en biais au lieu de les montrer à plat.
- Puis les icônes, toujours en 3D, ont eu droit à des ombres.
- Enfin, avec Windows 8, est apparue l'interface Metro. Cette interface revient à la représentation 2D monochrome (pas noir et blanc mais quand même monochrome), un énorme pas en arrière qui nous ramène quasiment aux premiers temps des Macintosh.
Une autre innovation douteuse dans les interfaces utilisateurs, c'est les rubans d'Office. Avant l'introduction des rubans, nous avions une ligne de menu avec les menus « Fichier », « Edit », « Insérer » et ainsi de suite jusqu'à « Aide ». Et nous avions des barres d'outils. C'était facilement configurable par l'utilisateur. Si un utilisateur (comme moi) préfére les menus déroulants, il peut enlever toutes les barres d'outils. Si un utilisateur (comme certains de mes collègues) n'aime pas les menus, il peut afficher plusieurs barres d'outils en les agençant à sa guise. Avec les rubans, la barre de menu a disparu et nous restons avec quelque chose qui ressemble à des barres d'outils tout en étant moins pratique. Et pourquoi l'un de ces rubans s'appelle-t-il « Accueil » ? Un traitement de texte est destiné à afficher et éditer des documents, insérer des éléments, plus quelques opérations sur fichier et l'accès à l'aide intégrée, donc je n'ai pas de problème pour les rubans intitulés « Affichage » « Édition », « Insertion », « Fichier » et « Aide », mais le ruban « Accueil », il sert à accueillir les visiteurs ou quoi ?
Un autre désavantage des rubans, exposé par Richard, c'est que l'affichage des boutons et autres éléments est très fluctuant. Il suffit de diminuer légèrement la largeur de la fenêtre pour provoquer un remaniement important du ruban : des boutons-icônes sont remplacés par des boutons-texte, des boutons disposés horizontalement se retrouvent alignés verticalement, et ainsi de suite. C'est très déroutant pour les utilisateurs et il est impossible d'acquérir des automatismes permettant de fluidifier le travail sur Office.
Je rapporte une anecdote qui nous avait été racontée par Paul Gaborit un soir à Albi pendant les Journées Perl 2008. L'un de ses collègues était un inconditionnel de Microsoft Word et l'utilisait pour rédiger ses publications universitaires. Un jour, après un changement de version, ce collègue a découvert que l'éditeur d'équations de Word avait été abandonné et ne figurait plus dans la nouvelle version de Word. Paul a donc entrepris d'enseigner L^AT_EX à son collègue. Il commence par lui expliquer comment taper du texte. Ensuite, il lui montre le mode mathématique de L^AT_EX. Pour afficher
E = m × c²
il faut coder
```
  $$ E = m \times c^2 $$
```
avec « ^ » pour les exposants et « _ » pour les indices. Le collègue de Paul a alors ouvert des yeux grands comme des soucoupes et s'est exclamé :
Mais, c'est l'éditeur d'équations de Word !
Une petite remarque : lors de la réunion, je n'ai pas réussi à me souvenir du nom de Paul Gaborit. Je replaçais très bien les circonstances de l'anecdote, mais j'étais incapable de retrouver son nom. Cela a héberlué les autres participants à la réunion de me voir confronté à un trou de mémoire.
Comment faire des documents à géométrie variable dans PowerPoint ou son équivalent LibreOffice Impress ? Le but étant par exemple l'écriture de supports de cours, avec une version contenant les questions et les réponses et autre une version contenant seulement les questions. C'est facile à faire avec L^AT_EX. Il faut définir deux documents maîtres, du genre
```
% complet.tex
\documentclass[a4paper]{article}

\begin{document}

\let\ifreponse\iftrue
\input{texte.tex}

\end{document}
```
et
```
% partiel.tex
\documentclass[a4paper]{article}

\begin{document}

\let\ifreponse\iffalse
\input{texte.tex}

\end{document}
```
puis le document contenant le véritable texte :
```
% texte.tex
Quelle est la couleur du cheval blanc d'Henri IV~?

\ifreponse\begingroup
Blanc.
\endgroup\fi

Quelle est la réponse à la question ultime sur la vie, l'univers
et le reste~?

\ifreponse\begingroup
42.
\endgroup\fi
```
Il semblerait que l'une des toutes premières versions d'OpenOffice Impress ait pu avoir une fonctionnalité similaire, mais elle a disparu des versions récentes et de LibreOffice Impress.
Nous avons mentionné la nouvelle récente signalant qu'un Apple I avait été vendu pour plusieurs centaines de milliers de dollars.

Divers

Si des gens sont prêts à payer 375 000 $ pour un ordinateur obsolète, il y en a d'autres qui sont prêts à payer plus d'un million de livres britanniques pour un broyeur de documents.
Une opinion partagée par de nombreuses personnes est qu'il faut varier les menus des repas que l'on consomme. Et pourtant la majorité des gens mangent toujours la même chose au petit-déjeuner, jour après jour, sans jamais varier sa composition. Il y a même des perfectionnistes comme Richard qui déterminent à la seconde près combien de temps il faut pour griller les tartines. Je fais remarquer que mes petits-déjeuners varient. Au moment de la réunion, c'était du café avec des tartines de pain à la confiture de framboises. À d'autres périodes, c'est du café avec des tartines de pain à la confiture d'abricots. Et j'aurais pu mentionner les occasions où je prends du café avec des tartines de pain à la confiture de fraises.
Un participant à la réunion nous raconte un séjour récent à l'hôpital. Après avoir subi une opération avec anesthésie générale, il se réveille en plein après-midi et est ramené à sa chambre. Des infirmières se pointent pour lui proposer à manger. Seul problème, elles n'ont plus de repas de midi, elles n'ont que des restes du petit-déjeuner. Et en fait, le narrateur était très content d'avoir son petit-déjeuner, qu'il trouvait plus appétissant que les déjeuners que l'on sert habituellement dans les hôpitaux.
Les repas sont si peu appétissants dans les hôpitaux que certains patients n'hésitent pas à recourir à Deliveroo ou à Uber Eats pour se faire livrer des repas à leur chambre d'hôpital.
Dans les formulaires officiels, le terme « Mademoiselle » a totalement disparu pour être remplacé par « Madame ». Mais dans la vie de tous les jours, ce n'est pas encore le cas. Ainsi, si l'on s'adresse à une fillette de 4 ans en lui disant « Madame », elle ne comprendra pas que l'on s'adresse à elle. Il se peut même que sa mère, si elle est à proximité, pense que c'est à elle qu'on adresse la parole et non pas à sa fille. D'où une confusion parfois gênante.