<title>MergeSort – Bead1</title>
<h1>Álalános infók</h1>
<p>Feladattal kapcsolatos kérdés esetén a menczer.andor@gmail.com email címen vagy teamsen keressetek. Ez hallgatókra és gyakvezekre egyaránt vonatkozik. Amennyiben a feladatkiírás hibás vagy nem egyértelmű, akkor a feladat szövegét javítani fogom.</p>
<p>A feladat egy rendező algoritmus megírása, melyre legfeljebb 15 pontot lehet kapni. Ennek van egy egyszerűbb, de lassabb, illetve bonyolultabb, de cserébe gyorsabb változata. A 15 pont megszerzéséhez elegendő a gyorsabb rendező algoritmus megírása. Ekkor használjátok teszteléskor a lassabb helyett is a gyorsabbat. Kevesebb pontért megoldható az egyszerűbb feladat, illetve ezt "felokosítani" lehet kényelmesebb mint nulláról rögtön a gyorsabbat megírni.</p>
<p>A megoldásotokat kipróbálhatjátok a mellékelt <code>Tester.java</code> fájl segítségével. Az itt található osztály paraméterül bekéri a rendezendő tömb hosszát, majd generál egy ilyen hosszúságú pszeudo-random int tömböt. A létrehozott tömböt az <code>Arrays.sort()</code> illetve az első és második feladat rendező algoritmusával is rendezni próbálja. A futási időket konzolra kiírja. Az <code>-ea</code> kapcsoló segítségével futtatáskor a fájl végén található ellenőrzések is lefutnak. Ezzel megbizonyosodhatunk a rendező algoritmusok helyességéről. Összegezve tehát a <code>Tester</code> osztály segítségével ellenőrizhetjük a rendező algoritmusok sebességét és helyességét.</p>
<p>Dolgozni a <code>Task1.java</code> és <code>Task2.java</code> fájlokban kell. Újabb fájlokat vagy <code>package</code> információt mindenki kénye kedve szerint adhat hozzá.</p>
<h1>Task1 – alapvető többszálas rendezés összefésüléssel</h1>
<p>Az <code>Arrays.sort()</code> gyors, de nem elég gyors. Mivel ez az algoritmus egy szállal dolgozik a leglogikusabb lépésnek a többszálasítás tűnik, ha teljesítményt szeretnénk növelni. Ehhez írjunk két segédmetódust.</p>
<p>Először is gondoljuk végig hogyan lehetne a feladatot több kisebb feladatra bontani. Mivel egy nagy tömböt szeretnénk rendezni ezért kézenfekvő megoldásnak tűnik a tömb feldarabolása. Írjunk egy <code>int[][] slice(int[] arr, int k)</code> metódust ami <code>k</code> darabra vág egy tömböt.</p>
<p>Az egyes kis tömböket immáron tudjuk egymástól függetlenül, több szálon rendezni, viszont kérdés hogy hogyan pakoljuk őket egymásba. Ehhez írjuk egy <code>int[] merge(int[] arr1, int[] arr2)</code> metódust ami az összefésüléses rendezésből ismert ősszefésülést végzi el.</p>
<p>Ha a szétdarabolást és összefésülést megírtuk már csak maga a <code>int[] sort(int[] array)</code> metódus megírása van hátra. Ez viszont gyerekjáték az előzőleg már megírt metódusok segítségével. A <code>Runtime.getRuntime().availableProcessors()</code> segítségével kérjük le hány processzort támogat az adott számítógép amin a programot futtatjuk, majd ennyi részre daraboljuk fel a tömböt és ennyi szálon rendezzük párhuzamosan az egyes mini-tömböket. Ha ez megvan, hozzunk létre egy üres tömböt és egy <code>for</code> ciklus segítségével egyenként fésüljük hozzá a már külön-külön rendezett mini-tömböket. Voila :)</p>
<h1>Task2 – optimalizált párhuzamos összefésüléses rendezés</h1>
<p>Az előző feladatban definiált algoritmus szinte minden modern x86-64 számítógépen gyorsabb lesz mint az <code>Arrays.sort()</code> egymagában. Azonban van még bőven mit faragni rajta. A feldarabolás ha belegondolunk teljesen felesleges, hiszen az elemszám az algoritmus során nem változik, ezért maradhatnának az adatok együtt, csupán indexeléssel megoldható az egyes intervallumok egymástól független rendezése. Bár léteznek in-place rendezések, gyorsabb ha rendezéskor az elemeket egyúttal új helyre is pakoljuk. Ehhez viszont nem kell feldarabolni az eredeti tömböt és nem kell újabb és újabb memóriát foglalni a program futása alatt.</p>
<p>Elegendő ha a program elején létrehozunk 2 tömböt, melyek azonos hosszúak, mint a rendezendő tömb. Az elsőbe átmásoljuk a rendezendő tömb elemeit, míg a másodikat nulla vagy bármilyen értékekkel töltjük fel. Ezt az inicializációs lépést követően nem lesz szükség új tömb létrehozására. Kisebb tömbök esetén a teljes tömbre mutató referenciát fogjuk használni, de "-tól" és "-ig" indexekkel. Mivel az egyes mini-tömbök között nincs átfedés, ezért több szál nyugodtan operálhat ugyanazon a tömbön bármiféle szinkronizáció nélkül. Ne feledjük, a szinkronizáció nem a barátunk, hanem az ellenségünk, hiszen minél többet szinkronizálunk, annál lassabb lesz az algoritmusunk. Ideális esetben tehát szinkronizációmentes, mégis helyesen működő programot tudunk írni.</p>
<p>Szintén sokat nyerhetünk ha nem csak magát a mini-tömbök rendezését párhuzamosítjuk, de az összefésülést is. Ehhez dobjuk ki az előző feladat szálíindítási részeit és menjünk neki újra a feladatnak. Ideális esetben a <code>main</code>-ben mindentől függetlenül csak egyetlen összefésülésre lenne szükség. Ehhez viszont fixen 2 részre kell bontani a tömböt. Ami persze nem valós kettébontás, csupán egy index segítségével megjelöljük hol kezdődik a tömbön belül a második mini-tömb. Ha ezzel megvagyunk hozzunk létre egy testvér szálat, akinek kiadjuk utasításba, hogy rendezze a tömb egyik felét, míg mi rendezzük a másikat. Miután készen vagyunk és a <code>Thread.join()</code> segítségével bevártuk a szálat, már csak azt a bizonyos egyetlen összefésülést kell elvégeznünk.</p>
<p>Egyből két kérdést is feltehetünk, az egyszerűbb hogy hogyan fésülöm össze a tömböket. A válasz egyszerű; mindig a testvér szál elindítása előtti, még nem kettévágott tömb indexeit kell elővenni. Ez lesz a rendezendő tömb, a két fele pedig már a rendezett mini-tömbök. A két mini-tömb a program elején allokált 2 tömb egyikében lesznek. Összefésülés alatt átmásolom őket a másik tömb azonos kezdő- és végindexei közé. Maga az összefésülés ugyanúgy működik mint az első feladatban, valójában csak az indexelős mókával van megfejelve, ugyanis nem hozhatunk létre új tömböket.</p>
<p>Másik jó kérdés hogy hogyan lesz ebből tetszőlegesen sok szál, ha csak 1 testvérszálat hozhatok létre. A válasz rendkívül egyszerű: rekurzió. A testvérszálra, majd az ő útnak eresztése után magamra ugyanis nem a rendezést kell meghívni, hanem egy rekurzív metódust ami addig vág ketté amíg nem érünk el legalább annyi mini-tömbhöz mint amennyi processzor rendelkezésre áll. Ha ez megtörtént, akkor már elegendő egyszerűen az <code>Arrays.sort()</code> meghívása.</p>
<p>A folyamatos rekurziv kettévágásokkal tulajdonképpen felépítjük az összefésüléses rendezés bináris fáját. A fa minden csúcsán egy szál létrehoz egy testvért (másik szálat), aki az egyik gyereken megy tovább, míg az eredeti szál a másik gyereken keresztül folytatja útját. Miután a megfelelő részgráfot elvégezte bevárja a testvért, azaz a másik gyerek által kijelölt részgráfot, majd összefésüli a két rendezett tömböt és feljebb lép a szülőbe. Itt ha testvérként jött létre nincs további teendője és terminál. Ha ő volt a létrehozó szál, akkor pedig hasonlóan összefésül és megint feljebb lép. A leveleken fog meghívódni az <code>Arrays.sort()</code> metódus, míg minden egyes belső csúcs egy összefésülés. A párhuzamosan végezhető összefésülések azonban szintenként duplázódnak, így az algoritmus jól skálázódik nagy tömbök rendkívül sok mini-tömbre való felbontásánál is.</p>
<p>Megjegyzés: a bináris fa a programban explicit nem jelenik meg, hiszen ez csupán a rekurzió velejárója. Az összefésüléses rendezés bináris fája mondhatni egyfajta értelmezése vagy absztrakciója a rekurzív JAVA programnak.</p>
<p>Sajnos a 2 tömb közötti ide-oda másolgatás okoz egy olyan kellemetlenséget is hogy ha nem figyelünk, akkor az algoritmus végére nem fogjuk tudni a 2 tömb közül melyikben van a végleges, rendezett és teljesen összefésült megoldás. A bináris fának minden egyes szintje egy másolást jelent a két tömb között, azaz a rekurzió mélységének paritása fogja meghatározni melyik tömböt kell visszaadnunk az algoritmus végén. A paritást kiszámolhatjuk a <code>main</code>-ben vagy a rekurzió során is nyomonkövethetjük, pl visszatérési érték segítségével feljuttathatjuk a bináris fa legtetejére az inverziót követő logikai értéket.</p>