Optimalizace algoritmůOptimalizace algoritmů

Jiří „Fila“ FilipovičJiří „Fila“ Filipovič

PUPworXPUPworX

Předmět přednáškyPředmět přednášky

časová složitost algoritmučasová složitost algoritmu• významvýznam• často používané metody snižování složitostičasto používané metody snižování složitosti

lineární optimalizacelineární optimalizace kdy a kde optimalizovatkdy a kde optimalizovat

základní metody, pro pokročilé asi nic základní metody, pro pokročilé asi nic nového…nového…

Složitost algoritmuSložitost algoritmu

teorie složitosti je velmi komplexní, bude teorie složitosti je velmi komplexní, bude demonstrován jen velmi zúžený pohleddemonstrován jen velmi zúžený pohled

složitostní třídasložitostní třída popisuje chování algoritmu popisuje chování algoritmu vzhledem k délce vstupuvzhledem k délce vstupu• časováčasová vs. vs. prostorováprostorová složitost složitost• nejlepšínejlepší, , nejhoršínejhorší a a průměrnýprůměrný případ případ• zajímá nás zajímá nás asymptotické chováníasymptotické chování funkce funkce

složitostisložitosti

Vlastnosti složitostních třídVlastnosti složitostních tříd

abstrahujeme od konkrétního času běhu abstrahujeme od konkrétního času běhu algoritmualgoritmu• nezávislost na CPU, kompilátoru…nezávislost na CPU, kompilátoru…

OO(g) – třída funkcí rostoucích nejvýše tak (g) – třída funkcí rostoucích nejvýše tak rychle jako grychle jako g

Zajímá nás asymptotické chováníZajímá nás asymptotické chování• T(logT(log22 n) = n) = OO(log n)(log n)

• T(3n + 1) = T(3n + 1) = OO(n)(n)• T(nT(n22 - n + 3) = - n + 3) = OO(n(n22))

Tabulka časůTabulka časů

1010 2020 5050 10001000

log nlog n 0,000001s0,000001s 0,000001s0,000001s 0,000002s0,000002s 0,000003s0,000003s

nn 0,00001s0,00001s 0,00002s0,00002s 0,00005s0,00005s 0,001s0,001s

nn22 0,0001s0,0001s 0,0004s0,0004s 0,0025s0,0025s 1s1s

22nn 0,001024s0,001024s 1,048576s1,048576s 35,7 let35,7 let 3,4∙103,4∙10287 let287 let

nnnn 2,8 hodiny2,8 hodiny 3∙103∙101212 let let 2,8∙102,8∙107171 letlet

3,2∙103,2∙1029862986 letlet

Určení složitosti - příkladUrčení složitosti - příklad

vyhledání prvku v polivyhledání prvku v poli

int hledejSekvencne(int pole[n], int prvek){ for (int i = 0; i < n; i++) if (pole[i] == prvek) return i; return -1;}

Určení složitosti - příkladUrčení složitosti - příklad

vyhledání prvku v polivyhledání prvku v poli

int hledejSekvencne(int pole[n], int prvek){ for (int i = 0; i < n; i++) if (pole[i] == prvek) return i; return -1;}

jaká je časová složitost?jaká je časová složitost?

Určení složitosti - příkladUrčení složitosti - příklad

vyhledání prvku v polivyhledání prvku v poli

int hledejSekvencne(int pole[n], int prvek){ for (int i = 0; i < n; i++) if (pole[i] == prvek) return i; return -1;}

jaká je časová složitost?jaká je časová složitost?• nejlepší případ nejlepší případ OO(1)(1)

Určení složitosti - příkladUrčení složitosti - příklad

vyhledání prvku v polivyhledání prvku v poli

int hledejSekvencne(int pole[n], int prvek){ for (int i = 0; i < n; i++) if (pole[i] == prvek) return i; return -1;}

jaká je časová složitost?jaká je časová složitost?• nejlepší případ nejlepší případ OO(1)(1)• nejhorší případ nejhorší případ OO(n)(n)

Určení složitosti - příkladUrčení složitosti - příklad

