Algoritmy
Tuto sekci bych chtěl později rozšířit o nějaké menu, tedy rozdělit algoritmy do kategorií.
Zatím je však budu přidávat pouze jako články. Zde uvedené algoritmy nemají úplně vždy jasné
praktické využití, ale pokusím se u každého nějaké najít. Tuto sekci jsem se rozhodl věnovat
oboru informačních technologií, kde se ve velké míře dbá na time a space complexity. Většina zde
uvedených algoritmů je přejata z knihy Průvodce
labyrintem algoritmů, kterou musím všem počítačovým nadšencům doporučit.
Jazyk, který používám v ukázkách zdrojových kódů, je jakousi směsicí C, JavaScriptu a C#. Má představovat
programátorům bližší pseudokód. Do budoucna k němu plánuji napsat dokumentaci.
Hledání prvku v nesetříděném poli
S tímto problémem už se nejspíš setkal každý programátor a jsem si jistý, že našel i správné řešení:
uint my_array[] = {4, 8, 1, 9, 6, 7, 3};
const uint my_item = 7;
find(my_array, my_item);
...
public static bool find(uint array[], uint item) {
for (int i = 0; i < array.length; i++) {
if (array[i] == item) {
return true;
}
}
return false;
}
Je dost pravděpodobné, že žádný lepší algoritmus na hledání konkrétního prvku v nesetříděném poli ani neexistuje. Přesto je tu možnost, jak tento problém řešit alespoň o malinko rychleji.
Pokud se na kód pro nalezení prvku podíváme očima počítače, zjistíme, že provádíme dvakrát operaci porovnávání - první je součástí cyklu a druhou zjišťujeme, jestli jsme narazili na onen hledaný prvek. Na dnešních procesorech jsou instrukce jako \(CMP\) a \(TEST\) opravdu zanedbatelně pomalé. Za problém bych označil spíše skokové instrukce (\(JZ\), \(JNB\), ...), kvůli kterým se musí vyprázdit fronta předem načtených instrukcí.
Toto nám zde pomůže vyřešit tzv. zarážka. Hledání prvku se záražkou se od původního algoritmu moc neliší, ale místo abychom kontrolovali, jestli má proměnná \(i\) pro indexování pole menší hodnotu než je velikost pole, umístíme na jeho konec (musíme jej zvětšit) námi hledáný prvek. Kód bude tedy vypadat takto:
uint my_array[] = {4, 8, 1, 9, 6, 7, 3, 7};
const uint my_item = 7;
find(my_array, my_item);
...
public static bool find(uint array[], uint item) {
uint i = 0;
while (array[i++] != item);
if (i < array.length - 1) {
return true;
}
return false;
}
Hmm... To nevypadá, že bychom se úplně zbavili té druhé podmínky, že? No... hned vám to objasním! Musíme si uvědomit, že druhé porovnání je jednoduše nezbytné. Díky němu zjistíme, jestli jsme našli námi hledáný prvek nebo zarážku. Duležité je, že je tato podmínka vně cyklu! Na prvek / zarážku tedy narazíme o něco rychleji.
Doufám, že jsem tento zlepšovák popsal dostatečně srozumitelně. Zde hraje opravdu důležitou roli nízkoúrovňový pohled na věc. Pokud bychom totiž hleděli pouze na pseudokódy, nikdy bychom nenašli ten hlavní rozdíl - rozdíl na úrovni strojového kódu. (Později sem nahraji i Assemblerovou variantu tohoto algoritmu.)
Hledání úseku s největším součtem
Na tomto jednoduchém problému je možné demonstrovat, jak může dobrá úvaha až neuvěřitelně snížit čas potřebný k vykonání požadované úlohy. Nechť \(\mathbb{Z}\) je množinou celých čísel. Nyní utvoříme množinu \(A\) a symbolem \(x\) označíme její libovolný prvek. Pak řekneme, že \(A \subset \mathbb{Z}\) (uvažujeme pouze konečné množiny, proto symbol \(\subset\) a ne \(\subseteq\)), tedy \(\forall x \in \mathbb{Z}\).
Nyní tyto matematické symboly přetransformujeme do řeči programátorů: Máme pole s prvky typu integer. To zní jednodušeji, že? :-) V tomto poli budeme chtít najít úsek, jehož součet je největší možný - žádný jiný úsek nemá větší součet. Jak tento problém řešit? První se nám nabízí řešení metodou brute force - hrubou silou. Inu... možnost to je, ale vezměte si tu složitost: \(O(n^2)\), ještě v horším případě klidně i \(O(n^3)\). Už pro 100prvkové pole by se tento algoritmus opakoval 10000krát, resp. 1000000krát, to je příšerné! Exituje mnohem lepší řešení se složitostí \(O(n)\). Tento algoritmus je úspornější i po stránce kódu:
int array[] = {2, -3, 4, -1, 8, -3, 2, 9};
int local_max = 0;
int global_max = 0;
for (uint i = 0; i < array.length; i++) {
local_max += array[i];
if (local_max < 0) {
local_max = 0;
} else if (local > global_max) {
global_max = local_max;
}
}
Nyní si výše uvedený kód trochu rozebereme. Metodou brute force bychom měli v lepším případě dva cykly - vnější by určoval začátek úseku a vnořený by byl použit ke sčítání. Takto bychom postupně prošli všechny úseky a podmínkou bychom zjišťovali, který má největší součet. Když se nad tím zamyslíme, dojde nám, že spoustu času trávíme sčítáním. Vlastně nastanou i případy, kdy provádíme součet \(x_1 + x_2 + ... + x_n\) a někdy později \(x_2 + x_3 + ... + x_n\), což jsou součty lišící se pouze o jeden prvek. Přesně tohle je kámen úrazu metody brute force. Náš algoritmus s časovou složitostí \(O(n)\) tento problém eliminuje.
Zkusme si vzít pole o dvou prvcích: \(\{1, 4\}\). Zde je asi hned jasné, že úsekem s největším součtem je \(1 + 4\), tedy \(5\). Nyní mějme pole \(\{-2, 4\}\). V tomto případě bude nejlepší možností pouze \(4\), protože \(-2\) by celkový součet snížila. Přejděme k poli o třech prvcích: \(\{1, 4, 5\}\). Největší možný součet je \(10\). V poli \(\{1, -1, 5\}\) to bude \(5\), ale nyní si musíme uvědomit, že tento úsek může být mít pozici \(0\) až \(2\) nebo \(2\) až \(2\). \(1+(-1)\) je \(0\), takže je nám to jedno. Co mít místo \(-1\) číslo \(-2\): \(\{1, -2, 5\}\). Součet \(1+(-2)\) je \(-1\), což se nám nevyplatí, takže výsledek je \(5\). A zde se nám vynořuje myšlenka našeho algoritmu! Vždy, když narazíme na součet menší než \(0\), jednoduše vynulujeme čítač. Díky tomu budeme vědět, že tento součet by naše celkové skóre zhoršil. Pak už pouze zbývá podmínka, kterou budeme ověřovat, který úsek má větší součet. To tedy znamená pouze jeden cyklu, a zjednodušeně i time complexity \(O(n)\).
Už brzy tu bude možnost přidávat komentáře!