Lekce 15 - K čemu jsou algoritmy?

V předešlém cvičení, Řešené úlohy k 13.-14. lekci C# .NET, jsme si procvičili nabyté zkušenosti z předchozích lekcí.

Po začátcích, kdy ses seznámil či seznámila s tím, co je to proměnná, jak funguje cyklus for a kdy použít switch, se nabízí otázka, co dál? Nejspíše by měly přijít na řadu objekty, či nějaká tvorba HTML s CSS, Bootstrap či se vrhnout na Android. I kdybyste se věnovali však čistě jazyku C, pořád je základní syntaxe jen jakési podhoubí, ze kterého se skládají dobré programy. V tomto článku si řekneme něco o tom, proč by nás algoritmy měly zajímat a proč se jim nejde vyhnout (pro tvoje zdraví a tvého budoucího šéfa).

Co je to algoritmus?

V té nejjednodušší definici je algoritmus postup pro řešení konkrétního problému. Co musí algoritmus splňovat, jaký má být atd., na to jsou na webu jiné články. My se spokojíme s řešením problému. Programování, víc než téměř jakékoliv jiné povolání, je o řešení problému. I když máte v hlavě představu třeba nové hry či fungující aplikace pro trh, záhy narazíte na několik problémů, se kterými se musíte nějak popasovat a zvolit si konkrétní metodu řešení. 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 1GB, 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 zmáčknou 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

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

Pokud 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í 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, a šé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ým se věnují tyto články XXXXX, je otázka správných technik 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 mu teda věřit tomu, že ví, co to 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

Zkusme si teď sami zkusit, jak bychom mohli čísla v poli setřídit. Zkusme použít ten nejzákladnější a nejspíš nejméně vhodný, 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:

public static void 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;
    }
}

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