Sleep Sort est un algorithme de tri de nombres entiers que j'ai trouvé sur Internet. Il ouvre un flux de sortie et, pour chaque numéro d'entrée en parallèle, retarde le nombre de secondes et génère ce nombre. En raison des retards, le nombre le plus élevé sera affiché en dernier. J’estime qu’il a O (n + m), où n est le nombre d’éléments et m le nombre le plus élevé.

Voici le code original dans Bash

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

Voici le pseudocode

sleepsort(xs)
 output = []
 fork
   for parallel x in xs:
     sleep for x seconds
     append x to output
 wait until length(output) == length(xs)
 return output

Votre tâche consiste à implémenter Sleep Sleep en tant que fonction dans le langage de programmation de votre choix. Vous pouvez négliger les facteurs de concurrence tels que les conditions de concurrence et ne jamais verrouiller les ressources partagées. Le code le plus court gagne. La définition de la fonction compte pour la longueur du code.

La liste de saisie est limitée à des entiers non négatifs uniquement, et la longueur de la liste de saisie devrait être raisonnablement longue (testez au moins 10 nombres), de sorte que des conditions de concurrence ne se produisent jamais. et en supposant que les conditions de course ne se produisent jamais.

Une sorte de tentative boiteuse de Perl , 59 55 52 38 32 caractères :

map{fork||exit print sleep$_}@a

Barebones: 25 personnages:

... si les résultats de tri comme sortie ne vous dérangent pas:

map{fork||die sleep$_}@a

Avec tous les accompagnements:

(pour une conformité maximale des défis, 44 caractères)

sub t{map{fork||exit print sleep$_}@_;wait}

Si vous laissez perl faire l'attente, 39 caractères:

sub t{map{fork||exit print sleep$_}@_}

Et encore une fois, si cela ne vous dérange pas die(), 32 personnages ...

sub t{map{fork||die sleep$_}@_}

Notez que dans Perl 6, ou lorsque la fonction 'say' est déclarée, il est possible de remplacer la printfonction par say, en sauvegardant un caractère dans chaque instance. Évidemment, puisque les diedeux terminent le processus forké et écrivent la sortie, cela reste la solution la plus courte.

C , 127 caractères, une solution plutôt évidente:

main(int c,char**v){
#pragma omp parallel for num_threads(c)
for(int i=1;i<c;++i){int x=atoi(v[i]);sleep(x);printf("%d ",x);}}

(Compilé avec gcc -std=c99 -fopenmp sort.cet en ignorant tous les avertissements.)

Ruby 1.9, 32 caractères

En tant que fonction:

s=->a{a.map{|i|fork{p sleep i}}}

Si nous pouvons simplement utiliser une variable prédéfinie, elle se réduit à 25 caractères:

a.map{|i|fork{p sleep i}}

JavaScript , 65 caractères (selon que vous utilisez console.logou autre chose pour afficher le résultat)

a.map(function(v){setTimeout(function(){console.log(v)},v*1000)})

Cela suppose qu'il as'agit d'un tableau d'entiers non négatifs et qui map()existe sur le prototype de tableau (JavaScript 1.6+).

APL ( 15 13)

{⎕←⍵⊣⎕DL⍵}&¨⎕

Ce qu'il fait:

¨⎕       : for each element of the input
&        : do on a separate thread
⎕DL⍵    : wait approx. ⍵ seconds
⎕←⍵     : output ⍵

Quatre essais à Erlang:

Sortie sur la console, ont pris la liberté de le faire chacun 9ms * Numberpuisque c'est assez pour le faire fonctionner (testé sur une carte intégrée Atom = lente):

Nécessite 60 caractères

s(L)->[spawn(fun()->timer:sleep(9*X),io:write(X)end)||X<-L].

La sortie vers la console est totalement un-Erlangish, nous envoyons donc un message à traiter P:

Nécessite 55 caractères

s(P,L)->[spawn(fun()->timer:sleep(9*X),P!X end)||X<-L].

