Vyhledávání, řazení, složitost
IB113 Radek Pelánek
2021
Otrávené studny
• 8 studen, jedna z nich je otrávená
• laboratorní rozbor
• dokáže rozpoznat přítomnost jedu
• je drahý
• kolik rozborů potřebujeme?
• jak určit otrávenou studnu?
• 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)
o jak určit otrávenou studnu za 1 den pomocí 3 paralelních rozborů?
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	
Vyhledávání: hra
• Myslím si přirozené číslo X mezi 1 a 1000.
• Povolená otázka: „Je X menší než A/?"
• Kolik otázek potřebujete na odhalení čísla?
Vyhledávání: hra
• Myslím si přirozené číslo X mezi 1 a 1000.
• Povolená otázka: „Je X menší než A/?"
• Kolik otázek potřebujete na odhalení čísla?
• Mezi kolika čísly jste schopni odhalit skryté číslo K otázek?
Vyhledávání: řešení
• půlení intervalu
• K otázek: rozlišíme mezi 2K čísly
• N čísel: potřebujeme log2 N otázek
6/55
řipomenutí: logaritmus
log10(1000) =3 log2(16) = 4 log2(1024)   = 10
http://www.khanacademy.org/math/algebra/logarithms https://www.umimematiku.cz/pocitani-logaritmy-3-uroven
Logaritmus - graf
i
o ■1
■2 ■3
y				
				
				
				
	? i	X í	5 \	3 1
				
				
				
\
Vyhledávání: motivace
vyhledávání v (pripravených) datech je velmi častý problém
• web
• slovník
• informační systémy
• dílčí krok v algoritmech
10/55
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)
11/55
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), 0(log(n))
Vyhledávání: půlení intervalu
o 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"
1, 3, 7, 12, 13, 18, 24, 35, 37, 39, 42, 53, 87, 88, 91, 98
Binární vyhledávání - ilustrace
I
4 < 7
		i—4 < 6 r. i								
