20. diel - Na čo sú algoritmy?

V minulej lekcii, Najčastejšie chyby Java začiatočníkov, robíš ich tiež?, sme si ukázali najčastejšie chyby začiatočníkov v Jave týkajúce sa napr. pomenovávania kolekcií, boolean výrazov a DRY.

Základné konštrukcie jazyka Java máme takmer za sebou. Skôr než 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ň nahliadnuť, 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 o zavolaní nejakej predpripravenej funkcie jazyka, ale čo 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ť

Keď narazíme na úlohu, ktorú vieme vyriešiť, ale nie sme si istí, či ju riešime efektívne, spýtame sa AI. Napríklad promptom: "Ako môžem najefektívnejšie v Jave zoradiť pole čísel?". AI nám pomôže navrhnúť rôzne prístupy a vysvetlí, že nie všetky riešenia sú rovnako efektívne. To je dôležité hlavne pri väčších dátach, kde už záleží nielen na tom, aby program fungoval, ale aj na tom, aby bol dostatočne rýchly.

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 by potom potrebovalo 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 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šenia 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 mohlo zdať, ž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. Ak bude vaš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ý. Používatelia aplikácií majú príšernú vlastnosť, ktorou je nedočkavosť. Keď napríklad stlačia tlačidlo, očakávajú, že sa niečo stane hneď... Nemažme si med okolo úst, my sme takí tiež. Nechceme čakať, kým náš skvelý program vyhodí výsledok. Nemusia to byť ani zložité výpočty. Ak programujeme hru, očakávame, že hneď po stlačení klávesu sa panáčik pohne. Očakávame, že po otvorení okna sa nám zobrazí zoznam použí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

Pokiaľ 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 veľkosti 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 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 prebiehať formou aukcií, zadáte čas a potom čakáte, či ľudia budú 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 a šé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 a v 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 stránka v niekoľkých jazykoch 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ž načrtli, je otázka správnych praktík v programovaní. Teda toho, čo by sme mali dodržiavať, aby vývoj softvéru iš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 orezať, alebo naopak. Tým sme sa dostali opäť k otázke času. Ak dáta najskôr orežeme, potom napríklad z desaťtisícov položiek triedime len 134. Rozdiel v rýchlosti 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 zoradiť. Skúsme použiť ten najzákladnejší a zrejme najmenej vhodný algoritmus, triedenie výberom.

Idea algoritmu (neefektívny selection sort)

Môžeme si povedať, že v nezoradenom 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)

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 zoradený 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 switch 1 and 3
2. (1,3,5,4)            the smallest is 3, 3 is on its place, we do not need to switch
3. (1,3,4,5)            the smallest is 4, we switch 4 and 5, we have the last item left, it must be the biggest so the algorithm stops, array is  sorted

Teraz si predvedieme jeho implementáciu:

public static int[] selectionSort(int[] numbers) {
   for (int i = 0; i < (numbers.length - 1); i++) {
      int minIndex = i;
      for (int j = i + 1; j < numbers.length ; j++) {
           if (numbers[j] < numbers[minIndex]) {
               minIndex = j;
           }
      }
      int temp = numbers[i];
      numbers[i] = numbers[minIndex];
      numbers[minIndex] = temp;
   }
   return numbers;
}

Keď už nejaký algoritmus máme, ale nerozumieme mu, necháme si ho podrobne vysvetliť od AI. Zadáme napríklad prompt: "Vysvetli mi po krokoch, ako funguje algoritmus Selection sort v Jave.".

Benchmark radiacich algoritmov

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

Konzolová aplikácia
| Algorithm/Items   | 1000  | 5000  | 10000 | 20000
|-----------------------|-------|-------|-------|-------
| Selection sort        | 6ms   | 30ms  | 51ms  | 197ms
| Bubblesort            | 10ms  | 60ms  | 151ms | 781ms
| Insertion sort        | 3ms   | 19ms  | 24ms  | 93ms
| Heapsort              | 1ms   | 1ms   | 2ms   | 4ms
| Merge sort            | 1ms   | 1ms   | 3ms   | 8ms
| 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 OOP kurze.

Na výstupe benchmarku vidíme, za ako dlho daný algoritmus zoradil pole o 1000, 5000, 10000 a 20000 prvkoch. Krásne tu vidíme, 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 a 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 Bubblesortom 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 vo svete algoritmov. Alebo čo robí programátor? Rieši problémy, ktoré by bežnému človeku ani nenapadli. Ale o tom to predsa je, však?

Zhrnutie lekcie

Algoritmus je ako návod alebo recept, podľa ktorého krok za krokom riešime nejaký problém. Rovnako ako pri varení nestačí vedieť, čo chceme uvariť, ale musíme poznať správny postup, ani v programovaní nestačí len vedieť, čo má program robiť. Záleží aj na tom, ako to urobíme. Niektoré postupy sú pomalé a zbytočne zložité, iné sú rýchle a premyslené. Práve tým sa algoritmy zaoberajú. Ukazujú nám, ako úlohy riešiť čo najlepšie, napríklad ako dáta triediť, vyhľadávať alebo spracovať tak, aby program bežal rýchlo a neplytval pamäťou.

V nasledujúcom cvičení, Riešené úlohy k 18.-20. lekcii Javy, 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š.