Sleep Sort to algorytm sortowania liczb całkowitych, który znalazłem w Internecie. Otwiera strumień wyjściowy i dla każdej liczby wejściowej równolegle opóźnia liczbę sekund i wysyła tę liczbę. Ze względu na opóźnienia najwyższa liczba zostanie wyprowadzona na końcu. Szacuję, że ma O (n + m), gdzie n to liczba elementów, a m to najwyższa liczba.

Oto oryginalny kod w Bash

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

Oto pseudokod

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

Twoim zadaniem jest wdrożenie funkcji Sleep Sort jako funkcji w wybranym języku programowania. Możesz pominąć wszelkie czynniki współbieżności, takie jak warunki wyścigu i nigdy nie blokować żadnych wspólnych zasobów. Najkrótszy kod wygrywa. Definicja funkcji liczy się do długości kodu.

Lista wejściowa jest ograniczona tylko do nieujemnych liczb całkowitych, a długość listy wejściowej powinna być odpowiednio długa (przetestuj co najmniej 10 liczb), aby warunki wyścigu nigdy się nie zdarzyły. i zakładając, że warunki wyścigowe nigdy się nie zdarzają.

Rodzaj kiepskiej próby Perla , 59 55 52 38 32 znaków :

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

Gołe kości: 25 znaków:

... jeśli nie masz nic przeciwko sortowaniu wyników jako wyniku wyjściowego:

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

Ze wszystkimi dodatkami:

(dla maksymalnej zgodności z wyzwaniem, 44 znaki)

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

Jeśli pozwolisz Perlowi na ciebie czekać, 39 znaków:

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

I znowu, jeśli nie masz nic przeciwko die(), 32 znaki ...

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

Zauważ, że w Perlu 6 lub gdy deklarowana jest funkcja „powiedz”, można zastąpić tę printfunkcję say, zapisując znak w każdym przypadku. Oczywiście, ponieważ dieoba kończą rozwidlony proces i zapisują dane wyjściowe, pozostaje to najkrótsze rozwiązanie.

C , 127 znaków, dość oczywiste rozwiązanie:

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

(Kompilowany gcc -std=c99 -fopenmp sort.ci ignorujący wszystkie ostrzeżenia.)

Ruby 1.9, 32 znaki

Jako funkcja:

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

Jeśli możemy po prostu użyć predefiniowanej zmiennej, zmniejsza się ona do 25 znaków:

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

JavaScript , 65 znaków (w zależności od tego, czy używasz, console.logczy czegoś innego do wyświetlania wyniku)

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

Zakłada się, że ajest to tablica liczb całkowitych nieujemnych i map()istnieje w prototypie macierzy (JavaScript 1.6+).

APL ( 15 13)

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

Co to robi:

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

Cztery próby w Erlang:

Wyjdź na konsolę, skorzystaj z tej możliwości, 9ms * Numberponieważ jest to wystarczająco dużo, aby działało (testowane na płycie wbudowanej Atom = wolno):

Potrzebuje 60 znaków

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

Dane wyjściowe na konsolę są całkowicie nienawistne, więc Pzamiast tego wysyłamy komunikat do przetworzenia :

Potrzebuje 55 znaków

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

Wysyłanie po pewnym czasie można również wykonać inaczej (działa to nawet z 1ms * Number):

Potrzebuje 41 znaków

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

W rzeczywistości jest to trochę niesprawiedliwe, ponieważ wbudowana funkcja send_afterjest opóźniona i wymaga erlang:prefiksu przestrzeni nazw , jeśli weźmiemy pod uwagę tę przestrzeń nazw zaimportowaną (wykonaną na poziomie modułu):

Potrzebuje 34 znaków

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

C # - 137 znaków

Oto odpowiedź w języku C # (zaktualizowana o stopnie równoległości zgodnie z komentarzem)

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

Poprawianie kodu @ BiggAl, ponieważ w tę grę gramy ....

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

... lub 97 175 z opóźnionym uruchomieniem wątku

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

Pobiera dane z wiersza poleceń, ala

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

Podobnie jak w przypadku wielu golfów pythonowych, pojawia się moment, w którym kod jest na tyle zwarty, że aliasing zmiennych w celu skrócenia nazw nawet nie zapisuje znaków.

Ten jest jednak funky, ponieważ alias sys i wątki ZARÓWNO jako t, więc sys.argv staje się t.argv. Krótszy niż z importu foo * i oszczędności postaci netto! Jednak przypuszczam, że Guido nie byłby zadowolony ...

Uwaga do samodzielnego uczenia się c i zaprzestania gry w python. ŚWIĘTA KRÓWKA JEST KRÓTSZE NIŻ ROZWIĄZANIE C!

Dla zabawy, oto wersja ColdFusion (8+) ;-) Ma 109 znaków, nie licząc zawijania linii i wcięć, które dodałem tutaj dla czytelności.

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

Zakłada się, że <cfoutput>to działa. Kilka znaków można zapisać, pisząc wszystko w jednym wierszu.

Java (aka nigdy nie wygrywa w codegolf): 234 211 187 znaków

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

bez golfa:

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 znaki

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

Scala - 42 40 znaków (przypadek specjalny)

