Vyhledávání, řazení, složitost
IB111 Úvod do programování skrze Python
2015
1 / 56
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?
2 / 56
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ů?
3 / 56
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
4 / 56
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?
Kolik předem formulovaných otázek potřebujete?
Mezi kolika čísly jste schopni odhalit skryté číslo na
K otázek?
5 / 56
Vyhledávání: řešení
„dynamické otázky : půlení intervalu
„předem formulované otázky : dotazy na bity v bitovém
zápisu (stejně jako u studen)
N čísel: potřebujeme log2 N otázek
K otázek: rozlišíme mezi 2K
čísly
6 / 56
Připomenutí: logaritmus
x = by
⇔ y = logb(x)
log10(1000) = 3
log2(16) = 4
log2(1024) = 10
logb(xy) = logb(x) + logb(y)
http://www.khanacademy.org/math/algebra/logarithms
http://khanovaskola.cz/logaritmy/uvod-do-logaritmu
7 / 56
Logaritmus – graf
8 / 56
Logaritmus – test
log3(81) = ?
log2(2) = ?
log5(1) = ?
log10(0.1) = ?
log2(
√
2) = ?
log0.5(4) = ?
9 / 56
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
10 / 56
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 / 56
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))
12 / 56
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
13 / 56
Výpočet odmocniny: binární půlení
horní odhadspodní odhad
0 1 20.5 1.5
0 1 20.5 1.5
0 1 20.5 1.5
0 1 20.5 1.5
0 1 20.5 1.5
střed
14 / 56
Výpočet odmocniny: binární půlení
def odmocnina(x, presnost = 0.01):
horni_odhad = x
spodni_odhad = 0
stred = (horni_odhad + spodni_odhad) / 2.0
while abs(stred**2 - x) > presnost:
if stred**2 > x:
horni_odhad = stred
if stred**2 < x:
spodni_odhad = stred
stred = (horni_odhad + spodni_odhad) / 2.0
return stred
15 / 56
Vyhledávání: program
def binarni_vyhledavani(hodnota, seznam):
spodni_mez = 0
horni_mez = len(seznam) - 1
while spodni_mez <= horni_mez:
stred = (spodni_mez + horni_mez) / 2
if seznam[stred] == hodnota:
return True
elif seznam[stred] > hodnota:
horni_mez = stred - 1
else:
spodni_mez = stred + 1
return False
16 / 56
Vyhledávání: rekurzivní varianta
def binarni_vyhledavani(hodnota, seznam,
spodni_mez, horni_mez):
if spodni_mez > horni_mez:
return False
stred = (spodni_mez + horni_mez)/2
if seznam[stred] < hodnota:
return binarni_vyhledavani(hodnota, seznam,
stred+1, horni_mez)
elif seznam[stred] > hodnota:
return binarni_vyhledavani(hodnota, seznam,
spodni_mez, stred-1)
else:
return True
17 / 56
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
18 / 56
Ř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ší
19 / 56
Ř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?
20 / 56
Řadicí algoritmy: komentář
Proč se tím tedy zabýváme?
1 ukázka programů 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
21 / 56
Ř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ě
22 / 56
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í: http://www.youtube.com/watch?v=lyZQPjUT5B4
23 / 56
Ř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
24 / 56
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?
25 / 56
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?
26 / 56
Složitost
n – délka vstupní posloupnosti
počet operací
jednoduché algoritmy O(n2
)
složitější algoritmy O(n log(n))
27 / 56
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ě
28 / 56
Bublinkové řazení: program
def bublinkove_razeni(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 finální pozici
29 / 56
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]
30 / 56
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
31 / 56
Ř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)
32 / 56
Řazení výběrem: program
def razeni_vyberem(a):
for i in range(len(a)):
vybrany = i
for j in range(i+1, len(a)):
if a[j] < a[vybrany]: vybrany = j
tmp = a[i]
a[i] = a[vybrany]
a[vybrany] = tmp
33 / 56
Ř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ří
34 / 56
Řazení vkládáním: program
def razeni_vkladanim(a):
for i in range(1,len(a)):
aktualni = a[i]
j = i
while j > 0 and a[j-1] > aktualni:
a[j] = a[j-1]
j -= 1
a[j] = aktualni
35 / 56
Význam proměnných
proměnná vybrany u řazení výběrem
index vybraného prvku
používáme k indexování, a[vybrany]
proměnná aktualni u řazení vkládáním
hodnota „posunovaného prvky
a[j] = aktualni
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 třeba řetězce
36 / 56
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)
37 / 56
Quick sort
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))
38 / 56
Ř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))
39 / 56
Radix sort
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)
40 / 56
Radix sort
aplikovatelné na (krátká) čí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é)
41 / 56
Radix sort ilustrace
42 / 56
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
)
43 / 56
Ilustrace rozdílů v složitosti
44 / 56
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))
45 / 56
Vyhledávání a řazení v Pythonu
x in seznam – test přítomnosti x v seznamu
seznam.index(x) – pozice x v seznamu
seznam.count(x) – počet výskytů x v seznamu
seznam.sort() – seřadí položky seznamu
sorted(seznam) – 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
46 / 56
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"))
47 / 56
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
48 / 56
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í
48 / 56
Unikátní prvky
def unikatni(seznam):
seznam = sorted(seznam)
# rozdilne chovani od seznam.sort()
vystup = []
for i in range(len(seznam)):
if i == 0 or seznam[i-1] != seznam[i]:
vystup.append(seznam[i])
return vystup
def unikatni(seznam):
return list(set(seznam))
49 / 56
Nejčastější prvek
def nejcastejsi(seznam):
seznam = sorted(seznam)
max_prvek, max_pocet = None, 0
akt_prvek, akt_pocet = None, 0
for prvek in seznam:
if prvek == akt_prvek:
akt_pocet += 1
else:
akt_prvek = prvek
akt_pocet = 1
if akt_pocet > max_pocet:
max_prvek = akt_prvek
max_pocet = akt_pocet
return max_prvek
50 / 56
Nejčastější prvek sofistikovaněji
def nejcastejsi(seznam):
return max(seznam, key=seznam.count)
Stack Overflow diskuze:
http://stackoverflow.com/questions/1518522/python-most-common-element-in-a-list
51 / 56
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
52 / 56
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 presmycky(slovo1, slovo2):
return sorted(slovo1) == sorted(slovo2)
53 / 56
Rozměňování peněz
vstup: částka X
výstup: vyplacení částky pomocí co nejméně mincí
(bankovek)
předpokládejme „klasické hodnoty peněz: 1, 2, 5, 10, 20,
50, 100, . . .
příklady:
29 → 2, 2, 5, 20
401 → 1, 200, 200
54 / 56
Rozměňování peněz
hladový algoritmus: „použij vždy nejvyšší minci, která je
menší než cílová částka
cvičení – naprogramovat
funguje pro klasické hodnoty
nefunguje pro obecný případ – najděte konkrétní příklad
zkuste vymyslet algoritmus pro obecný případ
55 / 56
Shrnutí
vyhledávání: půlení intervalu, rekurze
řadicí algoritmy:
jednoduché (kvadratické): bublinkové, výběrem,
vkládáním
složitější (n · log(n), rekurzivní): quick sort, slučování
příklady
56 / 56