Vyhledávání, řazení, složitost IB111 Základy programování Radek Pelánek 2017 1 / 61 ... ale nejdřív Praktické rady: čtení chybových hlášek časté chyby 2 / 61 Čtení chybových hlášek Traceback (most recent call last): File "sorting.py", line 63, in test_sorts() File "sorting.py", line 59, in test_sorts sort(a) File "sorting.py", line 52, in insert_sort a[j] = curent NameError: name ’curent’ is not defined kde je problém? (identiﬁkace funkce, číslo řádku) co je za problém (typ chyby) 3 / 61 Základní typy chyb SyntaxError invalid syntax: zapomenutá dvojtečka či závorka, záměna = a ==, . . . EOL while scanning string literal: zapomenutá uvozovka NameError – špatné jméno proměnné (překlep v názvu, chybějící inicializace) IndentationError – špatné odsazení TypeError – nepovolená operace (sčítání čísla a řetězce, přiřazení do řetězce, . . . ) IndexError – chyba při indexování řetězce, seznamu a podobně („out of range ) 4 / 61 Časté chyby projeví se „rychle (program spadne hned): zapomenutá dvojtečka, závorka, uvozovka překlepy použití = tam, kde mělo být == špatný počet argumentů při volání funkce zapomenuté len v “for i in range(alist)” 5 / 61 Časté chyby nemusí se projevit rychle / vždy: použití == tam, kde mělo být = "True" místo True záměna print a return chybné indexování (řetězce, seznamy) dělení nulou 6 / 61 Otrávené studny 8 studen, jedna z nich je otrávená laboratorní rozbor dokáže rozpoznat přítomnost jedu ve vodě je drahý kolik rozborů potřebujeme? jak určit otrávenou studnu? 7 / 61 Otrávené studny II 8 studen, jedna z nich je otrávená laboratorní rozbor dokáže rozpoznat přítomnost jedu ve vodě je drahý je časově náročný (1 den) jak určit otrávenou studnu za 1 den pomocí 3 paralelních rozborů? 8 / 61 Otrávené studny: řešení Řešení s využitím binárních čísel studna kód studna kód A 000 E 100 B 001 F 101 C 010 G 110 D 011 H 111 test přidělené studny 1 B, D, F, H 2 C, D, G, H 3 E, F, G, H 9 / 61 Vyhledávání: hra Myslím si přirozené číslo X mezi 1 a 1000. Povolená otázka: „Je X menší než N? Kolik otázek potřebujete na odhalení čísla? 10 / 61 Vyhledávání: hra Myslím si přirozené číslo X mezi 1 a 1000. Povolená otázka: „Je X menší než N? Kolik otázek potřebujete na odhalení čísla? Mezi kolika čísly jste schopni odhalit skryté číslo na K otázek? 10 / 61 Vyhledávání: řešení půlení intervalu K otázek: rozlišíme mezi 2K čísly N čísel: potřebujeme log2 N otázek 11 / 61 Připomenutí: logaritmus y = logb(x) ⇔ x = by log10(1000) = 3 log2(16) = 4 log2(1024) = 10 logb(xy) = logb(x) + logb(y) http://www.khanacademy.org/math/algebra/logarithms https://www.umimematiku.cz/pocitani-logaritmy-3-uroven 12 / 61 Logaritmus – graf 13 / 61 Logaritmus – test log3(81) = ? log2(2) = ? log5(1) = ? log10(0.1) = ? log2( √ 2) = ? log0.5(4) = ? 14 / 61 Vyhledávání: motivace vyhledávání v (připravených) datech je velmi častý problém: web slovník informační systémy dílčí krok v algoritmech 15 / 61 Vyhledávání: konkrétní problém vstup: seřazená posloupnost čísel + dotaz (číslo) výstup: pravdivostní hodnota (True/False) příp. index hledaného čísla v posloupnosti (-1 pokud tam není) příklad: vstup: 2, 3, 7, 8, 9, 14 + dotaz 8 výstup: True, resp. 3 (číslování od nuly) 16 / 61 Vyhledávání a logaritmus naivní metoda = průchod seznamu lineární vyhledávání, O(n) pomalé (viz např. databáze s milióny záznamů) jen velmi krátké seznamy základní rozumná metoda = půlení intervalu logaritmický počet kroků (vzhledem k délce seznamu), O(log(n)) 17 / 61 Vyhledávání: půlení intervalu binární vyhledávání podobné jako: hra s hádáním čísel, aproximace odmocniny podíváme se na prostřední člen ⇒ podle jeho hodnoty pokračujeme v levém/pravém intervalu udržujeme si „horní mez a „spodní mez 18 / 61 Binární vyhledávání – ilustrace Wikipedia 19 / 61 Vyhledávání: program def binary_search(value, alist): lower_bound = 0 upper_bound = len(alist) - 1 while lower_bound <= upper_bound: middle = (lower_bound + upper_bound) // 2 if alist[middle] == value: return True elif alist[middle] > value: upper_bound = middle - 1 else: lower_bound = middle + 1 return False 20 / 61 Přípomenutí: výpočet odmocniny def square_root(x, precision=0.01): upper = x lower = 0 middle = (upper + lower) / 2 while abs(middle**2 - x) > precision: if middle**2 > x: upper = middle if middle**2 < x: lower = middle middle = (upper + lower) / 2 return middle 21 / 61 Vyhledávání, přidávání, ubírání seřazený seznam – rychlé vyhledávání, ale pomalé přidávání prvků rychlé vyhledávání, přidávání i ubírání prvků – datová struktura slovník; vyhledávací stromy, hašovací tabulky více později / v IB002 22 / 61 Řadicí algoritmy: terminologická poznámka anglicky „sorting algorithm česky používáno: řadicí algoritmy nebo třídicí algoritmy řadicí vesměs považováno za „správnější 23 / 61 Řadicí algoritmy: komentář mnoho různých algoritmů pro stejný účel většina programovacích jazyků má vestavěnou podporu (funkce sort()) Proč se tím tedy zabýváme? 24 / 61 Řadicí algoritmy: komentář Proč se tím tedy zabýváme? 1 procvičení práce se seznamy 2 ilustrace algoritmického myšlení, technik návrhu algoritmů 3 typický příklad drobné změny algoritmu s velkým dopadem na rychlost programu 4 hezky se to vizualizuje a vysvětluje 5 tradice, patří to ke vzdělání informatika 6 občas se to může i hodit 25 / 61 Řadicí algoritmy: komentář zde důraz na jednoduché algoritmy, základní použití seznamů, intuici detailněji v IB002 Algoritmy a datové struktury I pokročilejší algoritmy důkazy korektnosti složitost formálně 26 / 61 Doporučené zdroje http://www.sorting-algorithms.com/ animace kódy vizualizace http://sorting.at/ elegantní animace více podobných: Google → sorting algorithms a na zpestření: xkcd Ineﬀective Sorts: https://xkcd.com/1185/ Bubble-sort with Hungarian folk dance: http://www.youtube.com/watch?v=lyZQPjUT5B4 27 / 61 Řadicí algoritmy: problém vstup: posloupnost (přirozených) čísel např. 8, 2, 14, 3, 7, 9 výstup: seřazená posloupnost např. 2, 3, 7, 8, 9, 14 pozn. většina zmíněných algoritmů aplikovatená nejen na čísla, ale na „cokoliv, co umíme porovnávat 28 / 61 Pokus č. 1 zkoušíme systematicky všechna možná uspořádání prvků pro každé z nich ověříme, zda jsou prvky korektně uspořádány je to dobrý algoritmus? 29 / 61 Co vy na to? zkuste vymyslet řadicí algoritmus co nejvíce různých principů co nejefektivnější algoritmus možná inspirace: jak řadíte karty? 30 / 61 Složitost n – délka vstupní posloupnosti počet operací jednoduché algoritmy O(n2 ) složitější algoritmy O(n log(n)) 31 / 61 Bublinkové řazení (Bubble sort) „probublávání vyšších hodnot nahoru srovnávání a prohazování sousedů po i iteracích je nejvyšších i členů na svém místě 32 / 61 Bublinkové řazení: program def bubble_sort(a): n = len(a) for i in range(n): for j in range(n-i-1): if a[j] > a[j+1]: tmp = a[j] a[j] = a[j+1] a[j+1] = tmp invariant cyklu: a[n-i-1:] ve ﬁnální pozici 33 / 61 Bublinkové řazení: příklad běhu [8, 2, 7, 14, 3, 1] [2, 7, 8, 3, 1, 14] [2, 7, 3, 1, 8, 14] [2, 3, 1, 7, 8, 14] [2, 1, 3, 7, 8, 14] [1, 2, 3, 7, 8, 14] 34 / 61 Implementační detail: prohazování prvků prohození hodnot dvou proměnných a, b na slidech psáno „běžným způsobem pomocí pomocné proměnné: t = a; a = b; b = t Python umožňuje zápis: a, b = b, a 35 / 61 Řazení výběrem (Select sort) řazení výběrem projdeme dosud neseřazenou část seznamu a vybereme nejmenší prvek nejmenší prvek zařadíme na aktuální pozici (výměnou) 36 / 61 Řazení výběrem: program def select_sort(a): for i in range(len(a)): selected = i for j in range(i+1, len(a)): if a[j] < a[selected]: selected = j tmp = a[i] a[i] = a[selected] a[selected] = tmp 37 / 61 Řazení vkládáním (Insert sort) podobně jako „řazení karet preﬁx seznamu udržujeme seřazený každou další hodnotu zařadíme tam, kam patří 38 / 61 Řazení vkládáním: program def insert_sort(a): for i in range(1,len(a)): current = a[i] j = i while j > 0 and a[j-1] > current: a[j] = a[j-1] j -= 1 a[j] = current 39 / 61 Význam proměnných proměnná selected u řazení výběrem index vybraného prvku používáme k indexování, a[selected] proměnná current u řazení vkládáním hodnota „posunovaného prvky a[j] = current v našich případech mají stejný typ (int), ale jiný význam a použití (záměna = častý zdroj chyb) zřejmější pokud řadíme řetězce 40 / 61 Quicksort rekurzivní algoritmus vybereme „pivota a seznam rozdělíme na dvě části: větší než pivot menší než pivot obě části pak nezávisle seřadíme (rekurzivně pomocí quicksortu) pokud máme smůlu při výběru pivota, tak je stejně pomalý jako předchozí v průměrném případě je rychlý – quick O(n log(n)) 41 / 61 Řazení slučováním (Merge sort) rekurzivní algoritmus seznam rozdělíme na dvě poloviny a ty seřadíme (pomocí Merge sort) ze seřazených polovin vyrobíme jeden seřazený seznam – „zipování vždy efektivní – O(n log(n)) 42 / 61 Speciﬁcké předpoklady – efektivnější algoritmus předchozí algoritmy využívají pouze operaci porovnání dvou hodnot aplikovatelné na cokoliv, co lze porovnávat, žádné další předpoklady s doplňujícími předpoklady můžeme dostat nové algoritmy (obecný princip) řazení (krátkých) čísel → Radix sort 43 / 61 Radix sort seznam („krátkých ) čísla postupujeme od nejméně významné cifry k nejvýznamnější seřadíme čísla podle dané cifry = rozdělení do 10 „kyblíčků (jednoduché, rychlé) 44 / 61 Složitost trochu podrobněji složitost algoritmu – jak je algoritmus výpočetně náročný časová, prostorová měříme počet operací, nikoliv čas na konkrétním stroji vyjadřujeme jako funkci délky vstupu O notace – zanedbáváme konstanty např. O(n), O(n log(n)), O(n2 ) 45 / 61 Ilustrace rozdílů v složitosti 46 / 61 Složitost řadicích algoritmů n – délka vstupní posloupnosti počet operací jednoduché algoritmy O(n2 ) složitější algoritmy O(n log(n)) 47 / 61 Python: Seznam funkcí Pro zajímavost: v Pythonu můžeme mít třeba i seznam funkcí def test_sorts(): for sort in [bubble_sort, insert_sort, select_sort]: a = [41, 71, 46, 15, 97, 44, 30, 11] sort(a) print(a) 48 / 61 Vyhledávání a řazení v Pythonu x in alist – test přítomnosti x v seznamu alist.index(x) – pozice x v seznamu alist.count(x) – počet výskytů x v seznamu alist.sort() – seřadí položky seznamu sorted(alist) – vrátí seřazené položky seznamu (ale nezmění vlastní proměnnou) pro řazení používá Python Timsort – kombinaci řazení slučováním a vkládáním 49 / 61 Různé způsoby řazení s = ["prase", "Kos", "ovoce", "Pes", "koza", "ovce", "kokos"] print(sorted(s)) print(sorted(s, reverse=True)) print(sorted(s, key=str.lower)) print(sorted(s, key=len)) print(sorted(s, key=lambda x: x.count("o"))) 50 / 61 Řazení za využití key https://developers.google.com/edu/python/sorting 51 / 61 Řazení v Pythonu: poznámky ukázky sorted: reverse, key – pojmenované argumenty parametrem funkce (key) je funkce vestavěná funkce: len, str.lower vlastní funkce: count letter o, get third letter „anonymní lambda funkce: lambda x: x.count("o") praktické použití: příklad: seřazení jmen studentů podle bodů na písemce využití dalších datových struktur, ukázky později 52 / 61 Unikátní prvky, nejčastější prvek máme seznam prvků, např. výsledky dotazníku (oblíbený programovací jazyk): ["Python", "Java", "C", "Python", "PHP", "Python", "Java", "JavaScript", "C", "Pascal"] chceme: seznam unikátních hodnot nejčastější prvek 53 / 61 Unikátní prvky, nejčastější prvek máme seznam prvků, např. výsledky dotazníku (oblíbený programovací jazyk): ["Python", "Java", "C", "Python", "PHP", "Python", "Java", "JavaScript", "C", "Pascal"] chceme: seznam unikátních hodnot nejčastější prvek přímočaře: opakované procházení seznamu efektivněji: seřadit a pak jednou projít elegantněji: využití pokročilých datových struktur / konstrukcí 53 / 61 Unikátní prvky def unique(alist): alist = sorted(alist) # rozdilne chovani od alist.sort() !! result = [] for i in range(len(alist)): if i == 0 or alist[i-1] != alist[i]: result.append(alist[i]) return result def unique(alist): return list(set(alist)) 54 / 61 Nejčastější prvek přímočaře def most_common(alist): alist = sorted(alist) max_value, max_count = None, 0 current_value, current_count = None, 0 for value in alist: if value == current_value: current_count += 1 else: current_value = value current_count = 1 if current_count > max_count: max_value = current_value max_count = current_count return max_value 55 / 61 Nejčastější prvek soﬁstikovaněji def most_common(alist): return max(alist, key=alist.count) Stack Overﬂow diskuze: http://stackoverflow.com/questions/1518522/python-most-common-element-in-a-list 56 / 61 Přesmyčky přesmyčky = slova poskládaná ze stejných písmen úkol: rozpoznat, zda dvě slova jsou přesmyčky vstup: dva řetězce výstup: True/False příklady: odsun, dusno → True kostel, les → False houslista, souhlasit → True ovoce, ovace → False 57 / 61 Přesmyčky řešení seřadíme písmena obou slov přesmyčky ⇔ po seřazení identické implementace za využití sorted přímočará def anagram(word1, word2): return sorted(word1) == sorted(word2) 58 / 61 Reklama na řazení řazení: velmi častý dílčí krok při programování i když to na první pohled nemusí být vidět vhodné uspořádání výstupů programu a koření v supermarketu! a taky se hodí, když jste krab: https://www.youtube.com/watch?v=f1dnocPQXDQ 59 / 61 Shrnutí vyhledávání: půlení intervalu řadicí algoritmy: jednoduché (kvadratické): bublinkové, výběrem, vkládáním složitější (n · log(n), rekurzivní): quick sort, slučování praktické použití řazení příklady 60 / 61