Lekce 13 - K čemu jsou algoritmy ?

V minulé lekci, Nejčastější chyby Kotlin začátečníků, děláš je také?, jsme si ukázali nejčastější chyby začátečníků v Kotlin, např. ohledně pojmenování kolekcí, Boolean výrazů a DRY.

Základní konstrukce jazyka Kotlin máme téměř za sebou. Než je ale zcela opustíme, musíte vědět, že o efektivním využívání těchto konstrukcí existuje celá další věda. Naštěstí nám o ní stačí jen vědět a občas do ní nahlédnout, když chceme něco speciálního. Tou vědou je algoritmizace a dnes si ji představíme.

Co jsou to algoritmy?

V té nejjednodušší definici je algoritmus postup pro řešení konkrétního problému. V podstatě vše, co není jen o zavolání nějaké předpřipravené funkce jazyka, musíme krok za krokem vymyslet a zapsat jako posloupnost příkazů. Vzpomeňte si např. na náš program, který počítal kořeny kvadratické rovnice. Bez znalosti přesného postupu, jak se kvadratická rovnice řeší, bychom si asi neškrtli. Tento postup jsme měli tentokrát přímo v zadání a naší jedinou úlohou bylo převést jej do kódu. V praxi vám ale klient samozřejmě neřekne, co budete v jeho aplikaci řešit za problémy a už vůbec ne, jak je implementovat

Problémy s neznalostí algoritmů

Algoritmy používáme v reálných komerčních aplikacích zejména pro řazení a vyhledávání. Problémy s neznalostí algoritmů jsou hned dva:

• buď nebudeme schopní určité úlohy vyřešit,
• nebo je vyřešíme špatně (je sice fajn něco vymyslet sám, ale řešení pak musíme alespoň porovnat s reálným světem).

Špatné řešení se pak projeví nejčastěji tím, že naše aplikace vyhledávající cestu v grafu bude potřebovat pět minut na to, aby zjistila, jak se jede z Prahy do Brna. Náš algoritmus totiž nebude efektivní.

Pro spoustu problémů naštěstí již existuje ideální algoritmus, který vymyslel někdo před námi. Lidé nad řešením často strávili část života a dostali za něj vědeckou cenu. Pravděpodobnost, že bychom vymysleli lepší, nebo že lepší algoritmus pro daný problém vůbec existuje, je tedy velmi nízká

Kurzy algoritmů na ITnetwork

Algoritmy tedy budeme brát jako kuchařku s recepty. Stačí nám nakouknout do místní sekce Algoritmy na konkrétní místo v případě, kdy potřebujeme konkrétní algoritmus. Např. algoritmus řešení kvadratické rovnice nalezneme v kurzu Matematické algoritmy. Algoritmy se nejčastěji týkají řazení a vyhledávání prvků, ale samozřejmě se může jednat i např. o neurální algoritmus k rozpoznání objektů v obrázku. Takovouto věc si ovšem již nebudeme psát na koleni, ale stáhneme si pro ni knihovnu.

Co algoritmy řeší?

Nejdříve se podívejme na dva hlavní problémy programů.

Paměť

Ač by se zdálo, že slovní spojení "nedostatek paměti" je fráze z učených knih na konci minulého století, potýkáme se s tím všichni. Zvlášť, pokud budete psát aplikace pro Android. Pokud vaše aplikace bude zabírat 1 GB, nikdo si ji nestáhne. Navíc zde funguje zajímavý zákon, když se zvětší paměť, zvětší se i velikost programů a s nedostatkem paměti se musíme potýkat nanovo.

Čas

Jestli je problém s pamětí znepokojující, čas je naprosto hrůzostrašný. Uživatelé aplikací mají příšernou vlastnost, nedočkavost. Když například stisknou tlačítko, očekávají, že se něco stane hned... Nemažme si med kolem pusy, i my jsme takoví uživatelé. Nechceme čekat, až náš skvělý program vyhodí výsledek. Nemusí to být ani složité výpočty. Pokud programujeme hru, očekáváme, že hned po stisknutí klávesy se panáček pohne. Očekáváme, že po otevření okna se nám zobrazí seznam uživatelů seřazený podle jména.

