Sleep Sort ist ein ganzzahliger Sortieralgorithmus, den ich im Internet gefunden habe. Es öffnet einen Ausgabestream und verzögert für jede parallel eingegebene Nummer die Anzahl der Sekunden und gibt diese Nummer aus. Aufgrund der Verzögerungen wird die höchste Zahl zuletzt ausgegeben. Ich schätze, es hat O (n + m), wobei n die Anzahl der Elemente und m die höchste Zahl ist.

Hier ist der Originalcode in Bash

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

Hier ist der 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

Ihre Aufgabe ist es, Sleep Sort als Funktion in der Programmiersprache Ihrer Wahl zu implementieren. Sie können Nebenläufigkeitsfaktoren wie Rennbedingungen vernachlässigen und niemals freigegebene Ressourcen sperren. Der kürzeste Code gewinnt. Die Funktionsdefinition wird auf die Codelänge angerechnet.

Die Eingabeliste ist nur auf nicht negative Ganzzahlen beschränkt, und die Länge der Eingabeliste sollte angemessen lang sein (mindestens 10 Zahlen testen), damit keine Rennbedingungen eintreten. und unter der Annahme, dass die Rennbedingungen niemals eintreten.

Eine Art lahmer Perl- Versuch, 59 55 52 38 32 Zeichen :

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

Barebones: 25 Zeichen:

... wenn Ihnen die Sortierergebnisse als Ausgabe nichts ausmachen:

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

Mit allen Zutaten:

(für maximale Herausforderung, 44 Zeichen)

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

Wenn Sie perl warten lassen, 39 Zeichen:

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

Und wieder, wenn es Ihnen nichts ausmacht die(), 32 Zeichen ...

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

Beachten Sie, dass es in Perl 6 oder bei Deklaration der printFunktion 'say' möglich ist, die Funktion durch zu ersetzen sayund jeweils ein Zeichen zu speichern. Da diebeide den Fork-Prozess beenden und die Ausgabe schreiben, bleibt dies offensichtlich die kürzeste Lösung.

C , 127 Zeichen, eine ziemlich offensichtliche Lösung:

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);}}

(Kompiliert mit gcc -std=c99 -fopenmp sort.cund ignoriert alle Warnungen.)

Ruby 1.9, 32 Zeichen

Als eine Funktion:

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

Wenn wir nur eine vordefinierte Variable verwenden können, wird diese auf 25 Zeichen reduziert:

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

JavaScript , 65 Zeichen (abhängig davon, ob Sie console.logfür die Ausgabe des Ergebnisses etwas anderes verwenden oder verwenden)

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

Dies setzt voraus, dass aes sich um ein Array nicht negativer Ganzzahlen handelt, map()das auf dem Array-Prototyp (JavaScript 1.6+) vorhanden ist.

APL ( 15 13)

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

Was es macht:

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

Vier Versuche in Erlang:

Bei der Ausgabe an die Konsole haben wir uns die Freiheit genommen, dies jeweils zu tun, 9ms * Numberda dies ausreicht, um es zum Laufen zu bringen (getestet auf einem Atom-Embedded-Board = langsam):

Benötigt 60 Zeichen

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

Die Ausgabe auf der Konsole ist vollständig ohne Erlangish, daher senden wir Pstattdessen eine Nachricht an process :

Benötigt 55 Zeichen

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

Das Senden nach einer bestimmten Zeit kann auch anders erfolgen (dies funktioniert sogar mit 1ms * Number):

Benötigt 41 Zeichen

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

Tatsächlich ist dies etwas unfair, da die eingebaute Funktion send_afterspät dran ist und den Namensraum als erlang:Präfix benötigt, wenn wir diesen Namensraum als importiert betrachten (auf Modulebene):

Benötigt 34 ​​Zeichen

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

C # - 137 Zeichen

Hier ist eine Antwort in C # (aktualisiert mit Grad der Parallelität wie kommentiert)

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 @ BiggAls Code, da das das Spiel ist, das wir spielen ...

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

... oder 97 175 mit verzögertem Threadstart

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

Übernimmt die Eingabe über die Kommandozeile

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

Wie bei vielen Python-Golfspielen kommt ein Punkt, an dem der Code so kompakt ist, dass Aliasing-Variablen zum Kürzen von Namen nicht einmal Zeichen speichern.

Dieser ist jedoch irre, weil er sys als Alias ​​verwendet und BEIDES als t einfädelt, sodass sys.argv zu t.argv wird. Kürzer als von foo import * und eine Netto-Charakterersparnis! Allerdings würde sich Guido wohl nicht darüber freuen ...

Beachten Sie, c selbst zu lernen und das Golfen in Python zu beenden. HEILIGE KUH, DAS IST KÜRZER ALS DIE C-LÖSUNG!

Zum Spaß ist hier eine ColdFusion (8+) Version ;-) Es hat 109 Zeichen ohne Zeilenumbrüche und Einrückungen, die ich hier zur besseren Lesbarkeit hinzugefügt habe.

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

Dies setzt voraus, dass dies der Fall <cfoutput>ist. Ein paar Zeichen können gespeichert werden, indem alles in eine Zeile geschrieben wird.

Java (aka gewinnt nie bei Codegolf): 234 211 187 Zeichen

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 Zeichen

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

Scala - 42 40 Zeichen (Sonderfall)

Wenn Sie einen Thread-Pool haben, der mindestens so groß ist wie die Anzahl der Listenelemente:

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

