Le tri anglais des Bermudes

samedi 19 avril 2014
par  Alain BUSSER

Petite expérience

Voici un algorithme si stupide que personne apparemment n'a encore pensé à l'implémenter:

  1. Créer un tableau d'entiers, allant de 0 à 16 (par exemple).
  2. Trier le tableau dans l'ordre croissant, à l'aide de la fonction de comparaison des entiers (c'est ici que l'algorithme est particulièrement stupide puisque le tableau est déjà trié).
  3. Afficher le résultat.

Essayer le script suivant en cliquant sur le bouton:

Si vous utilisez un navigateur autre que Chrome, il y a de fortes chances que l'affichage soit trié de 0 à 16, comme on s'y attend. Mais sous Chrome, l'affichage est plus surprenant...

Découverte du problème

Le point de départ a été une activité faite avec alcoffeethmique sur l’approximation normale d’une loi binomiale. Le cours sur la loi normale ayant déjà été fait, les élèves étaient familiarisés avec la forme de la célèbre courbe en cloche. Il s’agissait donc de leur faire représenter graphiquement des lois binomiales de paramètre N croissant (avec p voisin de 0,5) jusqu’à ce que la forme de cloche leur paraisse évidente [1]. Pour cela, la version d’alcoffeethmique ci-dessous a été utilisée :

alcoffeethmique pour les stats
logiciel de programmation orienté probas-stats-algo

L’algorithme utilisé pour représenter graphiquement une loi binomiale avec alcoffeethmique est celui-ci :

  1. N = 8
  2. p = 0.4
  3. loi = (binomiale N, p, k for k in [0..N])
  4. diagrammeBatonsTrie loi, 1

Télécharger

Rédigé ainsi, il suffit de modifier la première ligne pour avoir d’autres valeurs de N (mais il faut ajuster le dernier paramètre à la quatrième ligne pour que le graphique soit bien dimensionné). On peut décrire l’algorithme ainsi :

  1. On affecte la variable N à 8 (taille de l’échantillon).
  2. On affecte la variable p à 0,4 (probabilité de succès).
  3. On crée un tableau loi contenant les probabilités que le nombre de succès soit k pour toutes valeur de k allant de 0 à N.
  4. On dessine le diagramme en bâtons de la loi binomiale, en triant les valeurs de k au passage (ceci est nécessaire au cas où ces valeurs n’auraient pas été introduites dans l’ordre croissant).

On obtient alors le diagramme en bâtons suivant :

image/svg+xml

Mais pas toujours : Le graphique ci-dessus a été obtenu avec le navigateur Mozilla Firefox. Mais le même alcoffeethmique avec le même script produit sous Google Chrome un graphique visiblement assez différent :

image/svg+xml 50 0 51 2 1 53 5 3 4 55 9 6 7 8 57 14 10 11 12 13 60 20 15 16 17 18 19 64 27 21 22 23 24 25 26 68 35 28 29 30 31 32 33 34 72 44 36 37 38 39 43 42 40 41 77 54 52 49 45 46 48 47 81 62 61 56 58 59 84 67 63 65 66 87 73 69 70 71 89 78 74 76 75 92 83 82 79 80 94 88 86 85 90 91 93 95 96 97 98 99 100

Comme alcoffeethmique est programmé en CoffeeScript, il est relativement aisé de chercher dans son code source comment sont dessinés les diagrammes en bâtons :

  1. diagrammeBatonsTrie = (dico, ech=400) ->
  2.     nombreBatons = (x for x of dico when x<Infinity).length
  3.     dicotrie=(parseFloat x for x of dico when x<Infinity).sort (x,y)-> x>y
  4.     effaceDessin()
  5.     dessineSegment 20, 440, 620, 440, 'black'
  6.     abscisse = 40-600/nombreBatons
  7.     for x in dicotrie
  8.         abscisse += 600/nombreBatons
  9.         hauteur = 400/ech*dico[x]
  10.         dessineRectangle abscisse, 440-hauteur, 5, hauteur, 'blue'
  11.         dessineTexte x.toString().replace(".",","), abscisse, 460, 'black'

Télécharger

