15. diel - Na čo sú algoritmy?

V minulej lekcii, Matematické funkcie v C# a knižnica Math, sme si predstavili matematické funkcie vstavané v .NET Frameworku.

Základné konštrukcie jazyka C# máme takmer za sebou. Kým ich ale úplne opustíme, je potrebné vedieť, že efektívnym využívaním týchto konštrukcií sa zaoberá celý ďalší vedný odbor. Našťastie nám stačí len vedieť, že existuje, a občas do neho nazrieť, keď potrebujeme niečo špeciálne. Tým vedným odborom je algoritmizácia, ktorú si dnes predstavíme.

Čo sú to algoritmy?

V tej najjednoduchšej definícii je algoritmus postup pre riešenie konkrétneho problému. V podstate všetko, čo nie je len otázkou zavolania nejakej predpripravenej funkcie jazyka, musíme krok za krokom vymyslieť a zapísať ako postupnosť príkazov. Spomeňme si napr. na náš program, ktorý počítal korene kvadratickej rovnice. Bez znalosti presného postupu, ako sa kvadratická rovnica rieši, by sme si ani neškrtli. Tento postup sme mali tentokrát priamo v zadaní a našou jedinou úlohou bolo previesť ho do kódu. V praxi nám ale klient samozrejme nepovie, čo budeme v jeho aplikácii riešiť za problémy, a už vôbec nie to, ako ich budeme implementovať

Problémy s neznalosťou algoritmov

Algoritmy používame v reálnych komerčných aplikáciách najmä na radenie a vyhľadávanie. Problémy s neznalosťou algoritmov sú hneď dva:

• Nebudeme schopní určité úlohy vyriešiť.
• Alebo ich naopak vyriešime zle (je síce dobré niečo vymyslieť sám, ale potom je potrebné riešenie minimálne porovnať s reálnym svetom).

Zlé riešenie sa potom prejaví napríklad tým, že naša aplikácia vyhľadávajúca cestu v grafe bude potrebovať 5 minút na to, aby zistila, kadiaľ sa ide z Prahy do Bratislavy. Náš algoritmus totiž nebude efektívny.

Pre množstvo problémov našťastie už existuje ideálny algoritmus, ktorý vymyslel niekto pred nami. Ľudia riešením týchto algoritmov často strávili časť života a dostali zaň vedeckú cenu. Pravdepodobnosť, že by sme vymysleli lepšie riešenie alebo že lepší algoritmus pre daný problém vôbec existuje, je teda veľmi nízka

Kurzy algoritmov na ITnetwork

Algoritmy teda budeme brať ako takú kuchárku s receptami. Stačí nám nahliadnuť do miestnej sekcie Algoritmy na konkrétne miesto v prípade, keď potrebujeme konkrétny algoritmus. Napr. algoritmus riešenie kvadratickej rovnice nájdeme v kurze Matematické algoritmy. Algoritmy sa najčastejšie týkajú radenia a vyhľadávania prvkov, ale samozrejme sa môže jednať napr. aj o neurálny algoritmus na rozpoznanie objektov v obrázku. Takúto vec si však už nebudeme písať na kolene, ale stiahneme si pre ňu knižnicu.

Čo algoritmy riešia?

Najskôr sa pozrime na dva hlavné problémy programov.

Pamäť

Hoci by sa zdalo, že slovné spojenie "nedostatok pamäte" je fráza z učených kníh na konci minulého storočia, stretávame sa s tým všetci. Zvlášť ak budeme písať aplikácie pre Android. Pokiaľ bude naša aplikácia zaberať 1 GB, nikto si ju nestiahne. Navyše tu platí zaujímavý zákon, ktorý určuje, že keď sa zväčší pamäť, zväčší sa aj veľkosť programov a s nedostatkom pamäte sa musíme stretávať nanovo.

Čas

Ak je problém s pamäťou znepokojujúci, čas je úplne hrôzostrašný. Užívatelia aplikácií majú veľmi nepríjemnú vlastnosť - nedočkavosť. Keď používatelia napríklad stlačia tlačidlo, očakávajú, že sa niečo stane hneď… Nemažme si med okolo úst, aj my sme takí používatelia. Nechceme čakať, kým náš skvelý program vyhodí výsledok. Nemusí ísť ani o zložité výpočty. Pokiaľ programujeme hru, očakávame, že sa panáčik pohne ihneď po stlačení klávesy. Očakávame, že sa nám po otvorení okna zobrazí zoznam užívateľov zoradený podľa mena.

Konkrétne príklady pre algoritmizáciu

Ukážeme si, že všetky ostatné problémy sa priamo alebo nepriamo týkajú týchto dvoch základných kameňov úrazu.

