Lekce 15 - K čemu jsou algoritmy?

V minulé lekci, Matematické funkce v C# a knihovna Math, jsme si představili matematické funkce vestavěné v .NET Frameworku.

Základní konstrukce jazyka C# máme téměř za sebou. Než je ale zcela opustíme, je potřeba vědět, že efektivním využíváním těchto konstrukcí se zabývá celý další vědní obor. Naštěstí nám stačí jen vědět, že existuje, a občas do něj nahlédnout, když potřebujeme něco speciálního. Tím vědním oborem je algoritmizace, kterou si dnes 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 otázkou zavolání nějaké předpřipravené funkce jazyka, musíme krok za krokem vymyslet a zapsat jako posloupnost příkazů. Vzpomeňme 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 ani neškrtli. Tento postup jsme měli protentokrát přímo v zadání a naší jedinou úlohou bylo převést jej do kódu. V praxi nám ale klient samozřejmě neřekne, co budeme v jeho aplikaci řešit za problémy, a už vůbec ne to, jak je budeme 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:

• Nebudeme schopní určité úlohy vyřešit.
• Nebo je naopak vyřešíme špatně (je sice dobré něco vymyslet sám, ale je poté potřeba řešení minimálně porovnat s reálným světem).

Špatné řešení se pak projeví například tím, že naše aplikace vyhledávající cestu v grafu bude potřebovat 5 minut na to, aby zjistila, kudy 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é řešením těchto algoritmů často strávili část života a dostali za něj vědeckou cenu. Pravděpodobnost, že bychom vymysleli lepší řešení 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 takovou kuchařku s recepty. Stačí nám nahlédnout 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 např. i 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ášť budeme-li psát aplikace pro Android. Pokud bude naše aplikace zabírat 1 GB, nikdo si ji nestáhne. Navíc zde platí zajímavý zákon, který určuje, že když se zvětší paměť, zvětší se i velikost programů a s nedostatkem paměti se musíme potýkat nanovo.

Čas

Jestliže je problém s pamětí znepokojující, čas je naprosto hrůzostrašný. Uživatelé aplikací mají velmi nepříjemnou vlastnost – nedočkavost. Když uživatelé 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í jít ani o složité výpočty. Pokud programujeme hru, očekáváme, že se panáček pohne ihned po stisknutí klávesy. Očekáváme, že se nám po otevření okna 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 týkají těchto dvou základních kamenů úrazu.

Interakce se světem

Pokud jste zaregistrovali hru Kingdom Come: Deliverance, je to hra, která se může pochlubit světem, v němž můžete interagovat s každou postavou a s mnoha objekty. To představuje několik problémů. Prvním z nich je například paměťový nárok. Kdybychom každou postavu a každý domek poctivě vytvořili, svět o velikosti 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

Představme si, ž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íme, že náš program má fungovat i v angličtině. Dobře, aplikujeme jednoduchý if-else pro jazyky a přepíšeme stránku do angličtiny. Jenomže pak se ozvou lidé z Německa, že by bylo dobré přidat i němčinu. Dobře, dáme tam i německou verzi. Pak si šéf vymyslí, že bychom mohli přidat i bazar kožených bund, což je super nápad, ale kódovat to budeme my. Nejspíš na to stránka nebyla připravena, takže vytvoříme novou stránku s odkazem na původní, která je zase trojjazyčná. Tentokrát už zvolíme efektivní návrh, kdyby firma pronikla i do Francie. Bazar bude mít formu aukce, kdy zadáme čas a pak čekáme, zda lidé mohou přihazovat. Jenže se ukáže, že kolegové z Ruska mohli přihazovat i poté, co náš čas uběhl, zatímco kolegové z Anglie přišli o hodinu. Tak kód lehce poupravíme.

Rozrostli jsme se a máme tolik bund, že se zákazníci těžko orientují, proto se náš šéf rozhodne, že bundy rozdělíme do kategorií a zákazník bude moci vyhledávat podle ceny a značky. Dobře, nachystáme si kávu a jdeme na to. Našli jsme si návod, jak někdo naprogramoval vyhledávání podle ceny i značky, a máme to tam. Sotva kód dopíšeme, šéf přijde s tím, že by bylo hezké, kdyby zákazník mohl přidat kritéria a vyhledávat třeba jen ze tří oblíbených značek a v nějakém cenovém rozmezí. Objednáme si na příští týden dovolenou a začneme psát. Najdeme 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áme a už se těšíme, jak si odpočineme, když vtom nám volá zákaznická linka, že náš program nefunguje. Kód, který jsme stáhli z internetu, nefunguje pro velká data. Naše několikajazyčná stránka trpí tím, že na ní někdy vyskočí jiný jazyk, a my máme možnost si na dovolenou vzít naši práci a vyřešit vše, co za nás "pokazil" někdo jiný.

Co s tím?

Zde jsme se dotkli hned dvou témat. První téma, které jsme již nastínili, je otázka správných praktik v programování. Toho, co bychom měli dodržovat, aby vývoj softwaru šel jako na drátku. Druhým tématem je však schopnost myslet algoritmicky. Jak konkrétně problém, například třídění, vyřešit. Zda data nejdříve třídit a až poté osekat, či naopak. Tím jsme se dostali opět k otázce času. Pokud data nejdříve osekáme, pak třeba z desetitisíců položek třídíme jen 134. Rozdíl v rychlosti je pak jasný. Pokud navíc jen tak přejímáme kód někoho jiného, musíme dotyčnému věřit, že ví, co to dělá. Kód si sice můžeme vyzkoušet, ale co když jeho algoritmus funguje jen pro malá data?

Existuje spousta problémů, které nikdo neřešil, a proto bychom měli vědět, jak při řešení problémů postupovat. 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 setřídit čísla v poli. Zkusme použít ten nejzákladnější a nejspíš nejméně vhodný algoritmus, tedy 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ší prvek:

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)

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, vyměníme tedy 1 s 3
2. (1,3,5,4)            nejmenší je 3, 3 je na vhodném místě, neměníme tedy 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:

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

Benchmark řadicích algoritmů

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

Konzolová aplikace
| Algoritmus/Prvků      | 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

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, který 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, který 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 Bubblesortem rychle seřadit 10 tisíc čísel, i když Quick sortem to trvá 1 milisekundu.

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

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

V následujícím cvičení, Řešené úlohy k 14.-15. lekci C# .NET, 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š.