Konkrétní příklady pro algoritmizaci

Ukážeme si, že všechny ostatní problémy se přímo či nepřímo dotýkají těchto dvou základních kamenů úrazu.

Interakce se světem

Možná jste zaregistrovali hru Kingdom Come Deliverance. Je to hra, která se může pochlubit světem, kde můžete interagovat s každou postavou a s mnoha objekty. To má několik problémů, prvním je například paměťový nárok. Kdybychom každou postavu a každý domek poctivě vytvořili, svět o velikost města s 300 lidmi by zabíral obrovské množství paměti, kterou by nakonec hráč asociál vůbec nevyužil...

Příběh ze života

Zde si představme, že máme E-shop pro prodej jednoho kusu oblečení, konkrétně kožených bund. Náš e-shop má různé animace pro prodej bund. Jenže pak zjistíte, že váš program má fungovat i v angličtině. Dobře, dáte jednoduchý if-else pro jazyky a přepíšete stránku do angličtiny. Jenže pak se ozvou lidi z Německa, že by bylo dobré tam dát i němčinu. Dobře, dáte tam i německou verzi. Pak si tam šéf vymyslí, že byste mohli přidat i bazar kožených bund, což je super nápad, ale budete to kódit vy. Nejspíš na to stránka nebyla připravena, takže děláte novou stránku s odkazem na původní, která je zase trojjazyčná, tentokrát už zvolíte efektivní návrh, kdyby firma pronikla do Francie. Bazar bude formou aukcí, zadáte čas a pak čekáte, zda lidé mohou přihazovat. Jenže se ukázalo, že kolegové z Ruska mohli přihazovat i po tom, co váš čas uběhl a kolegové z Anglie přišli o hodinu. Tak to lehce poupravíte.

Rozrostli jste se a máte tolik bund, že se zákazníci těžko orientují, tak se váš šéf rozhodne, že bundy rozdělíte do kategorií, a zákazník bude moci vyhledávat podle ceny a jména. Dobře, nachystáte si kafe a jdete na to. Našli jste si návod, jak někdo naprogramoval vyhledávání podle ceny i podle jména a máte to tam. Sotva to dopíšete, šéf přijde s tím, že by bylo hezké, kdyby zákazník mohl přidat kritéria a že by mohl hledat třeba jen ze svých tří oblíbených značek a v nějakém cenovém rozmezí. Objednáte si na příští týden dovolenou a začnete psát. Najdete si řešení pro vícenásobné klíče při vyhledávání a několikafázové třídění. Za týden to vše máte a už se těšíte, jak si odpočinete, když v tom vám volá zákaznická linka, že váš program nefunguje. Kód, který jste stáhli z netu, nefunguje pro velká data. Vaše několika-jazyková stránka trpí tím, že tam někdy skáče jiný jazyk a vy máte možnost si na dovolenou vzít vaši práci a vyřešit vše, co za vás "pokazil" někdo jiný.

Co s tím?

Zde jsme se dotkli hned dvou témat. První téma, které jsme již nakousli, je otázka správných praktik v programování. Toho, co bychom měli dodržovat, aby vývoj softwaru šel jako po drátkách. To druhé je však schopnost algoritmicky myslet. Jak konkrétně vyřešit problém, například třídění. Jestli nejdřív třídit, pak až osekat či naopak. A jsme u otázky času, pokud nejdřív osekáme, pak třeba z desetitisíců položek třídíme jen 134. A ta rychlost je pak jasná. Navíc, pokud jen tak přejímáme kód někoho jiného, musíme věřit tomu, že ví, co dělá. Sice si můžeme kód vyzkoušet, ale co když jeho algoritmus funguje jen pro malá data?

