IB113 Radek Pelánek
2019
Rozcvička: Co je jiné?
• smrk, lípa, borovice, jedle
• prase, koza, husa, ovce
Odd one out: varianta pro pokročilé
o
Odd one out: varianta pro začátečníky
prase, pes, prase, prase
Odd one out: varianta pro začátečníky
prase, pes, prase, prase
• vstup: seznam
• výstup: prvek, který je v seznamu osamocen
Odd one out: základní řešení
def odd_one_out(alist): for x in alist: count = 0 for y in alist: if x == y:
count += 1 if count == 1: return x return None
zpracování dotazníku, hledání cesty v bludišti, předpověď počasí, úprava obrázků
• Jaká data budu zpracovávat?
• Jaká data budu potřebovat k řešení problému?
• Jaké operace s daty budu chtít provádět?
• Jak rychle budu chtít, aby operace s daty fungovaly?
Oddělení dat a funkcionality
Důležitý princip v mnoha oblastech informatiky
Príklad web
webový portál: oddělení funkcionality, dat a vzhledu
typická realizace:
• funkcionalita - program (Python, PHP...)
• data - databáze (MySQL...)
• vzhled - grafický styl (CSS)
Ukázka nevhodného kódu
if currency == 1 euro 1:
value = amount * 25.72
elif currency == 'dollar': value = amount * 21.90
elif currency == 'rupee': value = amount * 0.34
Reálnější příklad
def print_stats():
•     • •
if success_rate < 0.5: bg_color = "red"
elif success_rate < 0.85 bg_color = "yellow"
else:
bg_color = "green"
def print_stats():
• • •
bg_color = get_color(success_rate,
[0.5, 0.85, 1],
["red", "yellow", "green"])
• • •
Další úpravy:
• parametry jako globální konstanty „vytknuté" na začátek kódu
a použití nějaké standardní „colormap" (tip: viridis)
11/62
Abstraktní datové typy v IB113
• abstraktní datové typy - základní myšlenka
• fronta, zásobník, množina - ilustrace principu abstraktních datových typů, základní povědomí
• slovník - důkladnější probrání a procvičení dnes: rychlý přehled, příště: rozsáhlejší příklady
Abstraktní datové typy
Datový typ
• rozsah hodnot, které patří do daného typu
• operace, které je možno s těmito hodnotami provádět Abstraktní datový typ (ADT)
• rozhraní
• popis operací, které chceme provádět (případně i složitost)
Konkrétní datová struktura
9 implementace
9 přesný popis uložení dat v paměti
• definice funkcí pro práci s těmito daty
Poznámky: hranice není vždy úplně ostrá, rozdíl mezi „formálním" a „praktickým" pojetím ADT; nejednotná terminologie „datový typ", „datová struktura"
Dva pohledy na data
abstraktní, „uživatelský"
o operace, která s daty budu provádět
• co musí operace splňovat, efektivita...
• množina: ulož, najdi, vymaž
• tento předmět
konkrétní, implementační
9 jak jsou data reprezentována v paměti
• jak jsou operace implementovány
• hašovací tabulka, binární vyhledávací strom
• IB002
14/62
Abstraktní pohled na data
Výhody:
• snadný vývoj
o jednodušší přemýšlení o problémech Riziko:
• svádí k ignorování efektivity
• typický příklad: použití in pro vyhledávání v seznamech
Abstraktní datové typy
Nejpoužívanější ADT:
• seznam
• zásobník
• fronta, prioritní fronta
• množina
• slovník (asociativní pole)
16/62
Datový typ seznam: různé varianty
• obsahuje posloupnost prvků
• stejného typu
• různého typu
• přidání prvku
• na začátek
• na konec
• na určené místo
• odebrání prvku
• ze začátku
• z konce
• konkrétní prvek
• test prázdnosti, délky
• případně další operace, napr. přístup pomocí indexu
17/62
eznamy v Pythonu
opakování
• seznamy v Pythonu velmi obecné
• prvky mohou být různých typů
• přístup skrze indexy
• indexování od konce pomocí záporných čísel
• seznamy lze modifikovat na libovolné pozici
a = ['bacon',  'eggs',  'spam', 42]
print (a[l: 3]) # ['eggs', 'spam']
print (a [-2:-4:-1])     # ['spam', 'eggs']
a[-l] = 17 print(a) print(len(a))
eggs ,
eznamy v Pythonu - operace
s = [4, 1, 3] #
s.append(x) #
s.extend(t) #
s.insert(i, x) #
s.remove(x) #
s.pop(i) #
s.popO #
s.index(x) #
s.count(x) #
s.sortO #
s. reverse () #
x in s #
#
seznam
přidá prvek x na konec přidá všechny prvky t na konec přidá prvek x před prvek na pozici i odstraní první prvek rovný x odstraní (a vrátí) prvek na pozici i odstraní (a vrátí) poslední prvek vrátí index prvního prvku rovného x vrátí počet výskytů prvků rovných x seřadí seznam obrátí seznam
test, zda seznam obsahuje x (lineární průchod seznamem!)
19/62
Odd one out: řešení pomocí count
def odd_one_out(alist): for x in alist:
if alist.count(x) = return x return None
= 1
20/62
Generátorová notace pro seznamy
list comprehension specialita Pythonu
s = [x for x in range(1, 7)] print (s) # [1, 2, 3, 4, 5, 6]
s = [2 * x for x in ranged, 7)] print(s) # [2, 4, 6, 8, 10, 12]
s = [(a, b) for a in range(l, 5)
for b in ["A", "B"]] print (s) # [(1,   'A'),   (1,   'B'),  (2, 'A'),
#   (2,   'B'), ...
21/62
Odd one out: generátorová notace
def odd_one_out(alist):
return [x for x in alist
if alist.count(x) == 1]
Pozn. Mírně odlišné chování od předchozích ukázek - vrací seznam všech osamocených.
22/62
Vnořené seznamy
• prvky seznamů mohou být opět seznamy
• použití: vícerozměrná data (např. matice)
mat = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]] print(mat [1] [2]) #6
def null_matrix(m, n):
return [[0 for col in range(n)] for row in range(m)]
Pozn. efektivnější způsob práce s maticemi: knihovna numpy
23/62
24/62
Vnořené seznamy: Násobení matic
def matrix_mult(matL, matR): rows = len(matL) cols = len(matR[0]) common = len(matR) result = null_matrix(rows, cols) for i in range(rows): for j in range(cols): for k in range(common):
result [i] [j] += matL[i] [k] * matR[k] [j] return result
25/62
Interpretace dvojitého indexování
• „data [i] [j]11
• data indexuji „dvojicí čísel" 9 intuitivní
• neodpovídá implementaci v Pythonu
• „data [i]   [j]11
• indexuji prvním číslem, dostanu seznam
• tento seznam indexuji druhým číslem
• speciální případ obecného postupu
Pozn. V Pythonu můžeme mít i data[i, j] - to však není seznam, ale slovník indexovaný dvojicí. Více později.
26/62
Interpretace složitějšího indexování
čteme „zleva", resp. „z vnitřku":
• mat [2] [: :-l] [0]
• sorted(mat [1]) [2]
• (mat [0] *5) [7]
Čistě ilustrativní příklady, rozhodně ne ukázky pěkného kódu.
27/62
Fronta a zásobník
fronta a zásobník - „seznamy s omezenými možnostmi
11
Proč používat něco omezeného?
28/62
fronta a zásobník - „seznamy s omezenými možnostmi"
Proč používat něco omezeného?
• vyšší efektivita implementace
• citelnější a cistejsi kod
• „sebe-kontrola"
Sebe-kontrola, historická poznámka: GOTO; xkcd.com/292/
I COULĎRKTRUCIURE THE FTO&RMS FlW		EHSCREWGOODFfiňcnCE. HOUBADCAM IT8E?		
OR IJSEľ ONE LiTTIL 'GOID1 INSTEľAD.		\    goto i^*'n_äu!)3;		
			n	