L'envoi après un délai peut également être effectué différemment (cela fonctionne même avec 1ms * Number):

Nécessite 41 caractères

s(P,L)->[erlang:send_after(X,P,X)||X<-L].

En fait, c'est un peu injuste car la fonction intégrée send_afterest un retardataire et nécessite le erlang:préfixe d' espace de nom , si on considère cet espace de nom importé (effectué au niveau du module):

Nécessite 34 caractères

s(P,L)->[send_after(X,P,X)||X<-L].

C # - 137 caractères

Voici une réponse en C # (mise à jour avec des degrés de parallélisme commentés)

void ss(int[]xs){xs.AsParallel().WithDegreeOfParallelism(xs.Length).Select(x=>{Thread.Sleep(x);return x;}).ForAll(Console.WriteLine);}

Python - 81 93 148 150 153

Tweaking le code de BiggAl, puisque c'est le jeu auquel nous jouons ....

import threading as t,sys
for a in sys.argv[1:]:t.Timer(int(a),print,[a]).start()

... ou 97 175 avec départ différé du fil

import threading as t,sys
for x in [t.Timer(int(a),print,[a]) for a in sys.argv[1:]]:x.start()

Prend la saisie via la ligne de commande

./sleep-sort\ v0.py 1 7 5 2 21 15 4 3 8

Comme avec beaucoup de golfs python, il arrive un moment où le code est suffisamment compact pour que les variables qui aliasent pour raccourcir les noms n'enregistrent même pas les caractères.

Celui-ci est génial, car il alias sys et en enfilant BOTH en tant que t, donc sys.argv devient t.argv. Plus court que de foo import *, et une économie nette de caractère! Cependant, je suppose que Guido ne serait pas content ...

Note pour apprendre par vous-même et arrêter de jouer au python. La vache sainte est plus courte que la solution C!

Pour le plaisir, voici une version ColdFusion (8+) ;-) Elle compte 109 caractères, sans compter les retours à la ligne et les indentations que j'ai ajoutés pour la lisibilité ici.

<cfloop array="#a#" index="v">
  <cfthread><cfthread action="sleep" duration="#v*1000#"/>#v#</cfthread>
</cfloop>

Cela suppose que <cfoutput>c'est en vigueur. Quelques caractères pourraient être sauvegardés en écrivant le tout sur une seule ligne.

Java (aka ne gagne jamais à codegolf): 234 211 187 caractères

public class M{public static void main(String[]s){for(final String a:s)new Thread(){public void run(){try{sleep(Long.parseLong(a));}catch(Exception e){}System.out.println(a);}}.start();}}

ungolfed:

public class M {
    public static void main(String[] s) {
        for(final String a:s) new Thread(){
            public void run() {
                try {
                    sleep(Long.parseLong(a));
                } catch(Exception e){}
                System.out.println(a);
            }
        }.start();
    }
}

Javascript - 52 caractères

for(i in a)setTimeout("console.log("+a[i]+")",a[i])

Scala - 42 40 caractères (cas particulier)

Si vous avez un pool de threads au moins égal à la taille du nombre d'éléments de la liste:

a.par.map{i=>Thread.sleep(i);println(i)}

Scala - 72 caractères (général)

a.map(i=>new Thread{override def run{Thread.sleep(i);println(i)}}.start)

Haskell - 143 caractères

import Control.Concurrent
import System
d=threadDelay
f x=d(10^6*x)>>print x
g s=mapM(forkIO.f)s>>d(10^6*maximum s+1)
main=getArgs>>=g.map read

Cela pourrait probablement être raccourci en prenant l'entrée sur stdin si c'était une option, mais il est tard et de toute façon, il reste encore 104 caractères pour la fonction elle-même.

Befunge-98, 38 31 octets

Je sais que c’est un vieux défi, mais j’ai récemment découvert les langages 2D et le trio de sommeil, je savais comment les combiner et je cherchais un endroit pour les poster. Nous y sommes donc.