vyhledání prvku v polivyhledání prvku v poli

int hledejSekvencne(int pole[n], int prvek){ for (int i = 0; i < n; i++) if (pole[i] == prvek) return i; return -1;}

jaká je časová složitost?jaká je časová složitost?• nejlepší případ nejlepší případ OO(1)(1)• nejhorší případ nejhorší případ OO(n)(n)• průměr průměr OO(n/2) – za jakých předpokladů?(n/2) – za jakých předpokladů?

Určení složitosti - příkladUrčení složitosti - příklad

vyhledání prvku v polivyhledání prvku v poli

int hledejSekvencne(int pole[n], int prvek){ for (int i = 0; i < n; i++) if (pole[i] == prvek) return i; return -1;}

jaká je časová složitost?jaká je časová složitost?• nejlepší případ nejlepší případ OO(1)(1)• nejhorší případ nejhorší případ OO(n)(n)• průměr průměr OO(n/2) – za jakých předpokladů?(n/2) – za jakých předpokladů?

jde to rychleji?jde to rychleji?

Určení složitosti - příkladUrčení složitosti - příklad

int hledejBinarne(int pole[n], int prvek){ int leva = 0; int prava = n; while (leva <= prava){ int stred = (prava-leva)/2 + leva; if (prvek > pole[stred]) leva = stred + 1; else if (prvek < pole[stred]) prava = stred - 1; else return stred; } return -1;}

Určení složitosti - příkladUrčení složitosti - příklad

časová složitost časová složitost OO(log n)(log n)

int hledejBinarne(int pole[n], int prvek){ int leva = 0; int prava = n; while (leva <= prava){ int stred = (prava-leva)/2 + leva; if (prvek > pole[stred]) leva = stred + 1; else if (prvek < pole[stred]) prava = stred - 1; else return stred; } return -1;}

Snížení čas. složitostiSnížení čas. složitosti

některé metody jsou genericky využitelné některé metody jsou genericky využitelné v mnoha problémech:v mnoha problémech:• předpočítávánípředpočítávání• stromystromy• hashehashe• heuristikyheuristiky• aproximaceaproximace

PředpočítáváníPředpočítávání

použitelné pokud se pohybujeme v použitelné pokud se pohybujeme v relativně malé množině hodnot, které je relativně malé množině hodnot, které je složité získatsložité získat

typický případ snížení časové složitosti na typický případ snížení časové složitosti na úkor složitosti prostorovéúkor složitosti prostorové• časová složitost časová složitost OO(1)(1)• prostorová je úměrná velikosti předpočítaných prostorová je úměrná velikosti předpočítaných

datdat pozor – cache miss je řádově 100x pozor – cache miss je řádově 100x

pomalejší než běžná instrukce – něco je pomalejší než běžná instrukce – něco je dnes snazší počítat, než načítat z RAMdnes snazší počítat, než načítat z RAM

Předpočítávání - příkladyPředpočítávání - příklady

goniometrické funkcegoniometrické funkce• Pro nižší přesnost (předpočítá se omezený Pro nižší přesnost (předpočítá se omezený

počet úhlů)počet úhlů)• dnes je levnější aproximace Taylorovým dnes je levnější aproximace Taylorovým

rozvojemrozvojem vesmírný simulátorvesmírný simulátor

• realistické gravitační polerealistické gravitační pole předpočítávání viditelnostipředpočítávání viditelnosti

• PVSPVS bourání domůbourání domů

• složitá fyzika počítána v čase t+nsložitá fyzika počítána v čase t+n

StromyStromy

běžné užitíběžné užití• vyhledávání prvku (vyhledávání prvku (OO(log n))(log n))• setřídění (O(n log n))setřídění (O(n log n))

při modifikaci problém při modifikaci problém vyvažovánívyvažování• nevyvážený strom ztrácí požadované vlastnostinevyvážený strom ztrácí požadované vlastnosti

užití:užití:• setřídění pole čísel, nalezení číslasetřídění pole čísel, nalezení čísla• vytvoření prostorové hierarchievytvoření prostorové hierarchie• vytvoření obálkové hierarchievytvoření obálkové hierarchie

