<div dir="ltr">Szuper, akkor az első nagybead-hoz a feladatsort pár napon belül elküldöm példa megoldással együtt. Így már csak a második beadandón kell gondolkodni, bár az még pár hetet ráér.<div><br></div><div>Andor</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Oct 10, 2021 at 6:40 PM Grünwald Péter <<a href="mailto:grunci@gmail.com">grunci@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">
<div>Szia!</div><div>Szerintem jó feladat, megfelelően bonyolult ahhoz, hogy beadandónak lehessen nevezni.</div><div>Bár van egy olyan érzésem, hogy elég sok 5 pontos beadandóval fogok találkozni :)</div><div><br></div><div>Üdv,</div><div>Grünci</div>

</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Oct 10, 2021 at 1:46 PM Menczer Andor <<a href="mailto:menczer.andor@gmail.com" target="_blank">menczer.andor@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Sziasztok,<div><br></div><div>Első beadról már kérdezgetnek a hallgatók, úgy tűnik hogy őszi szünet elejére szeretnék ha meglenne.</div><div><br></div><div>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.</div><div><br></div><div>Nagyon nagy vonalakban erről lenne szó:</div><div><ul><li>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ó.</li><li>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.</li><li>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</li></ul>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...</div><div><br></div><div>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á.</div><div><br></div><div>Üdv,</div><div>Andor</div></div>
_______________________________________________<br>
Konkurens mailing list<br>
<a href="mailto:Konkurens@plc.inf.elte.hu" target="_blank">Konkurens@plc.inf.elte.hu</a><br>
<a href="https://plc.inf.elte.hu/mailman/listinfo/konkurens" rel="noreferrer" target="_blank">https://plc.inf.elte.hu/mailman/listinfo/konkurens</a><br>
</blockquote></div>
</blockquote></div>