C’est donc la troisième ligne qui effectue le tri croissant selon les valeurs du caractère, qui est responsable du mélange des bâtons. Elle crée, à partir de la liste dico des valeurs du caractère, une sous-liste formée par les seuls éléments qui soient à la fois numériques et finis [2]


Question : Comment Google Chrome trie-t-il les nombres ?

D’où vient cette relation d’ordre étrange ? Des Bermudes [3] ?

En effet le phénomène est parfaitement reproductible et le tri obtenu dépend visiblement de la taille du tableau à trier.

Fonction de tri

La variante suivante du script en haut de page, donne un tri correct par Chrome :

  1. N = 16
  2. tableau = [0..N]
  3. tableau.sort()
  4. alert tableau

Télécharger

Ainsi, par défaut, Chrome trie les nombres dans l’ordre croissant. Mais si on lui demande explicitement de le faire, il ne le fait plus... Et un autre problème surgit alors : cette fois-ci, c’est Firefox qui donne un résultat surprenant :

0,1,10,11,12,13,14,15,16,2,3,4,5,6,7,8,9

Au secours, ils sont tous fous !!! Non, en fait il y a une logique dans l’ordre choisi par Firefox : c’est l’ordre lexicographique. Et c’est parce que les informations dans une page html sont essentiellement textuelles, que les développeurs de chez Mozilla ont fait ce choix. Il est donc nécessaire, hors Google Chrome, de préciser que les nombres doivent être rangés dans l’ordre croissant et non dans l’ordre lexicographique, en fournissant à sort (trier) la relation d’ordre choisie :

  1. N = 16
  2. tableau = [0..N]
  3. tableau.sort (x,y) -> x>y
  4. alert tableau

Télécharger