Scala - 72 Zeichen (allgemein)

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

Haskell - 143 Zeichen

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

Dies könnte wahrscheinlich durch Eingabe von stdin verkürzt werden, wenn dies eine Option wäre, aber es ist spät und es sind immer noch 104 Zeichen für die Funktion selbst.

Befunge-98, 38 31 Bytes

Ich weiß, dass dies eine alte Herausforderung ist, aber ich habe vor kurzem sowohl Sleepsort- als auch 2D-Sprachen entdeckt, hatte eine Idee, wie ich sie kombinieren kann, und suchte nach einem Ort, an dem ich sie posten kann. Also sind wir hier.

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

Die Haupt-IP liest eine Zahl ( &) und trifft dann die, tdie sie klont: Man fährt in derselben Zeile fort und durchläuft die Zyklen, liest neue Zahlen und erzeugt neue Kinder, bis sie EOF erreichen, was die Sequenz beendet. Alle untergeordneten Prozesse bleiben in einer geschlossenen Schleife (das vund ^der dritten Spalte) hängen, bis die Haupt-IP das Lesen der Eingabe beendet und die Befehlssequenz ausführt '<21p, die das Zeichen <auf Position (1,2) setzt, das überschreibt ^und alle freigibt Die untergeordneten Prozesse, die gleichzeitig zu zyklisieren beginnen, reduzieren ihre Anzahl bei jeder Iteration um 1. Da die Ausführungsgeschwindigkeit verschiedener IPs in befunge synchronisiert ist, werden sie nacheinander beendet (und drucken ihren Wert) und sortieren die Eingabeliste.

Ein bisschen zu spät zur Party:

Ahorn - 91 83 Zeichen

In 91:

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

In 83:

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

(Dies benötigt Maple Version 15 und erwartet, dass die Liste in L sortiert wird.)

C, 70 69 Zeichen

Wartet nicht auf die Rückkehr der untergeordneten Prozesse, sonst funktioniert es.

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

PHP 57 Bytes

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

pcntl_fork () ist nur unter Linux verfügbar.

Schlag (38):

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

Bearbeiten: Gleitkomma von Standard, getrennt durch Leerzeichen oder Zeilenumbrüche.

Haskell, 90

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

Ich hoffe das erfüllt alle Anforderungen.

𝔼𝕊𝕄𝕚𝕟 11 Zeichen / 22 Bytes

ïć⇝שĤ⇀ôa,a⸩

Try it here (Firefox only).

שĤ⇀ôaDas sieht cool aus.

Nur ein paar Optimierungen aus @rmckenzies Version:

Python verzögerter Threadstart in 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 ohne Verzögerung in 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()

Verwaltete ein paar weitere Optimierungen mit Timeranstelle von Thread, die einen präziseren Aufruf haben und den Import überflüssig machten time. Die Methode für verzögerten Thread-Start profitiert vom Listenverständnis, da die Liste zu Beginn nicht mehr separat initialisiert werden muss, obwohl sie zwei Zeichen länger ist ( "["+"]"+" "-":") als die for-Schleife, sodass sie ohne verzögerten Start unbrauchbar ist und Sie vorsichtig mit einer Liste umgehen müssen anstatt eines Generators, oder Sie erstellen die Timer-Threads erst dann, wenn Sie den Generator durchlaufen haben.

Hat noch jemand irgendwelche Optimierungen?

Der Trick mit asHilfen, aber in 2.7.1 können Sie nur ein Modul in einen Alias ​​importieren, und nach einigem Herumspielen können Sie nicht einmal import mod1,mod2 as a,b, müssen Sie import mod1 as a, mod2 as b. Es werden immer noch ein paar Zeichen gespeichert, aber es ist nicht ganz das Heilmittel - alles, was ich dachte ... Und in der Tat ist es besser, sys als sys zu belassen. Aliasing Threading hilft trotzdem ...

Clojure, 54

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

Rust - 150 Bytes

Und aus diesem Grund programmieren Sie Golf nicht in Rust, es ist ausführlicher als Java;). Hängt von der äußeren Kiste ab crossbeam, ohne wäre es noch schlimmer.

|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)});})}

Komplettes Testprogramm:

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])
}

Irgendwie langweilig, Portierung von C #, nur um wieder mit der Sprache zu beginnen:

F # - 90 Zeichen

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)}

oder 71/65 Zeichen mit Nichtstandardität:

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

Tcl 8,6, 41 Zeichen

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

Du musst es mit töten ^C

VB.NET 100 Bytes

Da in VB.Net einzeilige Lambdas nur eine Anweisung enthalten müssen, muss dieser Code mehrere Zeilen enthalten:

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

Ich bin mir jedoch nicht sicher, ob Sie die Anzahl der importierten Anweisungen in der Byteanzahl angeben, da ich Folgendes schreiben könnte, wenn Sie sie nicht zählen:

VB.NET 71 Bytes

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 Bytes

Angenommen, Zahlen werden in der Befehlszeile angegeben ...

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

Mathematica, 34 oder 36 Bytes

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

Einfach die zu sortierende Liste an das Ende dieses Codes anhängen und auswerten. Wenn es sich um eine gültige Funktionsdefinition handeln muss, sind zwei zusätzliche Bytes erforderlich:

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

C ++ 11, 229 Bytes

#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 und Nutzung:

#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;
}