Mikä on unilajittelu?


Paras vastaus

Unilajittelu on vitsilajittelualgoritmi, josta tuli suosittu 4-kanavaisella levyllä / prog / [1]. Nukkumistavan pseudokoodi on:

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! Hilpeä .

Toisin sanoen, se tarkoittaa, että unilaji synnyttää yhden prosessin jokaiselle argumentille. Jokainen prosessi odottaa n sekuntia ja tulostaa sitten n, mikä tarkoittaa, että ”1”: n tulostaminen vie 1 sekunnin, tulostus kestää 2 sekuntia tulostaa ”2”, 100 sekuntia tulostaa ”100”. Tämä tarkoittaa, että numerot tulostetaan suurimmaksi osaksi niiden koon mukaisessa järjestyksessä, jolloin argumentit ”lajitellaan”.

Tämän algoritmin monimutkaisuus täydellisessä maailmassa on O(max(args)), koska suurimman arg -tulostaminen kestää max(args) sekuntia. Todellisuudessa monimutkaisuus on O(n^2 + max(args)), koska useiden taustaprosessien ylläpitäminen riippuu käyttöjärjestelmästä prosessin kontekstikytkennän ja priorisoinnin hallinnassa, joten algoritmi ulkoistaa todellisen lajittelun ydin.

Huomaa myös, että ei ole takeita siitä, että lajittelun tulos on oikea, ominaisuus, jota useimmilla muilla lajittelualgoritmeilla ei ole. div id = ”2cac47db7e”>

Vastaa

Hauskanpidon vuoksi Erlangissa on toteutus

sort(L) ->

Parent = self(),

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

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

Joka voidaan kirjoittaa hienosti yhtenä lausekkeena myös Erlang-kuoressa

[ receive X -> X end

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

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

Vastaa

Sähköpostiosoitettasi ei julkaista. Pakolliset kentät on merkitty *