16. diel - Na čo sú algoritmy?

V predchádzajúcej lekcii, Matematické funkcie v C# a knižnica Math, sme si predstavili matematické funkcie zabudované v .NET Frameworku.

Základné konštrukcie jazyka C# máme takmer za sebou. Kým ich ale úplne dokončí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 na 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, aké problémy budeme riešiť v jeho aplikácii, 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í vyriešiť určité úlohy.
• 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, ako 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ársku knihu s receptami. Ak potrebujeme konkrétny algoritmus, stačí nám nahliadnuť do miestnej sekcie Algoritmy. 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ť aj napr. 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 kníh koncom minulého storočia, stretávame sa s tým všetci. Zvlášť ak budeme písať aplikácie pre Android. Ak 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 tak stretneme znova.

Č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í. Nechceme čakať, kým náš skvelý program vyhodí výsledok. Nemusí ísť ani o zložité výpočty. Ak programujeme hru, očakávame, že sa panáčik pohne ihneď po stlačení klávesu. Očakávame, že sa nám po otvorení okna zobrazí zoznam užívateľov zoradený podľa mena.

Konkrétne príklady algoritmizácie

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 typu 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 budú prihadzovať. Ukázalo sa však, ž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 vedia ťažko zorientovať, a 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. Kód sme sotva dopísali a šé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í. Na ďalší týždeň si objednáme 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ď nám v tom volá zákaznícka linka, že náš program nefunguje. Kód, ktorý sme stiahli z internetu, nefunguje kvôli veľkým údajom. Naša niekoľkojazyčná stránka má problém s 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 po masle. 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. Ak dáta najskôr osekáme, potom napríklad z desaťtisíc položiek triedime len 134. Rozdiel v rýchlosti je potom jasný. Aľ navyše len tak preberáme kód niekoho iného, musíme dotyčnému veriť, že vie, čo ten kód 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 na výučbu algoritmov.

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

Poďme si teraz sami skúsiť, ako by sme mohli roztriediť čí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 netriedenom 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)

Máme 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

Ako ukážku 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

Ak 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 kurze OOP.

Na výstupe benchmarku vidíme, za ako dlho daný algoritmus zoradil pole s 1000, 5000, 10000 a 20000 prvkami. Tu krásne vidieť, 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 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 používame na aký účel. 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 nám už nezostáva nič iné, ako vám popriať veľa zdaru vo svete algoritmov. A teda čo robí programátor? Rieši 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 15.-16. 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š.