Mikuláš je tu! Získaj 90 % extra kreditov ZADARMO s promo kódom CERTIK90 pri nákupe od 1 199 kreditov. Len do nedele 7. 12. 2025! Zisti viac:
NOVINKA: Najžiadanejšie rekvalifikačné kurzy teraz s 50% zľavou + kurz AI ZADARMO. Nečakaj, táto ponuka dlho nevydrží! Zisti viac:

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

Predchádzajúci
Ďalší

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 si predstavíme svet algoritmov. Povieme si, čo to algoritmy vlastne sú a prečo by sme sa o ne mali zaujímať.

Čo sú to algoritmy?

Podľa tej najjednoduchšej definície 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 vtedy mali 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:

  • Nebudeme schopní určité úlohy vyriešiť.
  • Alebo ich naopak vyriešime nesprávne (je síce fajn niečo vymyslieť sám, ale riešenie je potom potrebné porovnať s reálnym svetom).

Nesprávne 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 výpočtu riešenia 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čebníc na konci minulého storočia, stretávame sa s tým všetci. Obzvlášť, ak budete písať aplikácie pre Android. Ak bude vaša aplikácia zaberať 1GB, nikto si ju nestiahne. Navyše tu funguje zaujímavý zákon, keď sa zväčší pamäť, zväčší sa aj veľkosť programov a s nedostatkom pamäte sa tak stretávame znova.

Čas

Ak je problém s pamäťou znepokojujúci, čas je ešte hrôzostrašnejší. 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žme si med okolo úst, aj my sme presne takí istí. Nechceme čakať, kým náš skvelý program vyhodí výsledok. Nemusia 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 používateľov zoradených 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

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 a s mnohými objektmi. To má niekoľko problémov, prvým je napríklad pamäťový nárok. Keby sme každú postavu a každý domček poctivo vytvorili, svet s veľkosťou 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

Predstavme si, ž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íme, že náš program má fungovať aj v angličtine. Dobre, dáme jednoduchý if-else pre jazyky a prepíšeme stránku do angličtiny. Lenže potom sa ozvú ľudia z Nemecka, že by bolo dobré tam dať aj nemčinu. Dobre, dáme tam aj nemeckú verziu. Potom si šéf vymyslí, že by sme mohli pridať aj bazár kožených búnd, čo je super nápad, ale kódovať to budeme my. Zrejme na to stránka nebola pripravená, takže robíme novú stránku s odkazom na pôvodnú, ktorá je zase trojjazyčná, tentoraz už zvolíme efektívny návrh, keby firma prenikla do Francúzska. Bazár bude formou aukcií, zadáme čas a potom čakáme, či ľudia môžu prihadzovať. Lenže sa ukázalo, že kolegovia z Ruska mohli prihadzovať aj po tom, čo náš čas ubehol, a kolegovia z Anglicka prišli o hodinu. Tak kód trochu poupravíme.

Rozrástli sme sa a máme toľko búnd, že sa zákazníci ťažko orientujú, tak sa náš šéf rozhodne, že bundy rozdelíme do kategórií, a zákazník bude môcť vyhľadávať podľa ceny a mena. Dobre, spravíme si kávu a ideme na to. Našli sme si návod, ako niekto naprogramoval vyhľadávanie podľa ceny aj podľa mena a máme to tam. Sotva kód dopíšeme, šéf príde s tým, že by bolo pekné, keby zákazník mohol pridať kritériá a že by mohol vyhľadávať napríklad len vo svojich troch obľúbených značkách a v nejakom cenovom rozmedzí. Objednáme si na budúci týždeň dovolenku a začneme písať. Nájdeme si riešenie pre viacnásobné kľúče pri vyhľadávaní a niekoľkofázovom triedení. Za týždeň to všetko máme a už sa tešíme, ako si oddýchneme, keď v tom nám volá zákaznícka linka, že náš program nefunguje. Kód, ktorý sme stiahli z netu, nefunguje kvôli príliš veľkým dátam. Naša niekoľkojazyčná stránka trpí tým, že tam niekedy skáče iný jazyk a my si musíme na dovolenku vziať našu prácu a vyriešiť všetko, čo za nás "pokazil" niekto iný.

Čo s tým?

Tu sme sa dotkli hneď dvoch tém. Prvá téma, ktorú sme už načrtli, je otázka správnych praktík v programovaní. Toho, čo by sme mali dodržiavať, aby vývoj softvéru išiel ako po masle. To druhé je však schopnosť algoritmicky myslieť. Ako konkrétne vyriešiť problém, napríklad triedenie. Či najskôr triediť, až potom osekať alebo naopak. A sme pri otázke času, ak najskôr osekáme, potom napríklad z desaťtisíc položiek triedime len 134. A tá rýchlosť je potom jasná. Ak navyše 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?

Existuje veľa problémov, ktoré ešte nikto neriešil, a mali by sme vedieť, ako postupovať pri ich riešení. Na to slúži naša sekcia pre výuku algoritmov.

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

Skúsme si teraz sami, ako by sme mohli čísla v poli roztriediť. Skúsme použiť ten najzákladnejší a zrejme najmenej vhodný algoritmus, a teda triedenie výberom.

Idea algoritmu (neefektívny selection sort)

Môžeme si povedať, že v neroztriedenom poli vždy vyberieme najmenší doposiaľ nevybraný prvok a ten vložíme do nového poľa. Potom budeme vyhľadávať väčší prvok:

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 s rovnakou veľkosťou.

Idea algoritmu (efektívny selection sort)

Majme pole s veľkosťou 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 zatriedený 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

Ak 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 s 1000, 5000, 10000 a 20000 prvkami. Krásne tu vidíme, 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 Bubblesortom 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 vo svete algoritmov. Alebo čo robí programátor? Rieši problémy, ktoré by normálnemu človeku ani nenapadli. Ale o tom to predsa je, však?

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é 66x (6.7 kB)
Aplikácia je vrátane zdrojových kódov

 

Predchádzajúci článok
Best practices pre vývoj softvéru - Práca s databázou
Všetky články v sekcii
Best practices pre návrh softwaru
Preskočiť článok
(neodporúčame)
Best practices pre vývoj softvéru - Vývoj webových aplikácií
Článok pre vás napísal David Hartinger
Avatar
Užívateľské hodnotenie:
211 hlasov
David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.
Unicorn university David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.
Aktivity