Cet aspect de la fonction sort (tri de JavaScript est, du point de vue mathématique, une porte ouverte vers un univers vaste d’exercices de statistiques : les notions de médiane et de quartiles ne dépendant que du tri, ces notions peuvent très bien s’étendre à d’autres relations d’ordre que l’ordre naturel des nombres. Par exemple, avec l’ordre alphabétique, la notion de mot médian d’un dictionnaire a du sens et même un sens assez concret...

Trier les algorithmes de tri

En fait, il semble que les différents navigateurs internet utilisent différents algorithmes de tri. Ainsi :

  • Safari utiliserait un algorithme de tri par sélection, inefficace sur de grands tableaux puisque le temps de tri d’un tableau de taille n est proportionnel à n² ;
  • Firefox aurait plutôt opté pour le tri fusion, proportionnel à n ln(n) ;
  • Chrome fait plus compliqué : Selon la taille du tableau et la nature de ses éléments, il choisit entre
  • Quant à Internet Explorer, comme ce n’est pas un logiciel libre, on ne peut pas savoir comment il trie les éléments ; on peut cependant supposer que c’est le tri rapide, puisque son auteur Charles Antony Richard Hoare travaille chez Microsoft qui est propriétaire de Internet Explorer.

La correction du bug

En fait, il n’est (heureusement) pas nécessaire de détecter la nature du navigateur et appliquer un algorithme différent selon le navigateur. Il suffit, au lieu d’une fonction booléenne comme relation d’ordre

  1. (x,y) ->
  2.     x>y

Télécharger

d’appliquer une fonction numérique

  1. (x,y) ->
  2.     x-y

Télécharger

Ce qui a pour effet de réconcilier les navigateurs, Firefox continuant à interpréter la relation d’ordre comme booléenne (un nombre positif étant assimilé à true) et Chrome acceptant enfin de ranger les nombres dans l’ordre croissant. La modification [4] sera faite dans la prochaine version d’alcoffeethmique...

Ainsi, on peut tester en haut de cette page la version universelle du tri d’entiers déjà triés :

  1. N = 16
  2. tableau = [0..N]
  3. tableau.sort (x,y) -> x-y
  4. alert tableau

Télécharger

Celle-ci donne l’ordre croissant quel que soit le navigateur, même dans le triangle des Bermudes...

Cependant, même si on sait comment faire pour que Chrome trie les nombres dans l’ordre correct, tout ceci n’explique pas comment il trie les entiers avec la version en haut de cette page. Et comme Chrome n’est pas un logiciel libre, on ne peut pas consulter son code source pour voir comment est effectué ce tri mystérieux venu d’ailleurs...


Pour essayer d’en savoir plus, on peut faire quelques expériences, ce qui permet d’émettre des conjectures :

  • Si la taille du tableau est inférieure à 10, les entiers sont triés dans l’ordre croissant, comme on peut le vérifier cas par cas ; exemple pour N=9 :

image/svg+xml 0 1 2 3 4 5 6 7 8 9

Par contre dès N=10, l’ordre naturel n’est plus respecté :

image/svg+xml 5 0 1 2 3 4 6 7 8 9 10

  • Pour N supérieur à 9, la médiane est déplacée avant le minimum du tableau ; on le voit pour N=10 ci-dessus mais aussi pour les valeurs suivantes : N=11 :

image/svg+xml 6 0 1 2 3 4 5 7 8 9 10 11

Mais aussi N=12 :

image/svg+xml 6 0 7 2 1 3 4 5 8 9 10 11 12

On voit qu’à partir de N=12, la situation devient plus compliquée que le déplacement de la médiane en première position. Mais en continuant on émet d’autres conjectures :

  • Le premier élément reste en seconde position juste après la médiane ; on l’a déjà vu ci-dessus mais effectivement cela semble rester le cas, avec N=13 :

image/svg+xml 7 0 8 2 1 3 4 5 6 9 10 11 12 13

Puis avec N=16 :

image/svg+xml 8 0 9 2 1 11 5 3 4 6 7 10 12 13 14 15 16

  • Il y a toujours deux éléments insérés entre 0 et 1 : l’élément suivant la médiane, et l’élément 2. Regarder les graphiques ci-dessus, mais aussi pour N=20 :

image/svg+xml 10 0 11 2 1 13 5 3 4 15 9 7 8 6 12 14 16 17 18 19 20

ou N=32 :

image/svg+xml 16 0 17 2 1 19 5 3 4 21 9 6 7 8 23 14 13 12 10 11 26 20 18 15 22 24 25 27 28 29 30 31 32

  • Pour N supérieur à 15, le 5 est placé avant le 3 et le 4, et précédé d’un autre élément plus grand que lui. Là encore, on le voit au-dessus, mais aussi par exemple pour N=64 :

image/svg+xml 32 0 33 2 1 35 5 3 4 37 9 6 7 8 39 14 10 11 12 13 42 20 15 16 17 18 19 46 27 21 22 23 26 25 24 50 34 31 28 30 29 53 41 40 36 38 55 45 43 44 57 49 47 48 59 54 52 51 56 58 60 61 62 63 64

Quant à l’élément placé avant le 5, on peut tenter de conjecturer comment il dépend de N avec ce tableau :

N élément avant le 5
16 11
20 13
25 14
32 19
40 23
64 35
100 53

Édifiant, non ?

Il y a sans doute bien d’autres conjectures à émettre. Et on peut même espérer qu’avec beaucoup d’entre elles, on puisse se faire une idée sur l’algorithme de tri utilisé.

Un groupe de MATh.en.JEANS en culottes courtes y arrivera-t-il avant les développeurs de chez Google en bermudas ?


[1En plus, une semaine avant Pâques, ça aide à reconnaître une forme de cloche...

[2Si x n’est pas un nombre, le test x<Infinity échoue et x n’est pas retenu ; il en est évidemment de même si x est, par un hasard malencontreux, infini.

[3Lieu du siège social de Google, qui développe Chrome, et qui est anglais ; d’où le titre de l’article...

[4Solution découverte par Florian Tobé, mais elle avait déjà été faite dans le code source de DGPad qui avait connu un problème similaire.


Commentaires

Logo de Seb
lundi 28 avril 2014 à 04h31 - par  Seb

Intéressant. Du coup quand on a de vrais traitements à faire sur des données, le mieux est encore d’utiliser un vrai langage de programmation (python ;-) ) à la place de javascript et d’un obscur navigateur web :)