1	3		4	6	7		8	10	13	14
Wikipedia
14/55
1
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) if alist[middle] == value:
return True elif alist[middle] > value:
upper_bound = middle - 1 else:
lower_bound = middle + 1 return False
// 2
15/55
Pripomenutí: výpočet odmocniny
def square_root(x, precision=0.01): lower = 0 upper = x
middle = (upper + lower) / 2 while abs(middle**2 - x) > precision print(lower, upper, sep=M\tM) if middle**2 > x:
upper = middle if middle**2 < x:
lower = middle middle = (upper + lower) / 2 return middle
Vyhledávání, přidávání, ubírání
a 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
Řadicí algoritmy: terminologická poznámka
• anglicky „sorting algorithm"
9 česky používáno: řadicí algoritmy nebo třídicí algoritmy
• řadicí vesměs považováno za „správnější"
18/55
Řadicí algoritmy: komentár
• mnoho různých algoritmů pro stejný účel
• většina programovacích jazyků má vestavěnou podporu (funkce sort O)
Proč se tím tedy zabýváme?
19/55
Řadicí algoritmy: komentá
Proč se tím tedy zabýváme? O procvičení práce se seznamy
Q ilustrace algoritmického myšlení, technik návrhu algoritmů
O typický příklad drobné změny algoritmu s velkým dopadem na rychlost programu
O hezky se to vizualizuje a vysvětluje
O tradice, patří to ke vzdělání (alespoň u informatika)
O občas se to může i hodit
20/55
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 Ineffective Sorts: https://xkcd.com/1185/
• Bubble-sort with Hungarian folk dance:
http://www.youtube.com/watch?v=lyZQPjUT5B4
v
Ř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"
22/55
• 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?
23/55
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?
24/55
Složitost
n - délka vstupní posloupnosti
počet operací
jednoduché algoritmy složitější algoritmy
0{n2) 0(nlog(n))
25/55
Bublinkové řazení (Bubble sort)
• „probublávání" vyšších hodnot nahoru 9 srovnávání a prohazování sousedů
• po / iteracích je nejvyšších / členů na svém místě
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+l] :
invariant cyklu: a[n-i-l:] ve finální pozici
tmp = a [j] a [j] = a[j+l] a[j+l] = tmp
27/55
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]
Implementační detail: prohazování prvků
• prohození hodnot dvou proměnných x, y
• na slidech psáno „běžným" způsobem pomocí pomocné proměnné: t = x; x = y; y = t
• Python umožňuje zápis: x, y = y, x
29/55
zení 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)
v
Razení výběrem: program
def select_sort(a):
for i in range(len(a)): selected = i
for j in range(i+l, len(a)): if a[j] < a[selected] : selected = j tmp = a[i] a[i] = a [selected] a [selected] = tmp
31/55
Řazení vkládáním (Insert sort)
• podobně jako „řazení karet"
• prefix seznamu udržujeme seřazený
• každou další hodnotu zařadíme tam, kam patří
32/55
Razení vkládáním: program
def insert_sort(a):
for i in ranged, len(a)): current = a[i]
j= 1
while j > 0 and a[j-l] > current:
a [j] = a[j-l]
j -= 1 a [j] = current
33/55
Význam proměnných
• proměnná selected u řazení výběrem
• index vybraného prvku
• používame 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
34/55
• 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)
• v průměrném případě je rychlý - quick 0(n\og(n))
w   pokud máme smůlu při výběru pivota, může být stejně pomalý jako předchozí
35/55
Ř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í - 0(nlog(n))
36/55
Specifické 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
ix 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é)
329	720	720	329
457	355	329	355
657	436	436	436
839 -	■■■n- 457 ......in-	839 ■■	Hu- 457
436	657	355	657
720	329	457	720
355	839	657	839
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms.
38/55
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), 0(n log(n)), 0(n2)
Ilustrace rozdílů v složitosti
n	logn	n	nlogn		n3	2n
8	3 nsec	0.01 /*	0.02 íx	0.06 //	0.51 fi	0.26 fi
16	4 nsec	0.02 fi	0.06 fi	0.26 fi	4.10 fi	65.5 fi
32	5 nsec	0.03 jti	0.16 /x	1.02 /x	32.7 fi	4.29 sec
64	6 nsec	0.06 fi	0.38 fi	4.10 fi	262 fi	5.85 cent
128	0.01 fi	0.13 /i	0.90 /x	16.38 m	0.01 sec	1020 cent
256	0.01 tx	0.26 pt	2.05 /x	65.54 p	0.02 sec	1058 cent
512	0.01 n	0.51 fi	4.61 fi	262.14 fi	0.13 sec	10135 cent
2048	0.01 /x	2.05 p	22.53 /*	0.01 sec	1.07 sec	10598 cent
4096	0.01 /x	4.10 fi	49.15 fi	0.02 sec	8.40 sec	101214 cent
8192	0.01 \i	8.19 m	106.50 m	0.07 sec	1.15 min	102447 cent
16384	0.01 fi	16.38 p	229.38 /x	0.27 sec	1.22 hrs	104913 cent
32768	0.02 ix	32.77 fi	491.52 /x	1.07 sec	9.77 hrs	109845 cent
65536	0.02 /x	65.54 /x	1048.6 /x	0.07 min	3.3 days	1019709 cent
131072	0.02 p	131.07 ft	2228.2 fi	0.29 min	26 days	103943S cent
262144	0.02 it	262,14 /x	4718.6 /u	1.15 min	7 mnths	1078894 cent
524288	0.02 /x	524,29 /x	9961.5 //	4.58 min	4.6 years	10157808 cent
1048576	0.02 fi	1048.60 fi	20972 fi	18.3 min	37 years	10315634 cent
Table 1.1   Running times for different sizes of input,  "nsec'1 stands for nanoseconds, ufi" is one microsecond and "cent" stands for centuries.
M. H, Alsuwaiyel: Algorithms, Design Techniques and Analysis.
Složitost řadicích algoritmů
n - délka vstupní posloupnosti
počet operací
jednoduché algoritmy složitější algoritmy
0{n2) 0(nlog(n))
41/55
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, a = random_list() print(a) sort(a) print(a)
insert_sort, select_sort]
42/55
Vyhledávání a řazení v Pythonu
• x in alist - test prí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
43/55
Různé způsoby razení
s = ["prase", "Kos", "ovoce", "Pes", "koza",
"kokos"]
"ovce"
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")))
44/55
proxy values
		r aa	aa'		rbbT
len y			\   \ \		
3		4		1	2
Sort the original list using the proxy values.
TbbT TcccT TaaaaT
https://developers.google.com/edu/python/sorting
45/55
Razení v Pythonu: poznámky
ukázky sorted:
• reverse, key - pojmenované argumenty o 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
46/55
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
47/55
nikátnŕ prvky, nejčastější prvek
• máme seznam prvků, např. výsledky dotazníku (obl 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í
Unikátní prvky
def unique(alist):
# pozor, rozdílné chování od alist.sort()! alist = sorted(alist) result = []
for i in range(len(alist)):
if i == 0 or alist [i-1]   != alist [i]: result.append(alist [i]) return result
48/55
Unikátní prvky
elegantnější řešení za využití datového typu množina
def unique(alist):
return list(set(alist))
49/55
Nejčastější prvek pomocí řazení
def most_common(alist): alist = sorted(alist) max_value, max_count = None, 0 current_value, current_count = None, 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
Nejčastější prvek sofistikovaněji
def most_common(alist):
return max(alist, key=alist.count)
Stack Overflow diskuze:
http: //stackoverf low. com/questions/ 1518522/python-most- common- element- in-a-list
51/55
Pripomenutí: Největší presmyčkové skupiny
Vstup: seznam českých slov, např.
https://wiki.korpus.cz/doku.php/seznamy:
srovnavaci_seznamy
(přes 300 tisíc slovních tvarů)
Výstup: největší množina slov, které jsou vzájemnou přes myč kou
vlasti, slavit, vstali, stavil, svitla, svalit
vynikal, vanilky, vynikla, navykli, vnikaly, viklany
kotle, loket, kotel, lokte, teklo, otekl
(8 řádků kódu v Pythonu, výpočet pod 1 sekundu)
• přesmyčky = slova poskládaná ze stejných písmen
• úkol: rozpoznat, zda dvě slova jsou přesmyčky
• vstup: dva řetězce
o příklady:
• odsun, dusno —> True
• kostel, les Falše
• houslista, souhlasit True
• ovoce, ovace Falše
• seřadíme písmena obou slov
• přesmyčky <^> po seřazení identické
• implementace za využití sorted přímočará
def anagram(wordl, word2):
return sorted(wordl) == sorted(word2)
54/55
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=f ldnocPQXDQ
• Jaká je základní myšlenka algoritmu pro binární vyhledávání?
• Jaká je základní myšlenka následujících řadicích algoritmů: bublinkové řazení, řazení vkládáním, řazení výběrem? Ilustrujte algoritmus na konkrétním vstupu.
• Co znamená pojem „složitost algoritmu"? Jaká je složitost algoritmů pro řazení a vyhledávání?
9 Python nabízí „vestavěnou" podporu pro řazení. Jak se používá?
• Uveďte příklady problémů, pro jejichž řešení využijeme řazení. Zkuste vymyslet vlastní příklady (nad rámec těch uvedených na přednášce).
< [S? ► < i ► < ± >   i •o^o
56/55
• vyhledávání: půlení intervalu
• řadicí algoritmy:
o jednoduché (kvadratické): bublinkové, výběrem, vkládáním
• složitější (r? • log(r?), rekurzivní): quick sort, slučování
• praktické použití řazení
• příklady