15. diel - K čomu sú algoritmy?

V predchádzajúcom cvičení, Riešené úlohy k 11.-12. lekciu C # .NET, sme si precvičili získané skúsenosti z predchádzajúcich lekcií.

Po začiatkoch, kedy si sa zoznámil či zoznámila s tým, čo je to premenná, ako funguje cyklus for a kedy použiť switch, sa ponúka otázka, čo ďalej? Pravdepodobne by mali prísť na rad objekty, či nejaká tvorba HTML s CSS, Bootstrap či sa vrhnúť na Android. Aj keby ste sa venovali však čisto jazyku C, stále je základná syntax len akési podhubie, z ktorého sa skladajú dobré programy. V tomto článku si povieme niečo o tom, prečo by nás algoritmy mali zaujímať a prečo sa im nejde vyhnúť (pre tvoje zdravie a tvojho budúceho šéfa).

Čo je to algoritmus?

V tej najjednoduchšej definícii je algoritmus postup pre riešenie konkrétneho problému. Čo musí algoritmus spĺňať, aký má byť atď., Na to sú na webe iné články. My sa uspokojíme s riešením problému. Programovanie, viac než takmer akékoľvek iné povolanie, je o riešení problému. Aj keď máte v hlave predstavu treba nové hry či fungujúci aplikácie pre trh, vzápätí narazíte na niekoľko problémov, s ktorými sa musíte nejako popasovať a zvoliť si konkrétny metódu riešenia. 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. Zvlášť, ak budete písať aplikácie pre Android. Ak vaša aplikácia bude zaberať 1GB, nikto si ju nestiahne. Navyše tu funguje zaujímavý zákon, keď sa zväčší pamäť, zväčší sa aj veľkosť programov as nedostatkom pamäte sa musíme zápasiť nanovo.

Čas

Ak je problém s pamäťou znepokojujúce, čas je úplne hrôzostrašný. Používatelia aplikácií majú príšernú vlastnosť, nedočkavosť. Keď napríklad stlačia tlačidlo, očakávajú, že sa niečo stane hneď ... nemaže si med okolo úst, aj my sme takí užívatelia. Nechceme čakať, až náš skvelý program vyhodí výsledok. Nemusí to byť ani zložité výpočty. Ak programujeme hru, očakávame, že hneď po stlačení klávesy sa panáčik pohne. Očakávame, že po otvorení okna sa nám zobrazí zoznam užívateľov zoradený podľa mena.

Konkrétne príklady pre algoritmizácia

Ukážeme si, že všetky ostatné problémy sa priamo alebo nepriamo dotýkajú týchto dvoch základných kameňov úrazu.

Interakcie so svetom

Ak ste zaregistrovali hru Kingdom Come Deliverance, je to hra, ktorá sa môže pochváliť svetom, kde môžete interagovať s každou postavou as mnohými objekty. To má niekoľko problémov, prvá 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 pre predaj jedného kusu oblečenia, konkrétne kožených búnd. Náš e-shop má rôzne animácie pre 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ú ľudí z Nemecka, že by bolo dobré tam dať aj nemčinu. Dobre, dáte tam i 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 kodi vy. Najskôr 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 formou aukcií, zadáte čas a potom čakáte, či ľudia môžu 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 mená. 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ázovou triedenia. 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 niekoľkých-jazyková stránka trpí tým, že tam niekedy skáče iný jazyk a vy máte možnosť si na dovolenku zobrať 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ým sa venujú tieto články XXXXX, je otázka správnych techník v programovaní. Toho, čo by sme mali dodržiavať, aby vývoj softvéru šiel ako po masle. To druhé je však schopnosť algoritmicky myslieť. Ako konkrétne vyriešiť problém, napríklad triedenie. Ak najskôr triediť, potom až osekať či naopak. A sme pri otázke času, ak najprv osekáme, potom napríklad z desaťtisícov položiek triedime len 134. A tá rýchlosť je potom jasná. Navyše, ak len tak prijímame kód niekoho iného, musíme mu teda veriť tomu, že vie, čo to robí. Síce si môžeme kód vyskúšať, ale čo keď jeho algoritmus funguje len 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. K tomu slúžia naše sekcie pre výučbu algoritmov.

Ukážka na záver - triedenie pomocou selection sort

Skúsme si teraz sami skúsiť, ako by sme mohli čísla v poli zotrieďiť. Skúsme použiť ten najzákladnejší a najskôr najmenej vhodný, triedenie výberom.

Idea algoritmu (neefektívne selection sort)

Môžeme si povedať, že v Hlavička poli vždy vyberieme najmenší doteraz nevybratý 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ívne? Pretože si musíme vytvárať pole bokom, tzn. pre pole veľkosti milión vytvoríme druhej pole o rovnakej veľkosti.

Idea algoritmu (efektívna selection sort)

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

Majme poľa 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šie 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)            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

Teraz si predvedieme jeho implementáciu:

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;
    }
}

Teraz už mi nezostáva, než tí popriať veľa zdaru sa svete algoritmov. Alebo čo robí programátor? Rieši problémy, ktoré by normálneho človeka nenapadli. Ale o tom to predsa je, že?

V nasledujúcom kvíze, Záverečný test - Základná konštrukcia C # .NET, si vyskúšame nadobudnuté skúsenosti z kurzu.