Mi az alvásfajta?


Legjobb válasz

Az alvási rendezés egy viccek rendezési algoritmusa, amely népszerűvé vált a 4chan táblán / prog / [1]. Az alvási rend pszeudokódja:

procedure printNumber(n)

sleep n seconds

print n

end

for arg in args

run printNumber(arg) in background

end

wait for all processes to finish

Ha-ha! Vidám .

Más szavakkal, más szavakkal azt jelenti, hogy az alvásfajta minden argumentumhoz egy folyamatot hoz létre. Minden folyamat n másodpercet vár, majd kinyomtatja a n -t, vagyis 1 másodperc, 2 másodperc a nyomtatás “2”, 100 másodperc a “100” kinyomtatásához. Ez azt jelenti, hogy a számok többnyire a méretük szerinti sorrendben kerülnek kinyomtatásra, ezzel “rendezve” az argumentumokat.

Ezen algoritmus összetettsége egy tökéletes világban O(max(args)), mivel max(args) másodpercekbe telik a legnagyobb arg kinyomtatása. A valóságban a bonyolultság O(n^2 + max(args)), mert a több háttérfolyamat fenntartása az operációs rendszerre támaszkodik a kontextusváltás és a folyamatok rangsorolásának kezelésében, ezért az algoritmus alapvetően kiszervezi a tényleges rendezést a kernel.

Vegye figyelembe azt is, hogy nincs garancia arra, hogy a rendezés kimenete valóban helyes, ez a tulajdonság a legtöbb más rendezési algoritmusnak nincs.

[1] http://dis.4chan.org/read/prog/1295544154

Válasz

Csak szórakozásból van megvalósítás az Erlang

sort(L) ->

Parent = self(),

[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],

[ receive X -> X end || \_ <- L ].

Amely szépen írható egy kifejezésként az Erlang shellbe is

[ receive X -> X end

|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)

|| P <- [self()], X <- L ] ].

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük