Stránka sa načítava, prosím čakajte…
© 2005 – 2024 Roman Horváth, všetky práva vyhradené. Dnes je 29. 3. 2024.
Dátum: 25. 3. 2014, pred viacerými rokmi, aktualizované: 6. 4. 2015, pred niekoľkými rokmi
Poznámka: Tento projekt je starší. Bude potrebné ho aktualizovať tak, aby bol kompatibilný s najnovšou verziou programovacieho rámca GRobot.
Na tejto stránke je publikovaný zdrojový kód triedy, ktorá realizuje porovnanie niekoľkých implementácií rôznych triediacich algoritmov. Výkon každého algoritmu je závislý od implementácie, v prípade jazyka Java aj od spôsobu interpretácie bajtkódu virtuálnym strojom a tiež od iných faktorov (napríklad od použitia hardvérového urýchlenia virtuálnym strojom), takže rovnaké implementácie algoritmov môžu poskytovať rôzne výsledky na rôznych platformách alebo počítačoch.
Aj napriek negrafickej orientácii kódu sú v ňom používané niektoré časti skupiny tried grafického robota. Na vygenerovanie prázdneho projektu odporúčam použiť Generátor projektov BlueJ (dostupný v sekcii Softvér na prevzatie).
~
/** * Vitajte vo veľkej súťaži triedení! Pred začatím súťaže musíme stanoviť * pravidlá súťaže!<br /> * * (1) Na to, aby boli výsledky jednotlivých triedení porovnateľné, musíme * zabezpečiť, aby všetky algoritmy (a ich optimalizované verzie) triedili * rovnaké (t. j. rovnako neusporiadané) zoznamy.<br /> * * (2) Na to, aby boli výsledky jednotlivých testov objektívne, musíme * zabezpečiť, aby každý algoritmus mal možnosť triediť pestrú paletu rôzne * neusporiadaných zoznamov. Zároveň by zoznamy mali byť dostatočne * veľké.<br /> * * Dodržanie týchto pravidiel súťaženia zabezpečíme vygenerovaním veľkého * množstva predlôh dostatočne veľkých zoznamov, ktoré potom postupne * posunieme na zotriedenie jednotlivým algoritmom. Aby sme zvýšili * objektívnosť testov, necháme každý algoritmus zotriediť každý zoznam * niekoľko ráz. */ public class VeľkáSúťažTriedení extends GRobot { // Predloha bude celočíselný zoznam private class Predloha extends Zoznam<Integer> {} // Definujeme zoznam predlôh, ktoré budeme postupne v sériách testov // posúvať algoritmom na triedenie private Zoznam<Predloha> predlohy = new Zoznam<Predloha>(); // Tento súkromný atribút použijeme na určenie zoznamu, s ktorým budeme // pracovať počas jednej série testov private int čísloPredlohy = 0; // Toto bude pracovný zoznam, ktorého prvky budú triedené; // tento zoznam sa po každom teste vymaže a naplní znova… private Zoznam<Integer> zoznam = new Zoznam<Integer>(); // Táto konštanta určuje počet predlôh, s ktorými budeme pracovať public final static int početPredlôh = 80; // Táto konštanta určuje počet prvkov v každej predlohe public final static int početPrvkov = 100; // Táto konštanta určuje, koľko testov bude vykonaných s tou istou // predlohou public final static int početTestov = 50; // Tento súkromný atribút poslúži na zaznamenávanie systémového času, // ktorý použijeme na meranie private long stopky = 0; // V konštruktore vykonáme a zobrazíme výsledky všetkých testov private VeľkáSúťažTriedení() { // Najskôr vygenerujeme predlohy for (int i = 0; i < početPredlôh; ++i) { Predloha predloha = new Predloha(); for (int j = 0; j < početPrvkov; ++j) predloha.pridaj((int)Svet.náhodnéCeléČíslo(-50, 50)); predlohy.pridaj(predloha); } // Chvíľu počkáme; pre istotu; aby sa stabilizovali všetky objekty // (keby bolo náhodou treba)… Svet.čakaj(1); // Nasleduje spúšťanie jednotlivých sérií testov… // (Vo viacerých prípadoch testujeme viacero verzií rovnakého // algoritmu, aby sme ukázali, akým spôsobom sa dá zvyšovať // efektívnosť. Vysvetlenie rozdielov medzi nimi je v komentároch // metód jednotlivých algoritmov.) spustiČasomieru(); for (čísloPredlohy = 0; čísloPredlohy < predlohy.veľkosť(); ++čísloPredlohy) for (int i = 0; i < početTestov; ++i) bubbleSort1(); long bubbleSort1 = zastavČasomieru(); spustiČasomieru(); for (čísloPredlohy = 0; čísloPredlohy < predlohy.veľkosť(); ++čísloPredlohy) for (int i = 0; i < početTestov; ++i) bubbleSort2(); long bubbleSort2 = zastavČasomieru(); spustiČasomieru(); for (čísloPredlohy = 0; čísloPredlohy < predlohy.veľkosť(); ++čísloPredlohy) for (int i = 0; i < početTestov; ++i) bubbleSort3(); long bubbleSort3 = zastavČasomieru(); spustiČasomieru(); for (čísloPredlohy = 0; čísloPredlohy < predlohy.veľkosť(); ++čísloPredlohy) for (int i = 0; i < početTestov; ++i) insertSort1(); long insertSort1 = zastavČasomieru(); spustiČasomieru(); for (čísloPredlohy = 0; čísloPredlohy < predlohy.veľkosť(); ++čísloPredlohy) for (int i = 0; i < početTestov; ++i) insertSort2(); long insertSort2 = zastavČasomieru(); spustiČasomieru(); for (čísloPredlohy = 0; čísloPredlohy < predlohy.veľkosť(); ++čísloPredlohy) for (int i = 0; i < početTestov; ++i) insertSort3(); long insertSort3 = zastavČasomieru(); spustiČasomieru(); for (čísloPredlohy = 0; čísloPredlohy < predlohy.veľkosť(); ++čísloPredlohy) for (int i = 0; i < početTestov; ++i) selectSort1(); long selectSort1 = zastavČasomieru(); spustiČasomieru(); for (čísloPredlohy = 0; čísloPredlohy < predlohy.veľkosť(); ++čísloPredlohy) for (int i = 0; i < početTestov; ++i) selectSort2(); long selectSort2 = zastavČasomieru(); spustiČasomieru(); for (čísloPredlohy = 0; čísloPredlohy < predlohy.veľkosť(); ++čísloPredlohy) for (int i = 0; i < početTestov; ++i) quickSort(); long quickSort = zastavČasomieru(); // Nasleduje výpis výsledkov… Svet.vypíšRiadok("Výsledok algoritmu bubbleSort1", bubbleSort1, "ms."); Svet.vypíšRiadok("Výsledok algoritmu bubbleSort2", bubbleSort2, "ms."); Svet.vypíšRiadok("Výsledok algoritmu bubbleSort3", bubbleSort3, "ms."); Svet.vypíšRiadok("Výsledok algoritmu insertSort1", insertSort1, "ms."); Svet.vypíšRiadok("Výsledok algoritmu insertSort2", insertSort2, "ms."); Svet.vypíšRiadok("Výsledok algoritmu insertSort3", insertSort3, "ms."); Svet.vypíšRiadok("Výsledok algoritmu selectSort1", selectSort1, "ms."); Svet.vypíšRiadok("Výsledok algoritmu selectSort2", selectSort2, "ms."); Svet.vypíšRiadok("Výsledok algoritmu quickSort", quickSort, "ms."); } /** * Táto metóda „spustí“ časomieru. V skutočnosti si iba zapamätá * začiatočný systémový čas v milisekundách, ktorý potom použije na * vypočítanie trvania jedného merania. */ public void spustiČasomieru() { stopky = System.currentTimeMillis(); } /** * Táto metóda „zastaví“ časomieru. V skutočnosti iba odčíta od aktuálneho * systémového času v milisekundách čas, ktorý sme si zapamätali na * začiatku merania v metóde „spustiČasomieru“. */ public long zastavČasomieru() { return stopky = System.currentTimeMillis() - stopky; } /** * Táto metóda vyčistí pracovný zoznam a skopíruje do neho predlohu určenú * indexom „čísloPredlohy“. */ public void zoznamPodľaPredlohy() { zoznam.vymaž(); zoznam.pridaj(predlohy.daj(čísloPredlohy)); } /** * Toto je najmenej efektívna implementácia bublinkového triedenia. Na * nízku efektívnosť má vplyv určenie horných hraníc cyklov výpočtami, * ktoré spomaľujú vykonávanie algoritmu pri každej iterácii. Keď je * iterácií veľa, spomaľujúci efekt sa výrazne prejaví. */ public void bubbleSort1() { zoznamPodľaPredlohy(); for (int i = 0; i < zoznam.veľkosť() - 1; ++i) { for (int j = 0; j < zoznam.veľkosť() - i - 1; ++j) { if (zoznam.daj(j) > zoznam.daj(j + 1)) zoznam.vymeň(j, j + 1); } } } /** * V tejto verzii algoritmu sme sa zbavili neustále sa zbytočne * opakujúcich výpočtov hraníc tým, že sme obrátili smerovanie cyklu zhora * nadol. Výpočet hornej hranice je tak vykonaný len raz, na začiatku. Po * vykonaní testov uvidíme, že zvýšenie efektívnosti je viditeľné na čase * vykonávania, ktorý je zhruba 70%-ný oproti pôvodnej verzii. */ public void bubbleSort2() { zoznamPodľaPredlohy(); for (int i = zoznam.veľkosť() - 1; i > 0; --i) { for (int j = 0; j < i; ++j) { if (zoznam.daj(j) > zoznam.daj(j + 1)) zoznam.vymeň(j, j + 1); } } } /** * Do tretice sa pokúšame zvýšiť efektívnosť zabezpečením skorého * skončenia triedenia v prípade, že už nenastáva žiadna výmena prvkov. * Toto vylepšenie má zmysel len pre niektoré usporiadania zoznamov. * V prípadoch, kedy je neusporiadanosť zoznamu taká veľká, že je potrebné * vykonávať triedenie do posledného prvku, je toto vylepšenie * v skutočnosti na škodu, pretože výsledný algoritmus spomaľuje. Naopak, * keď je zoznam takmer zotriedený a stačí len niekoľko výmen, algoritmus * skončí veľmi skoro. Vtedy by týmto vylepšením získal. Problém je, že * nevieme dopredu určiť do akej miery bude zoznam neusporiadaný. My * robíme testy pre veľa rôzne neusporiadaných zoznamov, čím zabezpečujeme * objektívnosť merania. Po spustení testov zistíme, že zisk tejto verzie * algoritmu je malý. Keby sme nepoznali žiadny iný algoritmus, uspokojili * by sme sa aj s takýmto drobným prírastkom efektívnosti. Vzhľadom na to, * že realita je iná, je pre nás takýto prírastok zanedbateľný. */ public void bubbleSort3() { zoznamPodľaPredlohy(); for (int i = zoznam.veľkosť() - 1; i > 0; --i) { boolean zastav = true; for (int j = 0; j < i; ++j) { if (zoznam.daj(j) > zoznam.daj(j + 1)) { zoznam.vymeň(j, j + 1); zastav = false; } } if (zastav) break; } } /** * Rôzne verzie triedenia vkladaním sa vzájomne odlišujú len minimálne. * Algoritmus je implementačne relatívne jednoduchý, preto neposkytuje * veľa priestoru na optimalizáciu. Prvá verzia je „prvoplánová“ bez * pokusov o vylepšenia. (Vylepšenia sú opísané pri ďalších verziách * algoritmov.) */ public void insertSort1() { zoznamPodľaPredlohy(); for (int i = 1; i < zoznam.veľkosť(); ++i) { int a = zoznam.daj(i); int j = i; while ((j > 0) && (a < zoznam.daj(j - 1))) { zoznam.vymeň(j, j - 1); --j; } zoznam.prepíš(j, a); } } /** * V tejto verzii sme skúsili zvýšiť efektívnosť zbavením sa neustáleho * spúšťania metódy „veľkosť()“ v určení hornej hranice cyklu (to má za * následok volanie metódy pri každej iterácii). Namiesto toho, aby sme * hornú hranicu cyklu „for“ určili volaním metódy „zoznam.veľkosť()“, si * pred vykonávaním cyklu uložíme hodnotu veľkosti zoznamu do premennej * a tú použijeme na stanovenie podmienky hornej hranice cyklu. Po * spustení testov zistíme, že istý časový zisk tu je. Nie extrémne veľký, * ale predsa. Použitie premennej je rýchlejšie než volanie metódy. * (Poznámka: takúto optimalizáciu smieme vykonať len pri takých * algoritmoch, pri ktorých sme si istí, že veľkosť spracúvaného zoznamu * sa počas vykonávania algoritmu nezmení. Našťastie v tomto prípade máme * splnenie tejto podmienky zaručené.) */ public void insertSort2() { zoznamPodľaPredlohy(); int veľkosť = zoznam.veľkosť(); for (int i = 1; i < veľkosť; ++i) { int a = zoznam.daj(i); int j = i; while ((j > 0) && (a < zoznam.daj(j - 1))) { zoznam.vymeň(j, j - 1); --j; } zoznam.prepíš(j, a); } } /** * V tretej verzii triedenia vkladaním skúšame nahradiť výmenu prvkov * posunom. V tomto algoritme (ako jedinom triediacom algoritme z tých, * ktoré sme preberali) nie je potrebná výmena prvkov, pretože prvky sa * v skutočnosti len posúvajú. Výmena je v tomto prípade zbytočný luxus. * Ale je tu jeden problém. Triedime zoznam. Zoznam je objekt, ktorého * prvky čítame a zapisujeme volaním metód. Keby sme použili pole, ku * ktorého prvkom pristupujeme priamo, zisk náhrady výmeny za posun prvkov * by bol zreteľný. No po spustení testov zistíme, že v tomto prípade, keď * používame zoznam, sme algoritmu v skutočnosti poškodili. Je to preto, * že na prečítanie prvku zoznamu musíme volať metódu „daj“ a na zapísanie * prvku do zoznamu zase metódu „prepíš“. To sú dve volania metód namiesto * jedného („vymeň“). Preto sa v skutočnosti vykonávanie algoritmu * spomalí. Síce minimálne, ale predsa. (Nuž: „nie je všetko čierne alebo * biele.“) */ public void insertSort3() { zoznamPodľaPredlohy(); int veľkosť = zoznam.veľkosť(); for (int i = 1; i < veľkosť; ++i) { int a = zoznam.daj(i); int j = i; while ((j > 0) && (a < zoznam.daj(j - 1))) { zoznam.prepíš(j, zoznam.daj(j - 1)); --j; } zoznam.prepíš(j, a); } } /** * Prvá verzia algoritmu triedenia výberom nezahŕňa žiadne úsilie * o optimalizáciu, o ktorej sa dá uvažovať v tej časti algoritmu, * v ktorej sú vykonávané výmeny prvkov. */ public void selectSort1() { zoznamPodľaPredlohy(); int ľavý = 0; int pravý = zoznam.veľkosť() - 1; while (ľavý < pravý) { int min = ľavý; int max = ľavý; for (int i = ľavý + 1; i <= pravý; ++i) { if (zoznam.daj(min) > zoznam.daj(i)) min = i; if (zoznam.daj(max) < zoznam.daj(i)) max = i; } zoznam.vymeň(min, ľavý); if (max == ľavý) zoznam.vymeň(min, pravý); else zoznam.vymeň(max, pravý); ++ľavý; --pravý; } } /** * V tejto verzii algoritmu sa usilujeme obmedziť množstvo výmen. A to * tak, že pred každou výmenou overujeme, či má alebo nemá zmysel * (konkrétne, či nejde o pokus vymeniť prvok sám so sebou) a až po * overení zavoláme metódu „vymeň“. V skutočnosti je metóda „vymeň“ * vnútorne optimalizovaná tak, aby sa v prípade, že sa pokúšame vymeniť * prvok „sám so sebou“ výmena nevykonala. (My však predpokladáme, že to * nevieme a nemáme to možnosť nijakým spôsobom zistiť, keďže táto * skutočnosť nie je uvedená v dokumentácii.) Napriek tomu je táto verzia * algoritmu zanedbateľne rýchlejšia. Malá úspora času, ktorú môžeme * spozorovať je spôsobená len obmedzením počtu volaní metódy „vymeň“, * pretože príkaz volania metódy nie je až taký náročný na vykonanie ako * by bola séria príkazov vykonávajúca výmenu prvkov tým spôsobom, ktorý * je opísaný v zdrojovom kóde triedy Vymeň. Môžeme povedať, že tento * spôsob vylepšenia by mal skutočný zmysel predovšetkým v prípade, keby * sme nepoužili optimalizovanú verziu metódy „vymeň“, ale nejakú vlastnú… */ public void selectSort2() { zoznamPodľaPredlohy(); int ľavý = 0; int pravý = zoznam.veľkosť() - 1; while (ľavý < pravý) { int min = ľavý; int max = ľavý; for (int i = ľavý + 1; i <= pravý; ++i) { if (zoznam.daj(min) > zoznam.daj(i)) min = i; if (zoznam.daj(max) < zoznam.daj(i)) max = i; } if (min != ľavý) { zoznam.vymeň(min, ľavý); if (max != ľavý) zoznam.vymeň(max, pravý); else if (min != pravý)zoznam.vymeň(min, pravý); } else if (max != pravý) zoznam.vymeň(max, pravý); ++ľavý; --pravý; } } /** * Algoritmus rýchleho triedenia sme implementovali len raz, pretože sme * nenašli priestor na optimalizáciu. (Dve nasledujúce metódy s názvom * „quickSort“, sú súčasťou tej istej implementácie.) Táto (prvá) metóda * tvorí súkromné rekurzívne jadro algoritmu, druhá metóda tvorí obálku. */ private void quickSort(int lo, int hi) { int pivot = zoznam.daj((lo + hi) / 2); int i = lo, j = hi; while (i <= j) { while (zoznam.daj(i) < pivot) ++i; while (zoznam.daj(j) > pivot) --j; if (i <= j) zoznam.vymeň(i++, j--); } if (lo < j) quickSort(lo, j); if (i < hi) quickSort(i, hi); } /** * Toto je verejná obálka algoritmu, ktorú potrebujeme, pretože do * rekurzívneho jadra nemôžeme zaradiť žiadne príkazy pre potreby súťaže. * Narušili by jeho činnosť. (Poznámka: názov metódy sme mohli recyklovať * vďaka mechanizmu polymorfizmu v Jave, ktorý nazývame „preťažovanie“.) */ public void quickSort() { zoznamPodľaPredlohy(); quickSort(0, zoznam.veľkosť() - 1); } // Nakoniec je tu hlavná metóda, ktorú, dúfam, netreba predstavovať… public static void main(String[] args) { Svet.použiKonfiguráciu("velka-sutaz-triedeni.cfg"); new VeľkáSúťažTriedení(); } }