Stromy - ukázkaStromy - ukázka

Stromy - ukázkaStromy - ukázka

HasheHashe

vyhledávání v relativně malé množině vyhledávání v relativně malé množině prvků z velké doményprvků z velké domény• slovníkyslovníky• prostorové umístění tělesprostorové umístění těles• heslahesla• aj.aj.

cíl – obvykle redukovat složitost cíl – obvykle redukovat složitost vyhledávání na vyhledávání na OO(1)(1)

Hashovací funkceHashovací funkce

mapuje vstupní klíč do indexu tabulkymapuje vstupní klíč do indexu tabulky hodnoty musí být mapovány rovnoměrně hodnoty musí být mapovány rovnoměrně

a náhodněa náhodně• pokud má více klíčů stejný hash, prohledávají pokud má více klíčů stejný hash, prohledávají

se tyto hashe sekvenčně (nebo je třeba je se tyto hashe sekvenčně (nebo je třeba je setřídit)setřídit)

• nalezení dobré hashovací funkce je někdy nalezení dobré hashovací funkce je někdy složité až nemožné (stojíme před úkolem složité až nemožné (stojíme před úkolem zajistit náhodné mapování nenáhodných dat)zajistit náhodné mapování nenáhodných dat)

hashovací funkci často hledáme pokusem hashovací funkci často hledáme pokusem a omylem, některé operace se obecně a omylem, některé operace se obecně hodí, využíváme velkých prvočíselhodí, využíváme velkých prvočísel

Příklad – hashování prostoruPříklad – hashování prostoru

metoda pro první fázi detekce kolizímetoda pro první fázi detekce kolizí prostor je rozdělen regulární mřížkou, prostor je rozdělen regulární mřížkou,

podle polohy na mřížce lze zakódovat podle polohy na mřížce lze zakódovat umístění tělesumístění těles

potenciálně kolidují tělesa se objeví na potenciálně kolidují tělesa se objeví na stejných indexech tabulkystejných indexech tabulky

výhodné při velkém množství výhodné při velkém množství pohybujících-se objektůpohybujících-se objektů

blíží se blíží se OO(n)(n)• zpomaluje nevhodná velikost mřížky, malá zpomaluje nevhodná velikost mřížky, malá

tabulkatabulka

Příklad hashování prostoruPříklad hashování prostoru Červený objekt se Červený objekt se

zahashuje do 0000zahashuje do 0000 Modrý do 0010 a 0110Modrý do 0010 a 0110 Žlutý do 0101 a 0110Žlutý do 0101 a 0110 Zelený do 0100, 0101, Zelený do 0100, 0101,

1000 a 10011000 a 1001

Jsou detekovány Jsou detekovány potenciální kolize:potenciální kolize:• Modrý x žlutýModrý x žlutý• Žlutý x zelenýŽlutý x zelený

Hashovací tabulkaHashovací tabulka

indexindex hodnotahodnota

00000000 čč

00010001

00100010 mm

00110011

01000100 m m žž

01010101 ž ž zz

01100110 zz

01110111

indexindex hodnotahodnota

10001000 zz

10011001 zz

10101010

10111011

11001100

11011101

11101110

11111111

HeuristikyHeuristiky

„„ořezávání“ nezajímavých větví výpočtuořezávání“ nezajímavých větví výpočtu problém s nalezením vhodných kritériíproblém s nalezením vhodných kritérií

• kterou větev zahodit, když nevidíme kterou větev zahodit, když nevidíme budoucnost?budoucnost?

užití např. užití např. • u pathfindingu (zahazování drahých cest)u pathfindingu (zahazování drahých cest)• v deskových hrách (zahazování nevýhodných v deskových hrách (zahazování nevýhodných

tahů)tahů)

AproximaceAproximace

nalezení přibližného výsledkunalezení přibližného výsledku někdy nutnost (fyzika), někdy výrazná někdy nutnost (fyzika), někdy výrazná

časová úspora (LOD, předpočítávání časová úspora (LOD, předpočítávání spojitých funkcí, heuristiky)spojitých funkcí, heuristiky)

