Le "Sleep sort" 9


Tout a commencé* par un message « Genius sorting algorithm: Sleep sort » sur 4chan : un anonyme propose un algorithme de tri en 2 lignes de code bash :

function f() {sleep "$1" echo "$1"}
while [ -n "$1" ] do f "$1" & shift done wait

Lorsqu’il est appelé avec une liste de N nombres comme dans ./sleepsort.bash 5 3 6 3 6 3 1 4 7 , ce code lance un processus pour chacun des nombres n. Chaque processus effectue la fonction f, qui utilise la fonction sleep pour attendre n secondes avant d’afficher le nombre n. Dans l’exemple, le 7ème processus n’attendra qu’une seconde avant d’afficher « 1 », le 4ème et le 6ème attendront 3 secondes avant d’afficher « 3 » dans un ordre qui n’a aucune importance et ainsi de suite jusqu’au dernier processus qui affichera « 7 » après 7 secondes. L’utilisateur verra ainsi s’afficher progressivement les N nombres triés dans l’ordre croissant.

Depuis ce message on voit des implémentations de « Sleep sort » fleurir dans tous les langages de programmation en utilisant diverses astuces, et des discussions sans fin sur les forums, anglophones surtout pour l’instant.

Prétextant que ce programme mettrait plus de 11 jours à trier les deux nombres 1000000 et 673, certains considèrent le « sleep sort » comme un bon gag, ce qu’il est certainement à l’origine. Pour ma part j’ai voté contre l’effacement de la page « Sleep sort » de la Wikipedia. Voici pourquoi.

D’abord, ce code est simple et fait l’éloge d’une grande qualité du programmeur : la paresse. Faire quelque chose d’utile simplement en attendant, quoi de plus beau ? A ce titre il mérite amplement sa place à côté du Spaghetti sort dont j’ai déjà causé ici en français, du « tri stupide » (Bogosort) ou des Stooge sort et Lucky sort sans intérêt, mais qui ont leur page Wikipédia.

 

Photo par Eben Regis sur flickr

 

Plus sérieusement, « Sleep sort » exploite de manière active l’écoulement du temps au lieu de le subir, ce qui est déjà intéressant en soi, mais pose également des questions intéressantes sur la « complexité » de tels algorithmes.

Car le « génie » de cet algorithme, s’il vous avait échappé, est qu’il prend en apparence un temps proportionnel à max(n), le plus grand des nombres à trier, pour s’exécuter, plus un temps proportionnel à N pour créer les processus. Or les algorithmes de tri généraux existants prennent un temps proportionnel à N.log(N). Il pourrait donc exister des cas où le « sleep sort » serait plus rapide. Mais est-ce vraiment le cas ?

Traitons d’abord de la partie la plus perceptible du temps d’exécution, l’attente de max(n) secondes. Sur les machines actuelles, l’attente se spécifie en millisecondes, et on pourrait probablement passer aux microsecondes. En fait il faut simplement garantir que deux processus associés à deux nombres x et x+1 se réveillent dans le bon ordre et aient le temps de produire leur sortie sans perturber le réveil des processus suivants. Déjà ceci soulève plein de problèmes intéressants au niveau des systèmes d’exploitation, de l’accès aux ressources critiques etc. Mais quelles que soient les solutions techniques, il reste qu’on ne sait pas bien exprimer théoriquement la complexité d’un tel algorithme : en principe, une durée d’exécution proportionnelle à l’une des données conduit à une complexité O(1) supposée largement inférieure à O(N), ce qui n’est pas le cas en pratique ici.

Ensuite la partie « proportionnelle à N » dans laquelle on crée les N processus est elle vraiment O(N) ? En principe oui, mais il existe une partie invisible : la gestion interne de la fonction système « sleep ». Dans tous les systèmes d’exploitation que je connais (au moins deux…), « sleep » provoque l’insertion du processus dans une liste de tous les processus suspendus en attente de l’échéance d’un certain temps. Et pour éviter de parcourir toute la liste à chaque interruption du timer pour trouver quels processus doivent être réveillés, on la maintient triée dans l’ordre des réveils programmés. « Triée » ? Et oui… : à chaque instruction « sleep », rencontrée le processus est inséré au bon endroit. « Inséré » ? Et re-oui… : l’exécution des N « sleep » revient à un « tri par insertion« , d’une complexité O(N²) rédhibitoire.

