Correction détaillée du Qcm

La correction détaillée du QCM est sortie (page principale) et j'y ai jeté un oeil.

Je suis un peu étonné par l'étendue qu'ont prise dans cette correction les considérations "bas niveau".
Autant je comprends très bien la mise en avant, pour la dernière question, de l'hypothèse "la différence attendue est très petite par rapport à la taille des séquents", autant passer plusieurs pages à commenter valgrind et la mise en cache me paraît peut-être un peu excessif.

Enfin, le passage sur l'utilisation des entiers comme vecteur de bits pour des chaînes de 15 caractères à 4 valeurs me semble à la limite du ridicule. C'est certainement astucieux, mais est-ce vraiment une bonne idée ? En imaginant qu'on écrive ce code source en situation réelle, est-ce une bonne manière de faire ? Certainement pas, parce que si demain les spécifications changent légèrement et on passe à de séquences de taille 20, vous êtes dans la choucroute (ou alors vous faites acheter des procos 64 bits à tout votre labo).

Parler de "solution attendue" dans ce cas me paraît discutable. Pour moi une "solution attendue", c'est ce qu'on conseille aux gens de faire, donc implicitement c'est "la meilleure", ou "une des meilleures", façon de faire. Je sais bien que le contexte d'un concours d'algo et de la programmation en général sont différents, mais là ça me paraît un peu excessif (alors qu'à la rigueur, le texte d'Ulrich Drepper pourrait être considéré comme de la culture générale, d'où son titre).

Pour formuler ça plus précisément, à mon humble avis :
- le raisonnement sur l'ordre de grandeur des contraintes fait partie des comportements désirables chez les canditats
- le raisonnement sur _la valeur numérique précise_ de ces contraintes n'est pas algorithmique, est une mauvaise pratique, et n'a pas forcément sa place dans le hall de gloire d'une correction détaillée

Il semble y avoir deux points dans ta critique :
- le fait que l'on passe quelques pages (moins de trois pages, en fait) à expliquer une utilisation basique de valgrind et à introduire les problématiques de mémoire cache permettant de comprendre pourquoi une solution va plus vite qu'une autre.
- le fait que la solution attendue consistant à mettre une chaîne de 15 caractères sur un entier ne soit pas algorithmiquement meilleure que d'indexer une table de hachage par la chaine brute.

Concernant le premier point, tu remarqueras que l'utilisation de valgrind n'est décrite que dans la section "Des solutions plus rapides, pour les curieux", et que c'était bien précisé que ce n'était aucunement une solution attendu. Désolé d'avoir voulu apprendre quelque chose aux candidats qui va au-delà de l'algorithmique pure ! Personne n'oblige un candidat à lire cette correction, et encore moins cette partie explicitement notée comme allant au delà de ce qui était nécessaire pour avoir le "maximum de points".

Concernant le deuxième point, notre solution est toujours asymptotiquement meilleure que celle d'utiliser la chaine brute, par un facteur multiplicatif. En effet, si la taille des sous-chaînes demandées est grande (par exemple, L = 100), tu peux utiliser la même astuce en utilisant un tableau de 7 entiers 32 bits, dans lesquels tu concatènes les représentations des nucléotides à l'aide de 2 bits. Avec une machine 32 bits, cette solution est asymptotiquement (grosso-modo) 16 fois plus rapide, et 32 fois plus rapide avec une machine 64 bits. C'est très loin d'être négligeable, on ne parle pas d'une amélioration de quelques pourcents ! Cette solution est donc bien "une des meilleures" dans une situation réelle, quelque soit la valeur L. En plus, en "situation réelle", plus L est grand plus c'est important de gagner du temps. Certes, c'est moins noble que de passer d'un algorithme en O(n²) à un autre en O(n), mais c'est tout aussi valable !

Enfin, comme tu as commencé à le dire, Prologin est un concours d'informatique, et non exclusivement d'algorithmique. Les "astuces" sur les bits d'un entiers sont justement très utilisées dans beaucoup d'implémentations d'algorithmes et de structures de données dans des logiciels programmés par des gens qui savent en général ce qu'ils font. Par exemple, le code du noyau linux est rempli de ce genre d'astuce. Voilà une des raisons pour lesquelles il nous a semblé approprié de proposer un exercice pouvant se résoudre plus rapidement en utilisant la représentation en mémoire des entiers.

Tu as bien analysé mon commentaire.

Tu as raison sur le fait que la présentation de valgrind ne "fait pas de mal". Ce n'est pas le point le plus important du message : ce que je reproche dans le fond ce sont les considérations bas niveau sur les vecteurs de bits qui nuisent (à mon avis) à la qualité de la programmation. La partie sur valgrind n'a fait que renforcer mon sentiment d'ensemble d'une certaine ínsistance un peu futile sur des considérations bas niveau, elle n'a rien à se reprocher en elle-même. Cependant, je ne suis pas sûr que sa place soit dans une correction d'exercices, même détaillées. L'impression qui ressort de cette partie, c'est que les correcteurs se sont amusés à profiler et optimiser à fond cet algorithme, et qu'ils ont décidé d'en faire part aux canditats.
Ça ressemble donc plus à un léger trip technique sur une question qui n'en valait pas forcément la peine qu'à un approfondissement naturel.

