[Konkurens] konkurens első beadandó

[Grünwald Péter]

 Szia!
Szerintem jó feladat, megfelelően bonyolult ahhoz, hogy beadandónak
lehessen nevezni.
Bár van egy olyan érzésem, hogy elég sok 5 pontos beadandóval fogok
találkozni :)

Üdv,
Grünci

On Sun, Oct 10, 2021 at 1:46 PM Menczer Andor <menczer.andor at gmail.com>
wrote:

> Sziasztok,
>
> Első beadról már kérdezgetnek a hallgatók, úgy tűnik hogy őszi szünet
> elejére szeretnék ha meglenne.
>
> Már régebben írtam, de megint írom hogy régen megcsináltam párhuzamosan a
> merge sort-t, tehát fejben megvannak az optimalizálási lépések. Maga az
> alap feladat elég egyszerű, tehát akinek nem megy nagyon a tárgy is el
> tudna kezdeni dolgozni, aztán amikor jönnek az extra feladatok extra
> pontokért, addigra meg már belejönnek.
>
> Nagyon nagy vonalakban erről lenne szó:
>
>    - Van az Arrays.sort(), ez gyors, de csak 1 szálat használ, ennél kéne
>    gyorsabbat írni több szál használatával. Alapfeladat, pl 5 pontért (a
>    15-ből) lehetne annyi hogy megírják a merge sort összefésülő metódusát,
>    illetve egy feldarabolós metódust ami egy n hosszú listából k db n/k hosszú
>    listát csinál. Eddig csak Java alaptudás kellett. Eddigi órai feladatok
>    alapján pedig tudniuk kell olyat csinálni, hogy a k listát rendezik k
>    szálon az Arrays.sort() segítségével, majd a main-ben join()-nal bevárják,
>    és az összefésülő metódussal egyberakják a sok, külön külön már rendezett
>    listát. Ez baromi lassú lesz, de kezdésnek jó.
>    - Felesleges memóriafoglalásokat és másolásokat ki lehet hagyni ha nem
>    daraboljuk fel az eredeti listát k kisebb listára, csak az indexekkel
>    bűvészkedünk. Tehát legyen a program elején két n hosszú tömbünk és a
>    program futása során csak ezeket használjuk. Az első tömb maga a rendezendő
>    szám-sorozat, míg a második egy kinullázott n hosszú tömb. A rendezésnél az
>    i. szál a tömb1 i. szeletét rendezve átmásolja a tömb2 i. szeletébe. Ha ez
>    megvan akkor a main log2(n)-szer ide-oda másolja a két tömb között az
>    adatokat, az összefésülések miatt mindig duplájára nőnek a rendezett
>    szeletek méretei.
>    - Az algoritmus 2. lépése, az összefésülés is párhuzamosítható, ehhez
>    írjuk át az algoritmust úgy hogy ne a main indítson el k szálat, hanem oszd
>    meg és uralkodj alapon legyen rekurzív: minden szál, beleértve a main-t is,
>    max 1 "testvérszálat" hozzon létre ami a tömb egyik felét rendezi, míg mi
>    rendezzük a másik felét. Egy rendezésnél mindig átkerülnek az adatok a 2
>    tömb közül a másikba, viszont mivel a testvér és mi is egy rendezést /
>    másolást végzünk, ezért amikor kész van a szál és join-nal bevárja a
>    testvért, akkor ugyanabban a tömbben lesznek az adatok. A testvér és a
>    saját munkánkat fésüljük össze az eredeti tömbbe. így az adatok már
>    rendezve lesznek és az eredeti tömbben is maradnak. Ha ezt az osztd meg és
>    uralkodj algoritmust rekurzívan használjuk akkor tetszőleges 2 hatvány
>    levéllel rendelkező bináris fát fogunk kapni. Kérjük le javaban hogy hány
>    szálat támogat a gép és a legkisebb legalább ekkora kettő hatvánnyal
>    rendelkező fával futassuk az algoritmust. Ekkor a fa egyes szintjein
>    párhuzamosan fog történni az összefésülés is, maga a main egyetlen
>    összefésülést fog végezni, míg ezen optimalizáió nélkül log2(n)
>    összefésülést kéne csinálnia
>
> Ez csak piszkozat, a hallgatóknak kicsit szebben, szájbarágósabban írnám
> le, de kb ez lenne a feladat. Lehet kissé száraz, nem olyan menő vagy
> jópofa mint pl a warcraft-os, de annyi előnye talán azért van ennek is hogy
> itt lehet sebességet is mérni. Azért az egyfajta sikerélmény a hallgatónak
> és végre látná a tárgy értelmét is hogy a sima arrays.sort-nál
> nagyságrendekkel gyorsabb kódot tudott írni. Nekem pl olcsó 15 wattos gagyi
> laptopon is 3x sebességgel tudok így rendezni egy 50 millió hosszú
> pseudo-random generált int-ből álló tömböt. Egy 64 magos szerver procin már
> ég és föld különbség lenne...
>
> Mit gondoltok, ez jó lenne első beadnak? Sok dolog nem is kell hozzá,
> viszont az alapokat nagyon kell érteni. Második beadba lehetne flancos
> dolgokat rakni, wait notify, reentrant lock, executor stb, de elsőnél azaz
> a mostaninál még az alapok mély megértésére mennénk rá.
>
> Üdv,
> Andor
> _______________________________________________
> Konkurens mailing list
> Konkurens at plc.inf.elte.hu
> https://plc.inf.elte.hu/mailman/listinfo/konkurens
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://plc.inf.elte.hu/pipermail/konkurens/attachments/20211010/636c13e0/attachment-0001.html>