Je spousta problémů, které nikdo neřešil a měli bychom vědět, jak postupovat při řešení problémů. K tomu slouží naše sekce pro výuku algoritmů.

Ukázka na závěr - třídění pomocí selection sort

Pojďme si teď sami zkusit, jak bychom mohli čísla v poli setřídit. Zkusme použít ten nejzákladnější a nejspíš nejméně vhodný způsob, třídění výběrem.

Idea algoritmu (neefektivní selection sort)

Můžeme si říct, že v nesetříděném poli vždy vybereme nejmenší, dosud nevybraný, prvek a ten vložíme do nového pole. Potom budeme vyhledávat větší:

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

Proč je tento kód neefektivní? Protože si musíme vytvářet pole bokem, tzn. pro pole velikosti milion vytvoříme druhé pole o stejné velikosti.

Idea algoritmu (efektivní selection sort)

Pole budeme třídit na místě, tak jaké je i znění tohoto algoritmu.

Mějme pole o velikosti n. Pojedeme od prvního prvku pole a najdeme nejmenší prvek. Ten vyměníme s prvním prvkem. Víme, že menší prvek se v poli nevyskytuje, takže máme jeden setříděný prvek. Posuneme se a hledáme nejmenší prvek ve zbytku pole. Ten zase vyměníme s druhým atd... Ukázka algoritmu:

0. (3,1,5,4)            původní pole
1. (1,3,5,4)            nejmenší je 1, tedy vyměníme 1 s 3
2. (1,3,5,4)            nejmenší je 3, 3 je na vhodném místě, neměníme nic
3. (1,3,4,5)            nejmenší je 4, vyměníme 4 a 5, zbyl nám poslední prvek, který
                        musí být největší, proto algoritmus končí, máme setříděno

Nyní si předvedeme jeho implementaci:

    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 řadících algoritmů

Pro názornost jsme pro vás připravili aplikaci, která porovná 6 nejznámějších řadících algoritmů, můžete si ji stáhnout v příloze. Její výsledek vypadá na mém počítači takto:

Konzolová aplikace
| 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

Pokud se budete dívat na zdrojový kód, není v něm nic, co byste ještě neznali, kromě rozdělení kódu do více funkcí a souborů. Této problematice se budeme dále věnovat v OOP kurzu.

Na výstupu benchmarku vidíme, za jak dlouho daný algoritmus seřadil pole o 1000, 5000, 10000 a 20000 prvcích. Vidíme zde krásně, jak asymptotická složitost opravdu funguje v praxi. Zatímco u 1000 prvků je úplně jedno, jaký algoritmus použijeme, u 10000 prvků je Bubblesort již nepoužitelný. A když počet prvků zdvojnásobíme, není jeho čas také dvojnásobný, ale více než trojnásobný. Pro více prvků se benchmark již ani nezkoušel, protože by na něm Bubblesort trval desítky vteřin. Určitě má tedy smysl přemýšlet nad tím, jaký algoritmus pro jaký účel používáme. Od špatné volby nás nezachrání ani rychlý počítač. Zde stroj s frekvencí několika GHz nedokáže rychle Bubblesortem seřadit 10 tisíc čísel, i když Quick sortem to trvá 1 milisekundu.

Na detailní popis i implementaci řadících algoritmů se můžete podívat v kurzu Řadící algoritmy. Benchmark je přiložený pod lekcí ke stažení.

Nyní už mi nezbývá, než vám popřát hodně zdaru ve světě algoritmů. Aneb co dělá programátor? Řeší problémy, které by normálního člověka ani nenapadly. Ale o tom to přeci je, že?

V následujícím cvičení, Řešené úlohy k 11.-13. lekci Kotlin, si procvičíme nabyté zkušenosti z předchozích lekcí.

 

Měl jsi s čímkoli problém? Stáhni si vzorovou aplikaci níže a porovnej ji se svým projektem, chybu tak snadno najdeš.