problém obchodního cestujícího:problém obchodního cestujícího:• OO(n!)(n!)• Pomocí GA – počítáme dokud chceme lepší Pomocí GA – počítáme dokud chceme lepší

výsledekvýsledek

Lineární optimalizaceLineární optimalizace

optimalizace „na úrovni programových optimalizace „na úrovni programových řádků“řádků“

zůstáváme v téže složitostní třídě, rychlost zůstáváme v téže složitostní třídě, rychlost zvyšujeme pouze násobkemzvyšujeme pouze násobkem

je dobré znát náročnost běžných je dobré znát náročnost běžných programových konstrukcíprogramových konstrukcí

je dobré znát hardware, na kterém je dobré znát hardware, na kterém program poběžíprogram poběží

je dobré znát programové prostředí, je dobré znát programové prostředí, náročnost knihovních funkcí atd.náročnost knihovních funkcí atd.

Volání funkcíVolání funkcí

volání funkcí představuje určitou režiivolání funkcí představuje určitou režii• kompilátor umí sám rozhodnout, která funkce kompilátor umí sám rozhodnout, která funkce

bude linkována inlinebude linkována inline rychlost volání funkce závisí na počtu a rychlost volání funkce závisí na počtu a

velikosti(!) parametrůvelikosti(!) parametrů• velká data je vhodnější předávat odkazemvelká data je vhodnější předávat odkazem

virtuální metody jsou pomalejšívirtuální metody jsou pomalejší• Nepoužívejte pozdní vazbu u jednoduchých a Nepoužívejte pozdní vazbu u jednoduchých a

často volaných metodčasto volaných metod

Výkonnost hardwareVýkonnost hardware

elementární aritmetické operace +, - a * elementární aritmetické operace +, - a * jsou velmi rychlé, a to i v plovoucí řádové jsou velmi rychlé, a to i v plovoucí řádové čárcečárce• neceločíselné dělení je o řád pomalejšíneceločíselné dělení je o řád pomalejší

goniometrické funkce jsou pomalejší než goniometrické funkce jsou pomalejší než dělenídělení

některé operace lze vektorizovatněkteré operace lze vektorizovat paměť je škálována – registry, L2 cache, paměť je škálována – registry, L2 cache,

RAM, HDD…RAM, HDD…• někdy je lepší počítat, než „sahat“ do pamětiněkdy je lepší počítat, než „sahat“ do paměti

Odstranění rekurzeOdstranění rekurze

rekurze je drahárekurze je drahá• (pře)plnění zásobníku(pře)plnění zásobníku• režie s voláním a předáváním parametrůrežie s voláním a předáváním parametrů

některé algoritmy jsou v iterační formě některé algoritmy jsou v iterační formě špatně čitelnéšpatně čitelné

neexistuje obecný návod, jak rekurzi neexistuje obecný návod, jak rekurzi odstranitodstranit

Odstranění rekurze - příkladOdstranění rekurze - příklad

unsigned faktorial(unsigned x){unsigned faktorial(unsigned x){

if (x == 0)if (x == 0)

return 1;return 1;

elseelse

return x*faktorial(x-1);return x*faktorial(x-1);

}}

Odstranění rekurze - příkladOdstranění rekurze - příklad

unsigned faktorial(unsigned x){unsigned faktorial(unsigned x){

if (x == 0)if (x == 0)

return 1;return 1;

elseelse

return x*faktorial(x-1);return x*faktorial(x-1);

}}

unsigned faktorialOpt(unsigned x, unsigned p = 1){unsigned faktorialOpt(unsigned x, unsigned p = 1){

if (x == 0)if (x == 0)

return p;return p;

elseelse

return faktorialOpt(x-1, x*p);return faktorialOpt(x-1, x*p);

}}

Kdy optimalizovat?Kdy optimalizovat?

optimalita kódu je nepřímo úměrná jeho optimalita kódu je nepřímo úměrná jeho čitelnostičitelnosti

