19. diel - Na čo sú algoritmy? Nové

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. 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, 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ť

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í najčastejšie 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 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 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. Obzvlášť, ak budete písať aplikácie pre Android. Ak bude vaša aplikácia zaberať 1GB, nikto si ju nestiahne. Navyše tu funguje zaujímavý zákon, 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, kde môžete interagovať s každou postavou a s 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 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í. Toho, čo by sme mali dodržiavať, aby vývoj softvéru išiel ako po masle. Tá druhá je schopnosť algoritmicky myslieť. Ako konkrétne vyriešiť problém, napríklad triedenie. Či najskôr triediť až potom 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 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)

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

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 zatriedený 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[] array) {
   for (int i = 0; i < (array.length - 1); i++) {
    int indexMin = i;
    for (int j = i + 1; j < array.length ; j++) {
        if (array[j] < array[indexMin]) {
            indexMin = j;
        }
    }
    int temp = array[i];
    array[i] = array[indexMin];
    array[indexMin] = temp;
   }
   return array;
}

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
| 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ž mi nezostáva nič iné, než ti popriať veľa zdaru vo svete algoritmov. Alebo čo robí programátor? Rieši problémy, ktoré by normálnemu človeku nenapadli. Ale o tom to predsa je, však?

V nasledujúcom cvičení, Riešené úlohy k 17.-19. 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š.