&#vt6j@p12<'
v:^ >$.@
>:!#^_1-

L’IP principale lit un nombre ( &), puis appuie sur celui tqui le clone: ​​on continue sur la même ligne et cycle, lisant de nouveaux numéros et générant de nouveaux enfants jusqu’à atteindre EOF qui termine la séquence. Tous les processus enfants restent bloqués dans une boucle fermée (le vet ^de la troisième colonne) jusqu'à ce que l'adresse IP principale termine la lecture de l'entrée et exécute la séquence de commandes '<21p, ce qui met le caractère <à la position (1,2), écrasant le tout ^et libérant tout. les processus enfants, qui commencent à cycler simultanément, réduisent de 1 leur nombre à chaque itération. Étant donné que la vitesse d'exécution de différentes adresses IP est synchronisée dans befunge, elles se termineront (et afficheront leur valeur) dans l'ordre, en triant la liste des entrées.

Un peu tard pour la fête:

Maple - 91 83 caractères

En 91:

M:=():use Threads in p:=proc(n)Sleep(n);:-M:=M,n;end:Wait(map(i->Create(p(i)),L)[])end:[M];

En 83:

M:=():use Threads in Wait(seq(Create(proc(n)Sleep(n);:-M:=M,n end(i)),i=L))end:[M];

(Cela nécessite la version 15 de Maple et attend que la liste soit triée en L)

C, 70 69 caractères

N'attend pas le retour des processus enfants, sinon fonctionne.

main(n) {
    while(~scanf("%d",&n)?fork()||!printf("%d\n",n,sleep(n)):0);
}

PHP 57 octets

<?for(;$i=fgets(STDIN);)pcntl_fork()?:die($i.usleep($i));

pcntl_fork () est uniquement disponible sous linux.

Bash (38):

xargs -P0 -n1 sh -c 'sleep $0;echo $0'

Edit: virgule flottante à partir de stdin, séparés par des espaces ou des nouvelles lignes.

Haskell, 90

import Control.Concurrent
s::[Int]->IO()
s=mapM_(\x->forkIO$threadDelay(x*9999)>>print x)

J'espère que cela répond à toutes les exigences.

, 11 caractères / 22 octets

ïć⇝שĤ⇀ôa,a⸩

Try it here (Firefox only).

שĤ⇀ôa, ça a l'air cool.

Quelques modifications de la version de @rmckenzie:

Python retardé thread commence dans 155 152 114 108 107:

import sys, threading as t
for x in [t.Timer(int(a),sys.stdout.write,[a]) for a in sys.argv[1:]]:x.start()

Python sans délai en 130 128 96 95 93:

import sys,threading as t
for a in sys.argv[1:]:t.Timer(int(a),sys.stdout.write,[a]).start()

Géré quelques optimisations supplémentaires, en utilisant à la Timerplace de Thread, qui a un appel plus concis et supprime le besoin d'importer time. La méthode de démarrage différée des threads bénéficie de la compréhension de liste car elle évite d'avoir à initialiser la liste séparément au début, bien qu'elle soit plus longue de deux caractères ( "["+"]"+" "-":") que la boucle for, elle est donc inutile sans démarrage différé et vous devez faire attention à utiliser une liste. au lieu d’un générateur, ou si vous ne créez pas les threads du minuteur tant que vous n’avez pas utilisé le générateur.

Est-ce que quelqu'un d'autre a des optimisations?

Le truc avec asaide, mais dans la version 2.7.1, vous ne pouvez importer qu'un seul module dans un alias, et après quelques jeux à propos de vous import mod1,mod2 as a,b, vous ne pouvez même pas , vous devez le faire import mod1 as a, mod2 as b. Il sauve toujours quelques caractères, mais ce n’est pas tout à fait le remède que je pensais ... Et en fait, il vaut mieux laisser sys en tant que sys. L'aliasing threading aide toujours bien ...

