Voir vos messages    Voir vos messages  
 + Enregistrement
  • First Image

    web applications

    Lorema psum dolor sit amet, consectetur adipiscing elit.

  • First Image

    web applications

    Lorema psum dolor sit amet, consectetur adipiscing elit.

  • First Image

    web applications

    Lorema psum dolor sit amet, consectetur adipiscing elit.

  • First Image

    web applications

    Lorema psum dolor sit amet, consectetur adipiscing elit.

    Reseaux sociaux

  • deviantart
  • Flux rss
  • Twitter
  • facebook
  • stuble
  • delicious
Connexion
Identifiant :

Mot de passe :

Se souvenir de moi



Mot de passe perdu ?

Inscrivez-vous !
Liens recommandés
IDEOZ Voyage, voyagez curieux





Le « Sleep sort »

Publié par Philippe Guglielmetti le 19/06/2011 13:11:29 (275 lectures) Articles du même auteur
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 ./s ...






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





Note: 0.00 (0 votes) - Noter cet article -
Format imprimable Envoyer cet article à un ami Créer un fichier PDF à partir de cet article
Signets Sociaux
Mettre en favoris dans Blinklist Mettre en favoris dans del.icio.us Mettre en favoris dans Digg Mettre en favoris dans Fark Mettre en favoris dans Furl Mettre en favoris dans Newsvine Mettre en favoris dans Reddit Mettre en favoris dans Simpy Mettre en favoris dans Spurl Mettre en favoris dans Yahoo Mettre en favoris dans Balatarin Mettre en favoris dans Faceboom Mettre en favoris dans Twitter Mettre en favoris dans Scripstyle Mettre en favoris dans Stumble Mettre en favoris dans Technorati Mettre en favoris dans Mixx Mettre en favoris dans Myspace Mettre en favoris dans Designfloat Mettre en favoris dans Google Plus Mettre en favoris dans Google Reader Mettre en favoris dans Google Bookmarks
 
Les commentaires appartiennent à leurs auteurs. Nous ne sommes pas responsables de leur contenu.
Auteur Commentaire en débat
Déposer un commentaire
Règles des commentaires*
Tous les commentaires doivent être approuvés par un Administrateur
Titre*
Nom*
Courriel*
Site Internet*
Message*
Code de Confirmation*
2 + 4 = ?  
Entrez le résultat de l'expression
Maximum de tentatives que vous pouvez essayer : 10