Ça aurait donc plus, à mon humble avis, sa place dans un billet sur un blog (vous avez un CMS, pourquoi ne pas en profiter pour poster de petits billets pour "apprendre au-delà" aux lecteurs avides (si vous laissez courir la rumeur que la lecture du blog augmente les chances au concours, succès garanti) ?), que dans une correction d'exercice, qui se veut conclusive et relativement universelle (il faut que tout le monde la lise), donc si possible claire et concise (quitte à ouvrir des portes, ou des liens, vers des sujets plus avancés).

Encore une fois, cette partie sur Valgrind n'est pas ce que je critique : moi, je l'aurais mise autre part, et comme j'ai décidé d'écrire un message au sujet de cette correction dans son ensemble j'ai décidé d'en dire deux mots au passage, mais je ne lui en veux pas.

> Concernant le deuxième point, notre solution est toujours
> asymptotiquement meilleure que celle d'utiliser la chaine brute,
> par un facteur multiplicatif.

Tu le sais certainement aussi bien que moi, l'étude théorique classique de la complexité *néglige* les facteurs multiplicatifs. Tu as tout à fait le droit de faire des analyses plus fines (même si, comme je l'ai dit plus haut, il ne faudrait pas non plus transformer une correction en une expérimentation), le problème c'est qu'ici elles ne me semblent pas tellement pertinente :
- comme le montre l'expérimentation, le gain observé n'est pas du tout un facteur 16, ou 32 en 64 bits, même asymptotiquement. Les opérations utilisées changent, leurs performances aussi (d'un facteur multiplicatif) et ton analyse est donc bancale sans un modèle précis des performances de ton processeur, non portable et irréaliste avec les machines d'aujourd'hui
- si tu utilisais un tableau d'entier, l'intérêt de la méthode décrite serait encore plus faible qu'avec le cas particulier actuel où un seul entier suffit (c'est l'exploitation à outrance de ce cas particulier que je critique principalement); je me permets même de conjecturer qu'elle serait plus lente que l'utilisation d'une structure de donnée bien pensée (comme une queue), puisque tu n'aurais plus accès à l'opération "shift" qui en fait tout son intérêt
- comme le montre la suite de la discussion, les effets de localités jouent essentiellement autant que cette méthode de stockage¹; faire une analyse formelle (qui se veut générale) à une échelle où les effets bas niveau (spécifiques à un cas particulier) jouent autant me semble périlleux, et certainement pas une bonne pratique à enseigner aux débutants.

¹ : je reconnais que ces effets de localités sont probablement rendus exploitables par la compacité de la représentation mémoire, et que donc sans cette "astuce" que je décrie ils perdraient tout leur sens. Ça n'enlève rien à mon propos, qui est de dire que ces deux considérations sont de même nature.

> Les "astuces" sur les bits d'un entiers sont justement très utilisées
> dans beaucoup d'implémentations d'algorithmes et de structures de
> données dans des logiciels programmés par des gens qui savent en
> général ce qu'ils font.

Pourquoi ne pas réutiliser ces structures de données merveilleuses ? La STL propose une classe bit_vector, et la plupart des compilateurs spécialisent vector pour profiter de la représentation mémoire compacte².
Réutiliser une structure de donnée déjà existante est certainement une bonne pratique que nous pouvons conseiller aux débutants les yeux fermés. Jouer à l'apprenti sorcier en imitant les "gens qui savent ce qu'ils font" est plus contestable.

² : mais pas de l'opérateur "shift", et vu les performances médiocres des manipulations en accès arbitraire sur des bits isolés avec le software/hardware actuel ça ne serait pas forcément si formidable. Encore une fois on se heurte au problème déjà mentionné : la valeur numérique précise de L rend l'astuce intéressante, mais elle ne peut pas évoluer ou s'adapter à des paramètres différents.

> Enfin, comme tu as commencé à le dire, Prologin est un concours
> d'informatique, et non exclusivement d'algorithmique.

Je pense que, de nos jours, des connaissances de base en ingénérie logicielle sont plus utiles aux gens qui s'intéressent à "l'informatique" que des astuces pour coder des chaînes de taille inférieure à 15. La correction proposée va à l'encontre de ces principes (de bon sens : si une modification de 20% d'un de tes paramètre fait foirer tout ton algorithme et nécessite un recodage quasi-complet, il y a comme un problème), et c'est ce que je lui reproche : considérer cette possibilité dans une discussion entre personnes informées est peut-être une bonne idée, exposer cette méthode comme une solution géniale à une bande de débutants impressionnables ne l'est clairement pas.

Une petite citation de Dijkstra :

« we have to be very careful in the choice of what we learn and teach, for unlearning is not really possible »