Clojure, 54

(defn s[n](doseq[i n](future(Thread/sleep i)(prn i))))

Rouille - 150 octets

Et c’est pourquoi vous ne codez pas le golf dans Rust, c’est plus bavard que Java;). Dépend de caisse externe crossbeam, ce serait encore pire sans elle.

|x|{extern crate crossbeam;crossbeam::scope(|s|for&v in x{s.spawn(move||{std::thread::sleep(std::time::Duration::from_secs(v));println!("{}",v)});})}

Programme de test complet:

fn main() {
    let z =
    |x|{extern crate crossbeam;crossbeam::scope(|s|for&v in x{s.spawn(move||{std::thread::sleep(std::time::Duration::from_secs(v));println!("{}",v)});})}
    ;
    z(&[4, 2, 3, 5, 7, 8, 9, 1, 6, 10])
}

Un peu ennuyeux, port du C #, juste pour recommencer avec le langage:

F # - 90 caractères

PSeq.withDegreeOfParallelism a.Length a|>PSeq.iter(fun x->Thread.Sleep(x);printfn "%A" x)

JavaScript, 74

function(a){for(i=0;i<a.length;i++)setTimeout('alert('+a[i]+')',a[i]*1e3)}

ou 71/65 caractères non standard:

function(a){a.map(function(v){setTimeout('console.log('+v+')',v*1e3)})}

Tcl 8.6, 41 caractères

lmap c $argv {after $c "puts $c"};vwait f

Vous devez le tuer avec ^C

VB.NET 100 octets

Parce que VB.Net exige que les lambdas sur une seule ligne ne contiennent qu'une seule instruction, ce code doit comporter plusieurs lignes:

Array.ForEach(i, Async Sub(x)
Await Threading.Tasks.Task.Delay(x*1000)
Console.WriteLine(x)
End Sub)

Ungolfed:

Option Strict Off

Sub Main(i() as String)
    Array.ForEach(i, Async Sub(x)
                         Await Threading.Tasks.Task.Delay(x * 1000)
                         Console.WriteLine(x)
                     End Sub)
End Sub

Cependant, je ne sais pas si vous comptez les déclarations imports dans les comptes d'octets, car si vous ne les comptez pas, je pourrais écrire ceci:

VB.NET 71 octets

a.ForEach(i, Async Sub(x)
Await t.Delay(x*1000)
c.WriteLine(x)
End Sub)

Ungolfed:

Option Strict Off
Imports t = System.Threading.Tasks.Task
Imports c = System.Console
Imports a = System.Array

Sub Main(i() as String)
    a.ForEach(i, Async Sub(x)
                     Await t.Delay(x * 1000)
                     c.WriteLine(x)
                 End Sub)
End Sub

Groovy, 47 octets

Suppose que les numéros sont donnés sur la ligne de commande ...

args.each{i->Thread.start{sleep(i*22)print i}}

Mathematica, 34 ou 36 octets

RunScheduledTask[Print@#,{#,1}]&/@

Il suffit d’ajouter la liste à trier à la fin de ce code et d’évaluer. Si la définition de la fonction doit être valide, deux octets supplémentaires sont nécessaires:

RunScheduledTask[Print@#,{#,1}]&/@#&

C ++ 11, 229 octets

#import<future>
#import<iostream>
using namespace std;int main(int a,char**v){auto G=new future<void>[a];while(--a){G[a]=move(async([=](){this_thread::sleep_for(chrono::seconds(atoi(v[a])));cout<<v[a]<<" "<<flush;}));}delete[]G;}

Ungolfed et utilisation:

#import<future>
#import<iostream>
using namespace std;
int main(int a,char**v){
 auto G=new future<void>[a];
 while(--a){
  G[a]=move(async(
   [=](){
    this_thread::sleep_for(chrono::seconds(atoi(v[a])));
    cout<<v[a]<<" "<<flush;
   }
  ));
 }
 delete[]G;
}