« Sleep sort » n’est donc pas un tri linéaire, du moins sur un ordinateur ayant beaucoup moins de N processeurs. Mais il soulève plein de questions intéressantes sur les algorithmes, les systèmes d’exploitation, l’architecture des ordinateurs et la psychologie des programmeurs. Il faut le garder !

Note* : en fait l’idée est plus ancienne comme le montre ce post « Linear Time Sort Puzzler » datant de 2006

  • H

    Tiens c’est marrant, je l’ai vu passer sur un forum il y a quelques jours, j’ai cru que c’était un gag ancien. Bon, c’est une astuce rigolote, mais est-ce qu’il y a de quoi s’y attarder plus que quelques secondes ?

    Et alors, garder ça sur WP ?!… dans la section « anecdotes » de l’article sur les algos de tri, à la rigueur. Enfin, y a bien un article sur unlambda, une pure private joke de normaliens… la vieille tradition du canular chère à l’École…

  • Krunch

    Un tri par insertion qui utilise un arbre bicolore (comme c’est le cas dans Linux) c’est O(n*log(n)), pas O(n^2).

  • http://www.lita.univ-metz.fr/~gely/ Alain

    hum…
    ça ressemble tout de même sacrément à un tri par comptage, qui est l’exemple typique quand on veut montrer un tri sans comparaisons et avec complexité linéaire sous condition (à savoir que l’étendue des valeurs triées, entières, doit être de l’ordre de O(n))

    (ou le tableau de comptage est remplacé par une structure « temporelle », chaque seconde faisant office d’une case)

    cf par exemple cette page de wikipédia
    http://fr.wikipedia.org/wiki/Tri_comptage

  • http://www.yvesmasur.ch/ Yves Masur

    Ce tri est un super gag. En fait de tri, c’est la pougne absolue, puisqu’il passe au système d’exploitation le soin de trier, et affiche ensuite le résultat. Pour moi, un algorithme doit être réalisé dans le code, pas ailleurs.

  • http://blog.rom1v.com ®om

    Moi j’ai trouvé ça intéressant, je garde en favoris pour suivre les différents liens de ton billet. Merci.

    • http://www.facebook.com/profile.php?id=100003406023708 Phue

      Bonjour,Vous avez fait une faute dans la division avec reste. Quand vous avez dit que vous de9ssandiez le criffhe des unite9s, vous avez de9ssandu le 6.Thomas R.

  • celui

    Mais arrêtons de comparer poires et bananes !

    En informatique, ce que l’on aime savoir, c’est si un algorithme est rapide ou pas, et le comparer avec les autres algorithmes qui font la même chose. « rapide », n’est pas une notion très scientifique et pour être sûr de comparer ce qui est comparable, on compare des algorithmes dans les mêmes conditions, c’est pour ça que l’on a des modèles, pas un modèle, plusieurs modèles.

    Ce qui n’est pas un modèle, c’est tout qui se s’exprime en secondes, et dépend de la machine. (donc l’ajout de processus)

    Le modèle le plus compliqué à analyser, c’est le modèle de complexité en temps. Et pour un informaticien, le temps ne s’exprime pas secondes, mais en nombre de portes (pour faire simple disons que nous n’avons à notre disposition que des portes ET, OU et NON) que comporte un circuit qui implémente cet algorithme.

    C’est con pour les informaticiens, le modèle qui semble le plus proche de la réalité, c’est le plus emmerdant à utiliser.

    Un modèle fastoche, c’est le modèle de complexité en requête. L’algorithme a accès un oracle qui « encode » l’entrée et on compte combien de fois on fait appel à l’oracle. Pour le tri, l’oracle prend en entrée les « numéros » de deux nombres à comparer et retourne le numéro du plus grand. Dans l’exemple de ce billet, on peut lui demander de comparer le 1er entier et le 4ème, l’oracle répond que le premier est le plus grand.

    Dans ce modèle là, on peut prouver qu’il faut O(n*log(n)) appels à l’oracle pour résoudre le problème de tri où n est le nombre d’entiers en entrée. [Tout le reste n'est, dans ce modèle, pas supposé dépendre de n]

    C’est pas parfait comme modèle, mais au moins, maintenant on a un nombre et on sait exactement à quoi il correspond, et on doit tous être plus ou moins convaincu que c’est une bonne approximation de la « rapidité » de l’algorithme.

    Sleep Sort, ne s’exprime pas franchement dans le modèle de complexité en requête, mais on peut essayer de faire un modèle ad-hoc.

    Pour que sleep sort ne soit pas buggué, le programmeur fait une hypothèse très forte, il est capable de lancer tous les « sleep » un moins d’une miliseconde, donc il fait la supposition que n, le nombre de nombres à trier, est au plus 1 miliseconde, donc que la complexité de son algorithme ne dépend pas de n. Donc ça fait sens, sous les hypothèse où cet algorithme fonctinne de prendre comme mesure de complexité les milisecondes passées à attendre. Et comme cela a été dit, c’est le plus grand des nombres à trier M , qui va s’écrire sur m = O(log(M)) bits. Il faut donc attendre O(2^m) secondes. Bref, Sleep Sort, dans un modèle qui a du sens (Temps à attendre en fonction de la taille des entrées) est un algorithme qui a une complexité exponentielle.

    Et c’est ça la moralité de l’histoire.

  • http://drgoulu.com Dr. Goulu

    Merci à Nicolas Gaudin pour son lien depuis LinuxFr.org, qui m’a valu un gros pic de visites et les intéressants commentaires ci-dessus.

    @H, je me suis posé aussi la question, mais visiblement cet algo bête soulève des questions qui le sont moins … (Merci pour Unlambda. Je connaissais d’autres langages de programmation exotiques qui m’ont bien amusé mais pas autant émoustillé que le « sleep sort »)

    @Krunch : merci pour l’info. Je me demande combien de processes attendent dans la sleeping queue en moyenne 10 ? 100 ? ça vaut la peine de faire une insertion sophistiquée ?

    @Alain : oui c’est vrai, je n’avais pas fait le lien avec le tri par comptage, et on y retrouve le principe courant d’échanger du temps pour de la mémoire (ou vice-versa)

    @Yves : c’est justement le problème des algos écrits dans des langages « de haut niveau » : tu dois savoir comment ils sont implantés en « bas niveau » pour analyser leur complexité. C’est ce qui rend ce gag intéressant à mon avis.

    @celui : absolument, il faut O(N.log N) comparaisons pour un tri dans le cas général. Mais il existe des tris linéaires O(n) pour des cas particuliers, dans lesquels il n’y a pas besoin de comparaisons. C’est le cas du « sleep sort » si on omet le tri par insertion dans la liste de réveil.
    Ton « hypothèse très forte (selon laquelle) il est capable de lancer tous les « sleep » un moins d’une miliseconde » ne me semble pas fondée : on pourrait masquer l’interruption timer jusqu’à ce que tous les sleeps soient lancés. D’accord sur la complexité exponentielle par rapport au nombre de bits, mais comme on ne mesure pas ainsi la complexité des algos de tri « classiques », c’est justement là qu’il ne faut pas comparer des poires et des bananes. Il se pourrait que le « sleep sort » trie une séquence de beaucoup de petis nombres redondants (2 1 1 1 2 2 2 1 1 1 1 0 2 1 …) mieux qu’un algo général. C’est justement le cas favorable au « tri par comptage » d’ailleurs…

  • Pingback: Langage de programmation Linotte » Blog Archive » Le webzinotte n°1