Interakcia so svetom

Ak ste zaregistrovali hru Kingdom Come: Deliverance, je to hra, ktorá sa môže pochváliť svetom, v ktorom môžete interagovať s každou postavou a s mnohými objektmi. To predstavuje niekoľko problémov. Prvým z nich je napríklad pamäťový nárok. Keby sme každú postavu a každý domček poctivo vytvorili, svet s veľkosťou mesta s 300 ľuďmi by zaberal obrovské množstvo pamäte, ktorú by nakoniec hráč asociál vôbec nevyužil...

Príbeh zo života

Predstavme si, že máme e-shop na predaj jedného kusu oblečenia, konkrétne kožených búnd. Náš e-shop má rôzne animácie na predaj búnd. Lenže potom zistíme, že náš program má fungovať aj v angličtine. Dobre, aplikujeme jednoduchý if-else pre jazyky a prepíšeme stránku do angličtiny. Lenže potom sa ozvú ľudia z Nemecka, že by bolo dobré pridať aj nemčinu. Dobre, dáme tam aj nemeckú verziu. Potom si šéf vymyslí, že by sme mohli pridať aj bazár kožených búnd, čo je super nápad, ale kódovať to budeme my. Zrejme na to stránka nebola pripravená, takže vytvoríme novú stránku s odkazom na pôvodnú, ktorá je zase trojjazyčná. Tentokrát už zvolíme efektívny návrh, keby firma prenikla aj do Francúzska. Bazár bude mať formu aukcie, kedy zadáme čas a potom čakáme, či ľudia môžu prihadzovať. Lenže sa ukáže, že kolegovia z Ruska mohli prihadzovať aj potom, čo náš čas ubehol, zatiaľ čo kolegovia z Anglicka prišli o hodinu. Tak kód ľahko poupravíme.

Rozrástli sme sa a máme toľko búnd, že sa zákazníci ťažko orientujú, preto sa náš šéf rozhodne, že bundy rozdelíme do kategórií a zákazník bude môcť vyhľadávať podľa ceny a značky. Dobre, nachystáme si kávu a ideme na to. Našli sme si návod, ako niekto naprogramoval vyhľadávanie podľa ceny aj značky, a máme to tam. Sotva kód dopíšeme, šéf príde s tým, že by bolo pekné, keby zákazník mohol pridať kritériá a vyhľadávať napríklad len z troch obľúbených značiek a v nejakom cenovom rozmedzí. Objednáme si na budúci týždeň dovolenku a začneme písať. Nájdeme si riešenie pre viacnásobné kľúče pri vyhľadávaní a niekoľkofázovom triedení. Za týždeň to všetko máme a už sa tešíme, ako si odpočinieme, keď v tom nám volá zákaznícka linka, že náš program nefunguje. Kód, ktorý sme stiahli z internetu, nefunguje pre veľké údaje. Naša niekoľkojazyčná stránka trpí tým, že na nej niekedy vyskočí iný jazyk, a my máme možnosť si na dovolenku vziať našu prácu a vyriešiť všetko, čo za nás "pokazil" niekto iný.

Čo s tým?

Tu sme sa dotkli hneď dvoch tém. Prvá téma, ktorú sme už načrtli, je otázka správnych praktík v programovaní. Toho, čo by sme mali dodržiavať, aby vývoj softvéru šiel ako na drôtiku. Druhou témou je však schopnosť myslieť algoritmicky. Ako konkrétne problém, napríklad triedenie, vyriešiť. Či dáta najskôr triediť a až potom osekať, či naopak. Tým sme sa dostali opäť k otázke času. Pokiaľ dáta najskôr osekáme, potom napríklad z desaťtisícov položiek triedime len 134. Rozdiel v rýchlosti je potom jasný. Pokiaľ navyše len tak preberáme kód niekoho iného, musíme dotyčnému veriť, že vie, čo to robí. Kód si síce môžeme vyskúšať, ale čo ak jeho algoritmus funguje iba pre malé dáta?

Existuje množstvo problémov, ktoré nikto neriešil, a preto by sme mali vedieť, ako pri riešení problémov postupovať. Na to slúži naša sekcia pre výučbu algoritmov.

Ukážka na záver – triedenie pomocou selection sort

Poďme si teraz sami skúsiť, ako by sme mohli zotriediť čísla v poli. Skúsme použiť ten najzákladnejší a najskôr najmenej vhodný algoritmus, teda triedenie výberom.

Idea algoritmu (neefektívny selection sort)

Môžeme si povedať, že v nesetriedenom poli vždy vyberieme najmenší doposiaľ nevybraný prvok a ten vložíme do nového poľa. Potom budeme vyhľadávať väčší prvok:

