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.
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.
A megoldásotokat kipróbálhatjátok a mellékelt Tester.java 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 Arrays.sort() illetve az első és második feladat rendező algoritmusával is rendezni próbálja. A futási időket konzolra kiírja. Az -ea 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 Tester osztály segítségével ellenőrizhetjük a rendező algoritmusok sebességét és helyességét.
Dolgozni a Task1.java és Task2.java fájlokban kell. Újabb fájlokat vagy package információt mindenki kénye kedve szerint adhat hozzá.
Az Arrays.sort() 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.
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 int[][] slice(int[] arr, int k) metódust ami k darabra vág egy tömböt.
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 int[] merge(int[] arr1, int[] arr2) metódust ami az összefésüléses rendezésből ismert ősszefésülést végzi el.
Ha a szétdarabolást és összefésülést megírtuk már csak maga a int[] sort(int[] array) 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 Runtime.getRuntime().availableProcessors() 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 for 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 :)
Az előző feladatban definiált algoritmus szinte minden modern x86-64 számítógépen gyorsabb lesz mint az Arrays.sort() 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.
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.
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 main-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 Thread.join() segítségével bevártuk a szálat, már csak azt a bizonyos egyetlen összefésülést kell elvégeznünk.
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.
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 Arrays.sort() meghívása.
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 Arrays.sort() 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.
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.
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 main-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.