IB113 Radek Pelánek
2019
Dnešní prednáška
• práce se soubory - rychlý úvod
• použití datových struktur na praktických příkladech
• interakce volby dat a algoritmu
• vnořené datové struktury: seznam seznamů, slovník indexovaný dvojicí, slovník slovníků...
Proč?
• vstupní data
• uložení výstupu programu
• zachování „stavu" programu mezi jednotlivými běhy větší projekty: databáze
základní postup:
• otevření souboru
• práce se souborem (čtení / zápis)
• zavření souboru
4/56
Práce se soubory: otevření, uzavření
• f = open(filename, mode)
• jméno souboru: řetězec
• způsob otevření:
• ctení ("r")
• zápis ("w") - přepíše soubor, pokud není, vytvoří jej
• přidání na konec ("a")
9 další možnosti: čtení i zápis, binární režim
• uzavření: f .closeO
5/56
Práce se soubory: čtení, zápis
• f . write(text) - zapíše řetězec do souboru
• neukončuje řádky, je třeba explicitně použít ; \n;
• f .readlineO - přečte jeden řádek
• f . readlines () - přečte všechny řádky, vrací seznam
řádků
• f .read(count) - přečte daný počet znaků
• f. read() - přečte celý soubor, vrací řetězec
• f. tell() - aktuální pozice v souboru
• f . seek(position) - přesun pozice v souboru
Práce se soubory: iterování po rá
deich
for line in f.readlines() print(line)
Alternativní způsob:
for line in my_file: print(line)
def word_freq_file(filename): f = open(filename) text = 1111
for line in f.readlines():
text += line output_word_freq(text)       # -> previous lecture f. closeO
word_f req_f ile (Mdevatero_pohadek. txt11)
Frekvence slov v souboru: úkol
Upravte výpis, aby vypisoval nejčastější slova zadané minimání délky.
a	2426	jsem	287
se	1231	jako	284
na	792	když	281
to	781	řekl	251
v	468	nebo	120
ze	467	jeste	110
je	446	pane	109
si	401	toho	91
tak	384	povídá	83
do	365	král	80
race se soubory: with
Speciální blok with
• není třeba soubor zavírat (uzavře se automaticky po ukončení bloku)
• souvislost s výjimkami
with open(M/tmp/my_file", MrM) as my_file: lines = my_file.readlines()
print(lines)
Zápis do souboru
Přímočará realizace cenzury dlouhých slov:
def censorship(filename, limit=5): f_in = open(filename) f_out = open(Mcensor_M+filename, for line in f_in: out_line = 1111 for word in line.split(): if len(word) < limit:
out_line += word + else:
out.line += MXXX 11 f_out.write(out_line+M\nM) f _in. closeO f_out.close()
Ukázka vstupu a výstupu
report.txt:
Climate models project robust 7 differences in regional climate characteristics between present-day and global warming of 1.5 degree C, and between 1.5 degree C and 2 degree C. These differences include increases in: mean temperature in most land and ocean regions (high confidence), hot extremes in most inhabited regions (high confidence), heavy precipitation in several regions (medium confidence), and the probability of drought and precipitation deficits in some regions (medium confidence).
censor_report.txt:
XXX XXX XXX XXX 7 XXX in XXX XXX
XXX XXX XXX and XXX XXX of 1.5 XXX C,
and XXX 1.5 XXX C and 2 XXX C. XXX XXX XXX
XXX in: mean XXX in most land and XXX XXX XXX
XXX hot XXX in most XXX XXX XXX XXX
XXX XXX in XXX XXX XXX XXX and the
XXX of XXX and XXX XXX in some XXX XXX
XXX
Námět na cvičení: zachování interpunkce (tečky, čárky, závorky).
12/56
vstup (v souboru): mřížka písmen + seznam slov k vyhledání
avelu elsok skapr teriz unped
pes
vlk
lev
prase
kos
kapr
13/56
Načtení ze souboru
def read_data(filename=Mosmismerka.txt"): f = open(filename) grid = [] words = [] reading_grid = True
for line in f.readlines():
line = line.stripO
if reading_grid: if line[0] ==
reading_grid = False
else:
grid.append(line)
else:
words.append(line)
f. closeO
return grid, words
14/56
Testování přítomnosti slova
• pro každou pozici a směr vyzkoušíme, zda se slovo vyskytuje
• jak zapsat elegantně?
15/56
Testování přítomnosti slova
DIRS = [(0, 1),  (1, 0),  (0, -1),  (-1, 0),
(1, 1),  (1, -1),  (-1, 1),  (-1, -1)]
def is_inside_grid(grid, x, y): return x >= 0 and y >= 0 and\
y < len(grid) and x < len(grid[y])
def test_word(grid, word, x, y, direction): for i in range(len(word)):
x2 = x + i*DIRS[direction][0] y2 = y + i*DIRS[direction][1] if not is_inside_grid(grid, x2, y2) grid[y2] [x2]   != word[i] : return False return True
Prohledání všech pozic a směrů
def search_word(grid, word): for y in range(len(grid)):
for x in range(len(grid [y])): for d in range(len(DIRS)):
if test_word(grid, word, x, y, d): highlight_word(grid, word, x, y, d) return True return False
17/56
def highlight_word(grid, word, x, y, direction): output_grid = [list(line) for line in grid] for i in range(len(word)):
x2 = x + i*DIRS[direction] [0]
y2 = y + i*DIRS[direction] [1]
output_grid [y2][x2] = word[i].upper() for y in range(len(output_grid)):
print("".join(output_grid[y]))
Pozn. Převod ze seznamu řetězců na seznam seznamů (důvod (ne)měnitelnost).
Matrix: 2 Pupendo: 3 Titanic: 2 Matrix: 3 Titanic: 4 Kolja: 4 Rocky: 1 Titanic: 3
• • •
výpis filmů: počet hodnocení, průměrné hodnocení
Pozn. Netflix prize, predikce hodnocení, 1 milion dolarů
•<□► < g ► < ^ ► < ^ ►    1    ^0 0,0
19/56
slovník:
• klíč: název filmu
• hodnota: seznam hodnocení
{'Matrix1:  [2, 3, 1, 3], 'Pupendo1:  [3], 'Titanic':  [2, 4, 3, 5], 'Kolja' :  [4, 4] , 'Rocky':   [1, 2, 2]}
Filmy: Načtení dat
def read_ratings(filename=Mfilmy.txt"): f = open(filename) ratings = {}
for line in f.readlines():
movie, rating = line. stripO . split ("
if movie not in ratings: ratings [movie] = []
ratings[movie].append(int(rating)) f. closeO return ratings
")
21/56
Filmy: přímočarý výpis
def print.ratings(ratings): for movie in ratings:
count = len(ratings[movie])
avg = sum(ratings[movie]) / count
print(movie, count, avg, sep=M\tM)
22/56
Filmy: řazený výpis
def print.ratings(ratings):
table_data = []
for movie in ratings:
count = len(ratings [movie])
avg = sum(ratings[movie]) / count
table_data.append((avg, count, movie))
table_data.sort()
for avg, count, movie in table_data:
print(movie, count, round(avg, 2), sep=M\tM)
•<□►   4 ^ t   <  -Ž  ►   4  S ►
23/56
24/56
[1, 2, 3] [(1, 2, 3)] [(1, 2), 3]
25/56
data = {"a"
"c" "x"
data["d"] = data["c"] =
[1, 3, 7, 12],
[2, 5],
[19, 2, 4]} [1, 2] [6, 7]
3     >T) o 26/56
dl = {"a": 5, "c": "R2D2"}
d2 = {"b": 8, "a": 7, "B": "C3P0"}
s = [dl, d2]
t = "BB8"
< □ ►  4 ^ t  < -ž ►  < s ►
27/56
board -
{(3,
(1, (2, (3,
0, 2, 4, 0,
1)
2)
3) 2)
"X", "0", "X", "0"}
28/56
Číselné bludiště
jednoduchá logická úloha
Ilustrace pojmů a postupů:
• návrh algoritmu
• volba datových struktur
• seznam seznamu
• slovník
• fronta
• načítání ze souboru
• objekty
29/56
Číselné bludiště
levý horní roh     pravý dolní roh
skoky vertikálně a horizontálně, číslo = délka skoku
	4	4	3	3		3	3	1	3	2		4	2	1	2	3
						1	1	2	1	3		1	2	2	2	3
						1	3	1	2	4		1	4	4	3	3
2	2	3	2	i]		4	3	4	1	4		3	4	3	1	4
1	4	4	4			4	1	4	4	lír		3	2	3	4	★
K vyzkoušení: www.umimematiku.cz/skakacka
30/56
• nej kratší cesta
• vzhledem k počtu skoků
• vzhledem k celkové délce cesty
• kontrola jednoznačnosti nejkratšího řešení
• generovaní „co nejtěžšího" zadaní
31/56
Reprezentace bludiště
Jak budeme v programu reprezentovat bludiště?
2	4	4	3	3
2	3	3	2	3
3	2	3	1	3
2	2	3	2	1
1	4	4	4	
zadáni 5
24433 23323 32313 22321 14440
txt
32/56
„klasická" reprezentace - dvojrozměrné pole (seznam seznamů v Pythonu)
maze[x][y] = number
[[2, 2, 3, 2, 1], [4, 3, 2, 2, 4], [4, 3, 3, 3, 4], [3, 2, 1, 2, 4], [3, 3, 3, 1, 0]]
Poznámka: maze[x] [y] nebo maze[y] [x]? (častý zdroj chyb: nekonzistence)
2	4	4	3	3
2	3	3	2	3
3	2	3	1	3
2	2	3	2	1
1	4	4	4	
•<□►    4 ^  t   <   -ž   ►    <  -Š ►
33/56
Načítání ze souboru
def read_maze(filename=Minput.txt"): f = open(filename) n = int(f readlineO) maze = [[0 for y in range(n)]
for x in range(n)] for y in range(n):
line = f .readlineO for x in range(n):
maze [x] [y] = int(line [x]) f. closeO return maze
34/56
Jak najít řešení?
2 4		4	3 3	
2 3		3	2 3	
3 2		3	13	
2	2	3	2	1
1	4	4	4	★
J_I
35/56
speciální případ obecného „prohledávání do šířky":
• systematicky zkoušíme všechny následníky
• pamatujeme si, kde už jsme byli
• pro každé pole si pamatujeme předchůdce (rekonstrukce cesty)
2 4		4	3	3	2		4 4		I3	3	2 4 4			I3	3
2	3	3	2	3		2	3	3	2	3	2	3	3	2	3
3	2	3	1	3		3	2	3	1	3	i	2	3	1	3
2	2	3	2	1		2	2	3	2	1	2	2	3	2	1
1	4	4	4			1	4	4	4		1	4	4	4	
2	4	4	3	3	2 4		4 í	3 3
2	3	3	2	3	2	3	3 í	2 3
■	2	3	1	3	i	2		|3
2	2	3	2	1	2	2	3 í	l 1
1	4	4	4	*	1	4	4 *	* *
37/56
co si potřebujeme pamatovat:
• fronta polí, které musíme prozkoumat (světle zelená pole)
• množina polí, která už jsme navštívili (tmavě zelená pole)
• informace o předchůdcích (světle modré šipky)
optimalizace: podle informace o předchůdcích poznáme, kde už jsme byli
•<□►   4 ^ t   <  -ž  ►   <  -š ►
38/56
Zápis v Pythonu - přímočaré řešení
def solve(n, maze): start = (0, 0) queue = deque([start]) pred = [[(-1, -1) for x in range(n)] for y in range(n)]
while len(queue) > 0:
(x, y) = queue.popleft() if maze [x] [y] == 0:
print_solution((x, y), pred)
break k = maze [x] [y]
if x+k < n and pred[x+k][y] == (-1, -1):
queue.append((x+k, y))
pred [x+k] [y] = (x, y) if x-k >= 0 and pred[x-k] [y] == (-1, -1):
queue.append((x-k, y))
pred [x-k][y] = (x, y) if y+k < n and pred[x][y+k] == (-1, -1):
queue.append((x, y+k))
pred[x] [y+k] = (x, y) if y-k >= 0 and pred[x][y-k] == (-1, -1):
queue.append((x, y-k))
pred[x] [y-k] = (x, y)
39/56
9 příkaz break - opuštění cyklu • využití zkráceného vyhodnocování
< [fpi ►  < -ž ►  < -E ►      -š     O Q, O
40/56
Alternativní reprezentace: slovník
slovník indexovaný dvojicí
souřadnice (x, y) —>► číslo na dané souřadnici
maze[(x, y)] = number
{(i,
(3,
(1, (2,
2) 0)
3)
4) }
2, (3, 2)
3, (2, 2) 2, (2, 3)
4, (4, 2)
1, (0, 0)
3, (2, 1)
3, (1, 4)
3, (0, 3)
2,
3,
4, 2,
2	4	4	3	3
2	3	3	2	3
3	2	3	1	3
2	2	3	2	1
1	4	4	4	*
41/56
U n-tic většinou nemusíme psát závorky:
• a, b = b, a
místo
(a, b) = (b, a)
• maze[x, y] místo
maze[(x, y)]
42/56
Slovník vs seznam seznamů
Pozor na rozdíl!
• maze[x] [y] - seznam seznamů
• maze [x, y] - slovník indexovaný dvojicí
43/56
Další vylepšení
Zobecnění repetitivního kódu
„copy&paste" kód pro 4 směry f or cyklus přes 4 směry
Předchůdci
• pamatujeme si rovnou celou cestu (*)
• také slovník
(*) to je sice „plýtvání pamětí", ale vzhledem k velikosti zadání nás to vůbec nemusí trápit
44/56
Upravený kód
def solve(maze): start = (0, 0) queue = deque([start]) pred = {}
pred[start] = [start] while len(queue) > 0:
(x, y) = queue popleftO if maze[x, y] ==0:
print(pred[x,y] ) for (dx, dy) in [(-150)5  (150)5 (0,-1), newx = x + dx * maze[x, y] newy = y + dy * maze[x, y] if (newx, newy) in maze and \ not (newx, newy) in pred: queue.append((newx, newy)) pred [newx, newy] = pred[x^j^L +^
Někdy jsou závorky důležité:
• s = [1, 2] - seznam obsahující dva prvky
s = [(1, 2)] - seznam obsahující jeden prvek (dvojici)
• s.append((l, 2)) - přidávám dvojici s.appendd, 2) - volám append se dvěma argumenty (chyba)
•<□►   4 ^ t   <  -ž  ►   <  -š ►
46/56
Piškvorky
herní plán:
• plán omezené velikosti
• neomezený plán
„chytrý" algoritmus?
47/56
• globální proměnné
• draw_board()
• makejnove(x, y)
• předávání funkcím
• draw_board(board, size)
• make-move (board, size, x, y, player)
• objektová reprezentace (více později)
o game. drawJboard ()
• game .make_move(x, y)
48/56
mplementace strategií: nevhodný styl
def strategy(num):
if num ==0: # random strategy x = randintd, N) y = randintd, N) elif num == 1: # first empty for x in range(N):
for y in range(N): s = board[x][y] # and so on elif num ==2: # clever # and so on.. .
49/56
Jaká datová struktura pro reprezentaci stavu?
• Člověče, nezlob se!
• Želví závody
• Pexeso
50/56
Člověče, nezlob se!
v
Želví závody
52/56
Pexeso - simulace paměti
• simulace hry pexeso
o hráči s různě dokonalou pamětí:
• prázdná paměť (náhodná hra)
• dokonalá paměť
• omezená paměť - „buffer" velikosti k
• pravděpodobnost výhry pro jednotlivé hráče
• reprezentace stavu hry (kartiček)?
• reprezentace paměti?
• Jakým způsobem pracujeme se soubory (otevření, čtení, zápis, uzavření)?
• Pomocí jakých příkazů projdeme všechny řádky textového souboru? V jakém pořadí je musíme použít?
• Jakými způsoby můžeme v Pythonu reprezentovat dvourozměrnou mřížku?
• Uveďte příklady použití následujících vnořených datových struktur: slovník seznamů, seznam seznamů.
• Ve slovníku f req máme napočítané frekvence slov v zadaném textu. Jakým způsobem vypíšeme slova seřazená podle těchto frekvencí?
•<□►   4 ^ t   <  -ž  ►   <  -š ►
54/56
Doporučené procvičování
https://www.umimeprogramovat.cz/porozumeni ^> sada „Slovníky"
https://www.umimeprogramovat.cz/rozhodovacka ^> sada „Přehled datových typů"
< [S? ► < 1 ► < ^ ►    1 •o^o
55/56
a načtení dat ze souboru
• volba reprezentace dat
• vnořené datové struktury: seznam řetězců, slovník seznamů, seznam seznamů, slovník indexovaný dvojicí
• algoritmy, řazení výstupu
příště: proměnné, typy, reprezentace v paměti, rekurze ^ „záludnosti"
56/56