[Konkurens] konkurens első beadandó

[Menczer Andor]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://plc.inf.elte.hu/pipermail/konkurens/attachments/20211010/f5a4c7c6/attachment.html>