14. diel - Na čo sú algoritmy?

Základnú konštrukciu jazyka Kotlin máme takmer za sebou. Kým ich ale úplne opustíme, musíte vedieť, že o efektívnom využívaní týchto konštrukcií existuje celá ďalšia veda. Našťastie nám o nej stačí len vedieť a občas do nej nahliadnuť, keď chceme niečo špeciálne. Tou vedou je algoritmizácia a dnes si ju 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 o zavolaní nejakej predpripravenej funkcie jazyka, musíme krok za krokom vymyslieť a zapísať ako postupnosť príkazov. Spomeňte 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 asi neškrtli. Tento postup sme mali tentoraz priamo v zadaní a našou jedinou úlohou bolo previesť ho do kódu. V praxi vám ale klient samozrejme nepovie, čo budete v jeho aplikácii riešiť za problémy a už vôbec nie, ako ich 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:

• buď nebudeme schopní určité úlohy vyriešiť,
• alebo ich vyriešime zle (je síce fajn niečo vymyslieť sám, ale riešenie potom musíme aspoň porovnať s reálnym svetom).

Zlé riešenie sa potom prejaví najčastejšie tým, že naša aplikácia vyhľadávajúca cestu v grafe bude potrebovať päť minút na to, aby zistila, ako sa ide z Prahy do Brna. Náš algoritmus totiž nebude efektívny.

Pre množstvo problémov našťastie už existuje ideálny algoritmus, ktorý vymyslel niekto pred nami. Ľudia nad riešením často strávili časť života a dostali zaň vedeckú cenu. Pravdepodobnosť, že by sme vymysleli lepší 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 kuchárku s receptami. Stačí nám nazrieť 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 môže ísť 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 učených kníh na konci minulého storočia, stretávame sa s tým všetci. Zvlášť, ak budete písať aplikácie pre Android. Ak vaša aplikácia bude zaberať 1 GB, nikto si ju nestiahne. Navyše tu funguje zaujímavý zákon, keď sa zväčší pamäť, zväčší sa aj veľkosť programov as 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ú príšernú vlastnosť, nedočkavosť. Keď napríklad stlačia tlačidlo, očakávajú, že sa niečo stane hneď... Nemažme si med okolo pusy, aj my sme takí používatelia. Nechceme čakať, kým náš skvelý program vyhodí výsledok. Nemusí to byť ani zložité výpočty. Pokiaľ programujeme hru, očakávame, že hneď po stlačení klávesy sa panáčik pohne. Očakávame, že po otvorení okna sa nám 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 dotýkajú týchto dvoch základných kameňov úrazu.

Interakcia so svetom

Možno ste zaregistrovali hru Kingdom Come Deliverance. Je to hra, ktorá sa môže pochváliť svetom, kde môžete interagovať s každou postavou as mnohými objektmi. To má niekoľko problémov, prvým je napríklad pamäťový nárok. Keby sme každú postavu a každý domček poctivo vytvorili, svet o veľkosť 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

Tu si predstavme, ž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íte, že váš program má fungovať aj v angličtine. Dobre, dáte jednoduchý if-else pre jazyky a prepíšete stránku do angličtiny. Lenže potom sa ozvú ľudia z Nemecka, že by bolo dobré tam dať aj nemčinu. Dobre, dáte tam aj nemeckú verziu. Potom si tam šéf vymyslí, že by ste mohli pridať aj bazár kožených búnd, čo je super nápad, ale budete to kódovať vy. Zrejme na to stránka nebola pripravená, takže robíte novú stránku s odkazom na pôvodnú, ktorá je zase trojjazyčná, tentoraz už zvolíte efektívny návrh, keby firma prenikla do Francúzska. Bazár bude formou aukcií, zadáte čas a potom čakáte, či ľudia môžu prihadzovať. Lenže sa ukázalo, že kolegovia z Ruska mohli prihadzovať aj po tom, čo váš čas ubehol a kolegovia z Anglicka prišli o hodinu. Tak to ľahko poupravíte.