nesoustřeďte se na kód na úrovni nesoustřeďte se na kód na úrovni programových řádků, hledejte úzká hrdlaprogramových řádků, hledejte úzká hrdla• někdy je úzké hrdlo zjevnéněkdy je úzké hrdlo zjevné• někdy zjevné neníněkdy zjevné není

nepočítali jsme s tím, že se daný kód volá tak častonepočítali jsme s tím, že se daný kód volá tak často některá funkce trvá déle, než jsme si mysleliněkterá funkce trvá déle, než jsme si mysleli přehlédli jsme zbytečné volání či nezoptimalizovanou přehlédli jsme zbytečné volání či nezoptimalizovanou

funkcifunkci je dobré používat profiler – najde chyby rychleji než je dobré používat profiler – najde chyby rychleji než

mymy

Kdy neoptimalizovat?Kdy neoptimalizovat?

často optimalizujeme ze zvyku i tam, kde často optimalizujeme ze zvyku i tam, kde to není nutnéto není nutné• existují třídící algoritmy v O(nexistují třídící algoritmy v O(n22) a O(n log n), ) a O(n log n),

má smysl o tom uvažovat u setřídění listiny má smysl o tom uvažovat u setřídění listiny vítězů, kterých je max. 20?vítězů, kterých je max. 20?

• pozná někdo co dělá toto?pozná někdo co dělá toto?while(*s++ = *t++);while(*s++ = *t++);

Kdy neoptimalizovat?Kdy neoptimalizovat?

často optimalizujeme ze zvyku i tam, kde často optimalizujeme ze zvyku i tam, kde to není nutnéto není nutné• existují třídící algoritmy v O(nexistují třídící algoritmy v O(n22) a O(n log n), ) a O(n log n),

má smysl o tom uvažovat u setřídění listiny má smysl o tom uvažovat u setřídění listiny vítězů, kterých je max. 20?vítězů, kterých je max. 20?

• pozná někdo co dělá toto?pozná někdo co dělá toto?while(*s++ = *t++);while(*s++ = *t++); nemachrujte – nikdy nevíte, kdo to po vás bude číst!nemachrujte – nikdy nevíte, kdo to po vás bude číst!

Kdy neoptimalizovat?Kdy neoptimalizovat?

často optimalizujeme ze zvyku i tam, kde často optimalizujeme ze zvyku i tam, kde to není nutnéto není nutné• existují třídící algoritmy v O(nexistují třídící algoritmy v O(n22) a O(n log n), má ) a O(n log n), má

smysl o tom uvažovat u setřídění listiny vítězů, smysl o tom uvažovat u setřídění listiny vítězů, kterých je max. 20?kterých je max. 20?

• pozná někdo co dělá toto?pozná někdo co dělá toto?while(*s++ = *t++);while(*s++ = *t++); nemachrujte – nikdy nevíte, kdo to po vás bude číst!nemachrujte – nikdy nevíte, kdo to po vás bude číst!

• neoptimalizujte části kódu, které se volají neoptimalizujte části kódu, které se volají současně s výrazně náročnější operacísoučasně s výrazně náročnější operací

šetření času CPU při načítání z disku (ovšem pokud šetření času CPU při načítání z disku (ovšem pokud nejedete multivláknově)nejedete multivláknově)

výpočty před/po dlouhým cyklemvýpočty před/po dlouhým cyklem

ProfilerProfiler

dynamická analýza výkonnosti programudynamická analýza výkonnosti programu měří, kolik času tráví CPU v jednotlivých měří, kolik času tráví CPU v jednotlivých

funkcích, jak často je voláfunkcích, jak často je volá obvykle umožňuje přímo diassemblovat obvykle umožňuje přímo diassemblovat

jednotlivé řádky kódujednotlivé řádky kódu dobře použitelný u zpracování dat s nízkou dobře použitelný u zpracování dat s nízkou

úrovní paralelizaceúrovní paralelizace je dobré připravit profileru různé „scénáře“je dobré připravit profileru různé „scénáře“

UkázkaUkázka

Dotazy?Dotazy?

Děkuji za pozornost.Děkuji za pozornost.