13. diel - Najčastejšie chyby programátorov - Na čo sú algoritmy?

V minulej lekcii, Best practices pre vývoj softvéru - Práca s databázou, sme sa venovali práci s dátami v databáze. Naučili sme sa formátovať výstupné dáta a využívať unikátny kľúč.

V dnešnom tutoriále kurzu Best practices pre návrh softvéru sa uvedieme do sveta algoritmov. Povieme si, čo to algoritmy vlastne sú a prečo by sme sa o ne mali zaujímať.

Č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, 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 chce riešenie minimálne potom 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 Brna. 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šenie 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. 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 stretávať nanovo.

Čas

Ak je problém s pamäťou znepokojujúci, čas je úplne hrôzostrašný. Uží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žme si med okolo pusy, aj my sme takí používatelia. Nechceme čakať, kým náš skvelý program vyhodí výsledok. Nemusí to byť ani zložité výpočty. Pokiaľ 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á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 as mnohými objektmi. 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 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 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 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 av 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 niekoľko-jazyková stránka 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ž zahryzli, je otázka správnych praktík v programovaní. Toho, čo by sme mali dodržiavať, aby vývoj softvéru šiel ako po drôtikoch. To druhé je však schopnosť algoritmicky myslieť. Ako konkrétne vyriešiť problém, napríklad triedenie. Či najskôr triediť, potom až 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

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

Idea algoritmu (neefektívny selection sort)

Môžeme si povedať, že v nesetriedenom 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.

Majme 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 zotriedený 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)            1 is the minimum, we swap 1 with 3
2. (1,3,5,4)            3 is the minimum, 3 is at the right place, we don't swap
3. (1,3,4,5)            4 is the minimum, we swap 4 with 5, there's only one element
                        left which has to be the maximum, the algorithms is finished, the array is sorted

Teraz si predvedieme jeho implementáciu:

public static int[] selectionSort(int[] numbers) {
   for (int i = 0; i < (numbers.length - 1); i++) {
      int indexMin = i;
      for (int j = i + 1; j < numbers.length; j++) {
           if (numbers[j] < numbers[indexMin]) {
               indexMin = j;
           }
      }
      int next = numbers[i];
      numbers[i] = numbers[indexMin];
      numbers[indexMin] = next;
   }
   return numbers;
}

public static int[] SelectionSort(int[] numbers)
{
   for (int i = 0; i < (numbers.Length - 1); i++)
   {
      int indexMin = i;
      for (int j = i + 1; j < numbers.Length; j++)
      {
         if (numbers[j] < numbers[indexMin])
         {
            indexMin = j;
         }
      }
      int next = numbers[i];
      numbers[i] = numbers[indexMin];
      numbers[indexMin] = next;
   }
   return numbers;
}

int * selectionSort(int * numbers, int length) {
  for (int i = 0; i < (length - 1); i++) {
    int indexMin = i;
    for (int j = i + 1; j < length; j++) {
      if (numbers[j] < numbers[indexMin]) {
        indexMin = j;
      }
    }
    int next = numbers[i];
    numbers[i] = numbers[indexMin];
    numbers[indexMin] = next;
  }
  return numbers;
}

def selection_sort(numbers):
    for i in range(len(numbers) - 1):
        index_min = i
        for j in range(i + 1, len(numbers)):
            if numbers[j] < numbers[index_min]:
                index_min = j
        next = numbers[i]
        numbers[i] = numbers[index_min]
        numbers[index_min] = next
    return numbers

func selectionSort(numbers: [Int]) -> [Int] {
  var sortedArr = numbers
  for i in 0..<(sortedArr.count - 1) {
    var indexMin = i
    for j in (i + 1)..<sortedArr.count {
      if sortedArr[j] < sortedArr[indexMin] {
        indexMin = j
      }
    }
    let next = sortedArr[i]
    sortedArr[i] = sortedArr[indexMin]
    sortedArr[indexMin] = next
  }
  return sortedArr
}

function selectionSort(array $numbers): array {
    $length = count($numbers);
    for ($i = 0; $i < ($length - 1); $i++) {
        $indexMin = $i;
        for ($j = $i + 1; $j < $length; $j++) {
            if ($numbers[$j] < $numbers[$indexMin]) {
                $indexMin = $j;
            }
        }
        $next = $numbers[$i];
        $numbers[$i] = $numbers[$indexMin];
        $numbers[$indexMin] = $next;
    }
    return $numbers;
}

function selectionSort(numbers) {
   for (let i = 0; i < (numbers.length - 1); i++) {
      let indexMin = i;
      for (let j = i + 1; j < numbers.length ; j++) {
           if (numbers[j] < numbers[indexMin]) {
               indexMin = j;
           }
      }
      let next = numbers[i];
      numbers[i] = numbers[indexMin];
      numbers[indexMin] = next;
   }
   return numbers;
}

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/Elements    | 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

Pokiaľ 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. Vidíme tu krásne, 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 Bubblesort 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, než ti 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 budúcej lekcii, Best practices pre vývoj softvéru - Vývoj webových aplikácií, sa naučíme využívať hotové softvérové riešenia a užitočné nástroje.

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š.

Stiahnuť

Stiahnutím nasledujúceho súboru súhlasíš s licenčnými podmienkami

Stiahnuté 0x (6.21 kB)
Aplikácia je vrátane zdrojových kódov

Článok pre vás napísal David Hartinger

Užívateľské hodnotenie:

Ešte nikto nehodnotil, buď prvý!

David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.

David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.

Aktivity