Rozrástli ste sa a máte toľko búnd, že sa zákazníci ťažko orientujú, tak sa váš šéf rozhodne, že bundy rozdelíte do kategórií, a zákazník bude môcť vyhľadávať podľa ceny a mena. Dobre, nachystáte si kávu a idete na to. Našli ste si návod, ako niekto naprogramoval vyhľadávanie podľa ceny aj podľa mena a máte to tam. Sotva to dopíšete, šéf príde s tým, že by bolo pekné, keby zákazník mohol pridať kritériá a že by mohol hľadať napríklad len zo svojich troch obľúbených značiek av nejakom cenovom rozmedzí. Objednáte si na budúci týždeň dovolenku a začnete písať. Nájdete si riešenie pre viacnásobné kľúče pri vyhľadávaní a niekoľkofázovom triedení. Za týždeň to všetko máte a už sa tešíte, ako si oddýchnete, keď v tom vám volá zákaznícka linka, že váš program nefunguje. Kód, ktorý ste stiahli z netu, nefunguje pre veľké dáta. Vaša niekoľko-jazyková stránka trpí tým, že tam niekedy skáče iný jazyk a vy máte možnosť si na dovolenku vziať vašu prácu a vyriešiť všetko, čo za vás "pokazil" niekto iný.

Čo s tým?

Tu sme sa dotkli hneď dvoch tém. Prvá téma, ktorú sme už zahryzli, je otázka správnych praktík v programovaní. Toho, čo by sme mali dodržiavať, aby vývoj softvéru šiel ako po drôtikoch. To druhé je však schopnosť algoritmicky myslieť. Ako konkrétne vyriešiť problém, napríklad triedenie. Či najskôr triediť, potom až osekať alebo naopak. A sme pri otázke času, ak najskôr osekáme, potom napríklad z desaťtisícov položiek triedime len 134. A tá rýchlosť je potom jasná. Navyše, pokiaľ len tak preberáme kód niekoho iného, musíme veriť tomu, že vie, čo robí. Síce si môžeme kód vyskúšať, ale čo ak jeho algoritmus funguje iba pre malé dáta?

Je veľa problémov, ktoré nikto neriešil a mali by sme vedieť, ako postupovať pri riešení problémov. 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 čísla v poli zotriediť. Skúsme použiť ten najzákladnejší a najskôr najmenej vhodný spôsob, 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äčšie:

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)

Pole budeme triediť na mieste, tak aké je aj znenie tohto algoritmu.

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)            pôvodné pole
1. (1,3,5,4)            najmenší je 1, teda vymeníme 1 s 3
2. (1,3,5,4)            najmenšia je 3, 3 je na vhodnom mieste, nemeníme nič
3. (1,3,4,5)            najmenší je 4, vymeníme 4 a 5, zostal nám posledný prvok, ktorý musí byť najväčší, preto algoritmus končí, máme zotriedené

Teraz si predvedieme jeho implementáciu:

    fun SelectionSort(cisla: IntArray) {
        var pomocna: Int
        var minimum: Int

        for (i in 0 until cisla.size - 1) {
            minimum = cisla.size - 1

            // hledání minima
            for (j in i until cisla.size - 1) {
                if (cisla[minimum] > cisla[j]) {
                   minimum = j
                }
            }

            // prohození prvků
            pomocna = cisla[minimum]
            cisla[minimum] = cisla[i]
            cisla[i] = pomocna
        }
    }
}

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 vyzerá na mojom počítači takto:

Konzolová aplikácia
| Algoritmus/Prvků      | 1000  | 5000  | 10000 | 20000
|-----------------------|-------|-------|-------|-------
| Selection sort        | 5ms   | 33ms  | 76ms  | 249ms
| Bubblesort            | 9ms   | 57ms  | 152ms | 956ms
| Insertion sort        | 4ms   | 16ms  | 16ms  | 65ms
| Heapsort              | 1ms   | 1ms   | 3ms   | 5ms
| Merge sort            | 1ms   | 1ms   | 3ms   | 9ms
| 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, aký 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, aký 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 rýchlo Bubblesort 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ž mi nezostáva, než vám popriať veľa zdaru vo svete algoritmov. Alebo čo robí programátor? Rieši problémy, ktoré by normálneho človeka ani nenapadli. Ale o tom to predsa je, že?

V budúcej lekcii, Verzovací nástroj Git a IntelliJ IDEA , sa naučíme založiť vzdialený GitHub repozitár a verzovať svoje projekty pomocou základných Git operácií, ktoré nám IntelliJ IDEA ponúka.

 

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š.