28/62
• LIFO = Last In First Out
• operace
• push (vložení)
• pop (odstranění) top (náhled na horní prvek) empty (test prázdnosti)
mnohá použití
• procházení grafů
• analýza syntaxe
• vyhodnocování výrazů o rekurze
9 9
29/62
implementace pomocí seznamu
• místo push máme append
• místo top máme [-1]
def push(stack, element): stack.append(element)
def pop(stack):
return stack.pop()
def top(stack):
return stack[-1]
def empty(stack):
return stack.empty()
< □ ► < g ► < B ► < ^ ►     1    -0 0,0
30/62
Příklad aplikace: postfixová notace
• infixová notace
• operátory mezi operandy
• (3 + 7) * 9
• je třeba používat závorky
• prefixová notace (polská notace)
9 operátory před operandy
• * + 3 7 9
• nepotřebujeme závorky
• postfixová notace (reverzní polská notace, RPN)
• operátory za operandy
• 37 + 9*
• nepotřebujeme závorky
využití zásobníku: převod mezi notacemi, vyhodnocení postfixová notace
Vyhodnocení postfixové notace
def eval_postfix(line): stack = []
for token in line.split():
if token == 1 * 1: b = pop(stack) a = pop(stack) push(stack, a * b)
elif token == 1+1: b = pop(stack) a = pop(stack) push(stack, a + b)
else:
push(stack, int(token)) return top(stack)
32/62
vstup			akce	zásobník	
7 4 7	+	* 8 +	push		
4 7 +	*	8 +	push	7	
7 + *	8	+	push	7	4
+ * 8	+		+	7	4 7
* 8 +			*	7	11
8 +			push	77	
+			+	77	8
				85	
