[Konkurens] konkurens első beadandó

[Menczer Andor]

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.

Andor

On Sun, Oct 10, 2021 at 6:40 PM Grünwald Péter <grunci at gmail.com> wrote:

> 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/8a82299c/attachment.html>