C2142 Návrh algoritmů pro přírodovědce
2. Úvod do složitosti
Tomáš Raček
Jaro 2016
Hledání nejčastějších slov – frequent_words
Zadání. Nalezněte v textu řetězce délky k s nejvyšším počtem
výskytů.
frequent_words(text, k)
1. Pro každý podřetězec délky k řetězce text spočítej jeho výskyt
pomocí funkce pattern_count(text, pattern)
2. Urči nejvyšší nalezenou četnost
3. Vrať řetězce s touto nejvyšší četností
Praktický test.
• krátké řetězce – frequent_words uspokojivě funguje
• dlouhé řetězce – nepoužitelné, čas výpočtu neodpovídá odhadu
frequent_words – doba výpočtu
Pozorování
• doba výpočtu je úměrná velikosti vstupních dat
• závislost není nutně lineární – výpočet na 1000krát větší úloze
nemusí trvat 1000krát déle
• na různých strojích/architekturách různé časy výpočtu
• Thinkpad T430s: 7 s
• Thinkpad X200s: 14 s
Důsledek (1). Nutná hlubší analýza frequent_words.
Důsledek (2). Porovnání náročnosti algoritmů podle času výpočtu
není vhodné, potřebujeme aparát nezávislý na konkrétním
stroji/architektuře.
Složitost
Složitost algoritmu. Zaveďme složitost algoritmu jako funkci f(n),
kde n je velikost vstupu.
Návrh. f(n) určuje počet jednoduchých operací daného algoritmu
pro vyřešení problému o velikosti n.
• jednoduché operace ≈ instrukce CPU (např. sečtení nebo
porovnání dvou čísel, AND/OR,…)
• řešení nezávislé na architektuře
Důsledek. Porovnání efektivity algoritmů lze zjednodušeně převést
na porovnání jejich složitostí.
Asymptotická složitost – definice
Formální definice
O(g) = { f | ∃c ∈ R+
, ∃n0 ∈ N : ∀n ≥ n0 : 0 ≤ f(n) ≤ c · g(n)}
f ∈ O(g) čteme „ f roste asymptoticky nejvýše tak rychle jako g“.
Význam konstant
c rozdíl pouze v multiplikativní konstantě nepovažujeme za
významný, tj. ztotožňujeme např. n2 a 4n2
n0 uvažujeme pouze „velká“ n
Poznámka. Analogicky lze definovat další množiny:
• f ∈ Ω(g) – f roste asymptoticky alespoň tak rychle jako g
• f ∈ Θ(g) – f roste asymptoticky právě tak rychle jako g
Asymptotická složitost – příklady
Rychlost růstu funkcí
log n n n log n n2
2n
n! pro n → ∞
Příklady
Funkce Složitostní třída Pojmenování
2142 O(1) konstantní
2 log n + 4 O(log n) logaritmická
0.5n + log n O(n) lineární
n2 − 10n O(n2) kvadratická
6n3 O(n3) kubická
2n − 1 O(2n) exponenciální
Poznámka. Ověření, zdali f ∈ O(g), lze provést výpočtem limity
limn→∞ f(n)/g(n).
Složitost problému
Cíl. Snaha o nalezení efektivních algoritmů pro daný problém.
Otázka. Lze zrychlovat pořád, nebo existuje nějaký dolní limit?
Složitost problému
• minimální počet operací potřebný pro vyřešení libovolné
instance problému
• nutno odvodit teoreticky → mnohdy netriviální
• odpovídá složitosti optimálního algoritmu pro daný problém
Jak ale poznám optimální algoritmus? Srovnejme odhady složitosti
problému Pi a složitosti algoritmů Aj řešící tento problém:
P1(n) < . . . < Pk(n) ≤ A1(n) < . . . < Am(n)
A je optimální algoritmus, pokud A(n) = Pk(n).
Složitost problému – příklady
Nalezení nejmenšího prvku pole
• je nutné projít všechny prvky pole – Ω(n) operací
• algoritmus se složitostí O(n) jistě existuje → složitost problému
(= složitost optimálního algoritmu) je lineární
Násobení matic
• potřeba Ω(n2) operací
• naivní algoritmus – O(n3)
• Strassenův algoritmus – O(nlog2 7) O(n2,81)
• aktuálně nejlepší algoritmus (2014) – O(n2,372...)
• nalezení optimálního algoritmu je otevřený problém
Prostorová složitost
Prostorová složitost. Vedle časové náročnosti algoritmů lze určit i
množství paměti, které algoritmus potřebuje pro svůj výpočet.
• velikost vstupních (a výstupních) dat neuvažujeme
• vyjadřujeme také O-notací
In situ algoritmus vyžaduje navíc pouze O(1) paměti.
• výpočet průměrné hodnoty prvků v poli
• naivní násobení matic
• …
Otázka. Je lepší in situ algoritmus s časovou složitostí O(n2) než
algoritmus s časovou složitostí O(n log n) a prostorovou složitostí
O(n)?
Vztah mezi časem a prostorem
Teze. Někdy lze snížit časovou složitost algoritmu zvýšením jeho
prostorové složitosti (a naopak).
↑ prostor ↓ čas
• softwarová cache
• předpočítání (mezi)výsledků
↑ čas ↓ prostor
• komprese
• zvýšení abstrakce
Složitost v praxi
Tabulka časů výpočtu algoritmů o složitostech log n, n, n2, 2n a pro
vstup velikosti 10, 20, 50 a 1000. Předpokládejme, že jedna iterace
algoritmu trvá 1µs.
10 20 50 1000
log n 0,000001 s 0,000001 s 0,000002 s 0,000003 s
n 0,00001 s 0,00002 s 0,00005 s 0,001 s
n2 0,0001 s 0,0004 s 0,0025 s 1 s
2n 0,001024 s 1,048576 s 35,7 let 3, 4 · 10287 let
Poznámka. Stáří vesmíru je odhadováno na 13, 8 · 109 let.
pattern_count – analýza
def pattern_count(text, pattern):
count = 0
for i in range(0, 1 + len(text) - len(pattern)):
if text[i : i + len(pattern)] == pattern:
count += 1
return count
Pozorování
• procházíme celkem |text| − |pattern| + 1 možných umístění
• každé porovnání dvou řetězců obnáší nejvýše |pattern|
porovnání jednotlivých znaků
Závěr. Počet kroků, které vykoná funkce pattern_count, lze vyjádřit
jako O(|pattern| · (|text| − |pattern| + 1)).
frequent_words – analýza I
def frequent_words(text, k):
counts = dict()
frequent_patterns = set()
for i in range(0, len(text) - k + 1):
pattern = text[i : i + k]
counts[pattern] = pattern_count(text, pattern)
max_count = max(counts.values())
for (pattern, count) in counts.items():
if count == max_count:
frequent_patterns.add(pattern)
return frequent_patterns
Pozorování
• počet volání pattern_count je |text| − k + 1
• další příkazy nejsou určující pro dobu běhu
frequent_words – analýza II
Složením předchozích informací dostáváme:
frequent_words(text, k)
• složitost funkce pattern_count je
O(|pattern| · (|text| − |pattern| + 1))
• počet volání pattern_count je |text| − k + 1
• platí k = |pattern|
• počet kroků celkem:
k · (|text| − k + 1) · (|text| − k + 1) = k · (|text| − k + 1)2
V praxi platí k |text|, asymptotická složitost funkce frequent_words
je tedy O(k · |text|2).
frequent_words – praxe
Měření. Doba výpočtu funkce frequent_words(text, k) pro k = 9 a
|text| = {1000, . . . , 9000}.
Pozorování. Naměřená data lze úspěšně proložit parabolou, což
odpovídá odhadnuté složitosti O(k · |text|2).
Hledání nejčastějších slov v textu
Dosavadní řešení. Jsme schopni navrhnout a implementovat
algoritmus se složitostí O(k · |text|2).
Zásadní otázka. Jde to i lépe?
Alternativní návrh. Počítání četností podřetězců při průchodu
textem
1. Procházej vstupní text postupně po podřetězcích délky k
1.1 Pokud se konkrétní podřetězec vyskytl poprvé, nastav jeho
četnost na 1, jinak ji zvyš o 1
2. Urči nejvyšší nalezenou četnost
3. Vrať řetězce s touto nejvyšší četností
faster_frequent_words
Jak ukládat pro každý řetězec jeho četnost?
• počet různých řetězců délky k z písmen A, C, G, T je 4k
• každému tomuto řetězci lze přiřadit číslo od 0 do 4k − 1
Příklad pro k = 3:
AAA → 0, AAC → 1, AAG → 2, . . . , TTT → 63
Příklad převodu řetězce na číslo. A → 0, C → 1, G → 2, T → 3.
ACCTG → A · 44
+ C · 43
+ C · 42
+ T · 41
+ G · 40
ACCTG → 0 + 64 + 16 + 12 + 2
ACCTG → 94
Implementace. Vytvořím pole o velikosti 4k, kde budu ukládat
četnosti jednotlivých řetězců.
Převod řetězce na číslo – implementace
def pattern2number(pattern):
characters = "ACGT"
if pattern == "":
return 0
else:
return 4 * pattern2number(pattern[:-1]) \
+ characters.index(pattern[-1:])
def number2pattern(number, k):
characters = "ACGT"
if k == 0:
return ""
else:
divisor = 4 ** (k - 1)
return characters[number // divisor] \
+ number2pattern(number % divisor, k - 1)
faster_frequent_words – implementace
def computing_frequencies(text, k):
frequency_array = [0] * (4 ** k)
for i in range(len(text) - k + 1):
pattern = text[i: i + k]
frequency_array[pattern2number(pattern)] += 1
return frequency_array
def faster_frequent_words(text, k):
frequent_patterns = set()
frequency_array = computing_frequencies(text, k)
max_count = max(frequency_array)
for i in range(0, 4 ** k):
if frequency_array[i] == max_count:
frequent_patterns.add(number2pattern(i, k))
return frequent_patterns
Složitost faster_frequent_words
Složitost jednotlivých fází algoritmu
• inicializace pole četností O(4k)
• převod řetězce na číslo (a naopak) O(k)
• průchod vstupním textem, počítání četností O(k · (|text| − k + 1))
• nalezení nejvyšší četnosti O(4k)
• výběr řetězců s nejvyšší četností O(k · 4k)
Celková složitost faster_frequent_words. Po úpravě dostáváme
složitost O(k · |text| + k · 4k), přičemž paměťová složitost je O(4k).
Závěr. Pro k n je faster_frequent_words výrazně rychlejší než
frequent_words.
A jde to ještě lépe? ;-)