33/62
• FIFO = First In First Out
• operace
• enqueue (vložení)
• dequeue (odstranění)
• front (náhled na přední prvek)
• empty (test prázdnosti)
• použití
• zpracovávání příchozích požadavků
• procházení grafu do šířky
• pokročilejší varianta: prioritní fronta
•<□►   4 ^ t   <  -ž  ►   <  -š ►
34/62
• implementace pomocí seznamů snadná, ale neefektivní
• přidávání a odebírání na začátku seznamu vyžaduje přesun
• pomalé pro dlouhé fronty
• použití knihovny collections
• datový typ deque (oboustranná fronta)
• vložení do fronty pomocí append
• odebrání z fronty pomocí poplef t
• přední prvek fronty je [0]
35/62
Fronta: ukázka deque
from collections import deque
q = deque(["Erie",  "John", "Michael"])
q.append("Terry")     # Terry arrives
q.append("Graham")    # Graham arrives
q.popleftO        # Eric leaves
q.popleftO        # John leaves
print(q) # deque(['Michael', 'Terry',
'Graham']
36/62
Datový typ množina
• neuspořádaná kolekce dat bez vícenásobných prvků
• operace
• insert (vložení)
• find (vyhledání prvku, test přítomnosti)
• remove (odstranění)
• použití
• grafové algoritmy (označení navštívených vrcholů)
• rychlé vyhledávání
• výpis unikátních slov
•<□►   4 ^ t   <  -Ž  ►   4 S ►
39/62
Množina v Pythonu
set(alist)	#	vytvoří množinu ze seznamu
len(s)	#	počet prvků množiny s
s. add(x)	#	přidání prvku do množiny
s .remove(x)	#	odebrání prvku z množiny
x in s	#	test, zda množina obsahuje x
sl <= s2	#	test, zda je sl podmnožinou s2
sl.union(s2)	#	sjednocení množin sl a s2
sl 1 s2	#	— totéž —
sl.intersection(s2)	#	průnik množin sl a s2
sl & s2	#	— totéž —
sl.difference(s2)	#	rozdíl množin sl a sl
sl - s2	#	— totéž —
sl.symmetric_diference(s2) # symetrický rozdíl množin		
sl ~ s2		# — totéž —
40/62
Množina v Pythonu
basket = [1 apple 1, 1 orange 1, 1 apple 1, 1 orange 1, 1 banana fruit = set(basket)
print(fruit) # {'orange ',   'apple', 'banana'}
print(1 orange 1 in fruit)    # True print(1 tomato 1 in fruit)    # False
a = set("abracadabra") b = set("engineering")
print(a)	#	{'a	9	'r',			'd'}
print(b)	#	{'i	9	'r',		'9',	'n'}
print(a I b)	#	{'a	9	'C,		'e',	'ď,
print(a & b)	#	{'r	'}				
print(a - b)	#	{'a	9	'C,		'd'}	
print(a " b)	#	{'a	9	'C,	'b1,	'e',	'ď,
'9'
'9'
'i 1
'i 1
n
n
41/62
Aplikace množiny
def unique(alist):
return list(set(alist))
def odd_one_out(alist):
return set(alist)-set([x for x in alist
if alist.count(x) > 1])
42/62
Datový typ slovník
dictionary, map, asociativní pole
• neuspořádaná množina dvojic (klíč, hodnota)
• klíče jsou unikátní
• operace jako u množiny (insert, find, delete)
• přístup k hodnotě pomocí klíče (indexování pomocí [])
• klíče jsou neměnné, ale hodnoty se smí měnit 9 příklady použití
• překlad UČO na jméno, jméno na tel. číslo
• počet výskytů slov v textu
• „cache" výsledků náročných výpočtů
Slovník vs. seznam
zjednodušené srovnání:
• indexování (klíče):
• seznam: čísla
• slovník: cokoliv (neměnitelného)
• pořadí klíčů:
• seznam: fixně dáno
• slovník: neřazeno
ovnfk v Pythonu
phone = {"Buffy": 5550101, "Xander": 5550168} phone["Dawn"] = 5550193 print(phone)
# {'Xander': 5550168, 'Dawn': 5550193, 'Buffy' print(phone["Xander"])
# 5550168
del phone["Buffy"] print(phone)
# {'Xander': 5550168,   'Dawn': 5550193} print(phone.keys())
# dict_keys(['Xander', 'Dawn']) print("Dawn" in phone)
# True
ovnřk v Pythonu
užitečné funkce pro slovníky
d.keys() # vrátí seznam klíčů
d.values() # vrátí seznam hodnot
d.items() # vrátí seznam záznamů (dvojic)
d.get(key, default)    # pokud existuje klíč key, vrátí
# jeho hodnotu, jinak vrátí
# hodnotu default d.get(key)                   # jako předtím,
# jen default je ted; None
46/62
Slovník v Pythonu
.items() - použití např. pro kompletní výpis (nikoliv vyhledávání!)
for name, num in phone.items():
print (name + 111 s number is", num)
# Xander's number is 5550168
# Dawn's number is 5550193
47/62
Odd one out: řešení se slovníkem
def odd_one_out(alist): count = {} for x in alist:
count [x] = count.get(x, 0) + 1 for x in count:
if count [x] == 1:
return x
return None
48/62
Odd one out: řešení se slovníkem
def odd_one_out(alist): count = {} for x in alist:
count [x] = count.get(x, 0) + 1 return min(count.keys(), key=count.get)
Pozn. Odlišné chování od ostatních ukázek v případě, kdy není splněn předpoklad unikátního osamoceného prvku.
49/62
Prevod do morseovky
připomenutí: dřívější řešení přes seznamy
morse = [".-", "-.."] #e
def to_morse(text): result = 1111
for i in range(len(text)):
if ord(11A11) <= ord(text[i]) <= ord c = ord(text[i]) - ord ("A") result += morse [c] + "I" return result
Prevod do morseovky
morse = {"A": "B": "C":  "-.-."} # etc.
def to_morse(text): result = 1111 for c in text:
result += morse.get(c, "?") + "I" return result
# advanced version def to_morse(text):
return(M|M.join(list(map(lambda x: morse.get(x, "?"),
text))))
51/62
def encrypt(text, subst): result = 1,11 for c in text:
if c in subst:
result += subst [c] else:
result += c return result
my.cipher = {"A":  "Q", "B":  "W", "C":  "E"} # etc.
print(encrypt("BAC", my_cipher)) # WQE
52/62
text = """It is a period of civil war. Rebel spaceships, striking [...] restore freedom to the galaxy """
output_word_freq(text)
the 7
to 4
rebel 2
plans 2
of 2
her 2
53/62
Frekvenční analýza slov
def is_word_char(char):
return char not in ' ! M#$°/0&\ ' 0*+,-./:;<=>?@ [\\] *V{
def word_freq(text):
text = 1111.join(filter(is_word_char, text)) text = text.lower() word_list = text.split() freq = {}
for word in word_list:
freq[word] = freq.get(word, 0) + 1 return freq
54/62
def output_word_freq_simple(text): freq = word_freq(text) for word in freq:
print(word,  "\t", freq[word])
Jak udělat výpis seřazený podle četnosti a vypisovat pouze nejčetnější slova?
55/62
v
Razení výstupu: pomocný seznam dvoji
def output_word_freq(text, topN=10): freq = word_freq(text)
tmp = [(freq[word], word) for word in freq] tmp.sort(reverse=True) for count, word in tmp[:topN]: print(word,  "\t", count)
56/62
Razení výstupu: využití lambda funkce
def output_word_freq(text, topN=10): freq = word_freq(text)
words = sorted(freq, key=lambda x: -freq[x]) for word in words [:topN]:
print(word,  "\t", freq[word])
<  □  ►   4 ^ t   <  -Ž  ►   < -E ►
57/62
ndexování slovníku
slovník můžeme indexovat „neměnitelnými" datovými typy
v ' I
• cisla
• řetězce
• dvojice
• n-tice (neměnná forma seznamu)
58/62
data = {}
data[(l, 5)] = "white king" data[2, 6] = "black rookM
print(data.keys()) #dict_keys([(1, 5),   (2, 6)])
Můžeme vynechávat kulaté závorky u n-tice.
Pozor na rozdíl:
• data[x] [y] - seznam seznamů
• data[x, y] - slovník indexovaný dvojicí
59/62
• Co znamenají pojmy abstraktní datový typ a konkrétní datová struktura?
• Jaké operace podporují datové typy fronta a zásobník? Jaký je mezi nimi rozdíl? K čemu je využíváme?
• K čemu slouží datový typ slovník? Jak používáme slovník v Pythonu?
• Jaký je rozdíl mezi seznamem a n-ticí?
• Co to je postfixová notace? Za využití které datové struktury ji vyhodnocujeme?
• Jakým způsobem můžeme reprezentovat dvourozměrnou mřížku (například šachovnici)?
• Jak můžeme vypsat všechny unikátní prvky v seznamu? Uveďte alespoň tři různá řešení (nápověda: množina, slovník, count()).
• Jaký je rozdíl mezi datafxlfyl a datafx,yl?
J  J LJL./J L  < -y >   <      , I >oc\o
60/62
https://www.umimeprogramovat.cz/rozhodovacka https://www.umimeprogramovat.cz/vystup-programu
^> sada „Slovníky"
61/62
• datové typy: abstraktní vs. konkrétní
• seznam, vnořený seznam („vícerozměrné pole")
• zásobník, fronta
• množina
• slovník
příště: rekapitulace, řešené (rozsáhlejší) příklady
•<□►   4 ^ t   <  -ž  ►   <  -š ►
62/62