Jeśli masz pulę wątków, co najmniej rozmiar liczby elementów listy:

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

Scala - 72 znaki (ogólnie)

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

Haskell - 143 znaki

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

Prawdopodobnie można by to skrócić, przyjmując wejście na stdin, gdyby to była opcja, ale jest już późno i tak czy inaczej, nadal ma 104 znaki dla samej funkcji.

Befunge-98, 38 31 bajtów

Wiem, że to stare wyzwanie, ale niedawno odkryłem zarówno sleepsort, jak i języki 2D, wpadłem na pomysł, jak je połączyć i szukałem miejsca, aby je opublikować, więc oto jesteśmy.

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

Główny adres IP odczytuje liczbę ( &), a następnie uderza w to, tktóry go klonuje: jeden przechodzi do tej samej linii i wykonuje cykle, odczytuje nowe liczby i generuje nowe potomki, aż osiągnie EOF, który kończy sekwencję. Wszystkie procesy potomne utkną w zamkniętej pętli ( vi ^trzeciej kolumny), dopóki główny adres IP nie zakończy odczytu danych wejściowych i nie wykona sekwencji poleceń '<21p, która umieszcza znak <w pozycji (1,2), zastępując ^i zwalniając wszystkie procesy potomne, które zaczynają się cyklicznie, zmniejszając o 1 ich liczbę przy każdej iteracji. Ponieważ szybkość wykonywania różnych adresów IP jest zsynchronizowana w befunge, będą one kończyć (i drukować swoją wartość) w kolejności, sortując listę danych wejściowych.

Trochę późno na imprezę:

Klon - 91 83 znaków

W 91:

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

W 83:

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

(Wymaga wersji 15 Maple i oczekuje, że lista zostanie posortowana w L)

C, 70 69 znaków

Nie czeka na powrót procesów potomnych, w przeciwnym razie działa.

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

PHP 57 bajtów

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

pcntl_fork () jest dostępny tylko w Linuksie.

Bash (38):

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

Edycja: zmiennoprzecinkowy od standardowego, oddzielony spacjami lub znakami nowej linii.

Haskell, 90

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

Mam nadzieję, że spełnia wszystkie wymagania.

𝔼𝕊𝕄𝕚𝕟, 11 znaków / 22 bajty

ïć⇝שĤ⇀ôa,a⸩

Try it here (Firefox only).

שĤ⇀ôa, to wygląda świetnie.

Tylko kilka poprawek z wersji @rmckenzie:

Python opóźniony start wątku w 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 bez opóźnienia 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()

Zarządzałem kilkoma dodatkowymi optymalizacjami, używając Timerzamiast Thread, który ma bardziej zwięzłe wywołanie i wyeliminował potrzebę importowania time. Metoda opóźnionego startu wątku korzysta ze zrozumienia listy, ponieważ eliminuje potrzebę oddzielnego inicjowania listy na początku, chociaż jest ona o dwa znaki dłuższa ( "["+"]"+" "-":") niż pętla for, więc jest bezużyteczna bez opóźnionego startu i należy uważać, aby użyć listy zamiast generatora, albo tak naprawdę nie tworzysz wątków timera, dopóki nie poruszysz generatora.

Czy ktoś jeszcze ma jakieś optymalizacje?

Sztuczka z pomocą aspomaga, ale w wersji 2.7.1 możesz zaimportować tylko jeden moduł do aliasu, a po niektórych zabawach o tobie nie możesz, nawet import mod1,mod2 as a,bmusisz import mod1 as a, mod2 as b. Wciąż oszczędza kilka postaci, ale to nie jest lekarstwo - wszystko, co myślałem, że to było ... I w rzeczywistości lepiej zostawić sys jako sys. Aliasing wątków wciąż pomaga ...

Clojure, 54

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

Rdza - 150 bajtów

I dlatego nie piszesz golfa w Rust, jest bardziej gadatliwy niż Java;). Zależy od zewnętrznej skrzynki crossbeam, bez niej byłoby jeszcze gorzej.

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

Pełny program testowy:

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

Trochę nudne, port C #, żeby znów zacząć korzystać z języka:

F # - 90 znaków

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

lub 71/65 znaków o niestandardowym charakterze:

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

Tcl 8.6, 41 znaków

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

Musisz to zabić ^C

VB.NET 100 bajtów

Ponieważ VB.Net wymaga, aby lambda w jednym wierszu zawierały tylko jedną instrukcję, ten kod musi zawierać wiele wierszy:

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

Nie golfowany:

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

Jednak nie jestem pewien, czy policzymy instrukcje importu w liczbie bajtów, ponieważ jeśli ich nie policzymy, mógłbym napisać:

VB.NET 71 bajtów

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

Nie golfowany:

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 bajtów

Zakłada, że ​​liczby są podane w wierszu poleceń ...

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

Mathematica, 34 lub 36 bajtów

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

Wystarczy dołączyć listę do posortowania na końcu tego kodu i ocenić. Jeśli musi to być poprawna definicja funkcji, zajmuje dwa dodatkowe bajty:

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

C ++ 11, 229 bajtów

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

Niegolfowane i użytkowanie:

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