0. (3,1,5,4)
1. (1)
2. (1,3)
3. (1,3,4)
4. (1,3,4,5)

Prečo je tento kód neefektívny? Pretože si musíme vytvárať pole bokom, tzn. pre pole veľkosti milión vytvoríme druhé pole o rovnakej veľkosti.

Idea algoritmu (efektívny selection sort)

Majme pole o veľkosti n. Pôjdeme od prvého prvku poľa a nájdeme najmenší prvok. Ten vymeníme s prvým prvkom. Vieme, že menší prvok sa v poli nevyskytuje, takže máme jeden zotriedený prvok. Posunieme sa a hľadáme najmenší prvok vo zvyšku poľa. Ten zase vymeníme s druhým atď. Ukážka algoritmu:

0. (3,1,5,4)        original array
1. (1,3,5,4)        the smallest is 1, so we swap 1 with 3
2. (1,3,5,4)        the smallest is 3, 3 is in the appropriate place, we don't change anything
3. (1,3,4,5)        the smallest is 4, we swap 4 and 5, we have the last element left, which
                    must be the largest, so the algorithm ends, we have it sorted

Teraz si predvedieme jeho implementáciu:

public static void SelectionSort(int[] numbers)
{
    for (int i = 0; i < numbers.Length - 1; i++)
    {
        int minimumIndex = i;
        // finding the minimum
        for (int j = i + 1; j < numbers.Length; j++)
        {
            if (numbers[j] < numbers[minimumIndex])
                minimumIndex = j;
        }
        // swapping elements
        int temp = numbers[i];
        numbers[i] = numbers[minimumIndex];
        numbers[minimumIndex] = temp;
    }
}

Benchmark radiacich algoritmov

Pre názornosť sme pre vás pripravili aplikáciu, ktorá porovná 6 najznámejších radiacich algoritmov, môžete si ju stiahnuť v prílohe. Jej výsledok na našom počítači vyzerá takto:

Konzolová aplikácia
| Algorithm/Elements    | 1000  | 5000  | 10000 | 20000
|-----------------------|-------|-------|-------|-------
| Selection sort        | 1ms   | 44ms  | 165ms | 614ms
| Bubblesort            | 3ms   | 95ms  | 474ms | 1694ms
| Insertion sort        | 1ms   | 22ms  | 93ms  | 378ms
| Heapsort              | 0ms   | 1ms   | 2ms   | 5ms
| Merge sort            | 0ms   | 1ms   | 3ms   | 5ms
| Quick sort            | 0ms   | 0ms   | 1ms   | 4ms

Pokiaľ sa budete pozerať na zdrojový kód, nie je v ňom nič, čo by ste ešte nepoznali, okrem rozdelenia kódu do viacerých funkcií a súborov. Tejto problematike sa budeme ďalej venovať v OOP kurze.

Na výstupe benchmarku vidíme, za ako dlho daný algoritmus zoradil pole o 1000, 5000, 10000 a 20000 prvkoch. Vidíme tu krásne, ako asymptotická zložitosť skutočne funguje v praxi. Zatiaľ čo pri 1000 prvkoch je úplne jedno, ktorý algoritmus použijeme, pri 10000 prvkoch je Bubblesort už nepoužiteľný, a keď počet prvkov zdvojnásobíme, nie je jeho čas tiež dvojnásobný, ale viac ako trojnásobný. Pre viac prvkov sa benchmark už ani neskúšal, pretože by na ňom Bubblesort trval desiatky sekúnd. Určite má teda zmysel premýšľať nad tým, ktorý algoritmus na aký účel používame. Od zlej voľby nás nezachráni ani rýchly počítač. Tu stroj s frekvenciou niekoľkých GHz nedokáže Bubblesortom rýchlo zoradiť 10 tisíc čísel, aj keď Quick sortom to trvá 1 milisekundu.

Na detailný popis aj implementáciu radiacich algoritmov sa môžete pozrieť v kurze Radiace algoritmy. Benchmark je priložený pod lekciou na stiahnutie.

Teraz už nám nezostáva nič iné, než vám popriať veľa zdaru sa svete algoritmov. Alebo čo robí programátor? Riešia problémy, ktoré by bežného človeka ani nenapadli. Ale o tom to predsa je, že?

V nasledujúcom cvičení, Riešené úlohy k 14.-15. lekcii C# .NET, si precvičíme nadobudnuté skúsenosti z predchádzajúcich lekcií.

 

Mal si s čímkoľvek problém? Stiahni si vzorovú aplikáciu nižšie a porovnaj ju so svojím projektom, chybu tak ľahko nájdeš.