Ako vybrať vhodný spôsob uloženia a spracovania dát?
Po prednáške budete vedieť:
list — Usporiadané prvky, indexovanie a zmena obsahutuple — Usporiadaná skupina hodnôt, ktorá sa nemeníset — Unikátne prvky a rýchle testovanie členstvadict — Vyhľadávanie hodnoty podľa kľúčadeque — Efektívne pridávanie a odoberanie na oboch koncochlist)Zoznam je dynamické pole, ktoré uchováva prvky v poradí.
0.numbers = [10, 20, 30]
numbers.append(40) # pridaj na koniec
numbers.insert(1, 15) # vlož na index 1
del numbers[0] # odstráň podľa indexu
numbers.remove(30) # odstráň prvý výskyt hodnoty 30
print(numbers)remove(value) vyvolá ValueError, ak hodnota v zozname nie je.
tuple)N-tica je usporiadaná kolekcia, ktorú po vytvorení nemožno meniť.
point = (3, 5)
x, y = point
print(x, y)Použite ju napríklad pre súradnice alebo záznam s pevnou skupinou hodnôt.
N-tica s jedným prvkom potrebuje čiarku: single = (7,).
set)Množina uchováva unikátne, hashovateľné prvky. Poradie prvkov nie je definované.
colors = {"modrá", "zelená", "modrá"}
print(colors) # každý prvok sa v množine vyskytuje iba raz
print("zelená" in colors)Vyhľadanie, pridanie a odstránenie majú priemerne O(1); v najhoršom prípade môžu byť pomalšie.
a = {1, 2, 3}
b = {3, 4}
print(a | b) # zjednotenie: {1, 2, 3, 4}
print(a & b) # prienik: {3}
print(a - b) # rozdiel: {1, 2}
print(a ^ b) # symetrický rozdiel: {1, 2, 4}Na bezpečné odstránenie prvku použite discard; remove vyvolá KeyError, ak prvok chýba.
+-------------+
| A | A v B
| +-------|--+
| | A ^ B | |
+-------------+ |
| B |
+----------+def has_duplicates(items):
seen = set()
for item in items:
if item in seen:
return True
seen.add(item)
return False
print(has_duplicates([4, 2, 4])) # TrueKaždú hodnotu kontrolujeme a pridávame priemerne v konštantnom čase, takže celý priechod je priemerne O(n).
dict)Slovník mapuje jedinečné kľúče na hodnoty.
person = {"name": "Anna", "age": 20}
print(person["name"])[] vyvolá KeyError; get umožňuje zadať predvolenú hodnotu.person["age"] = 21
person["city"] = "Bratislava"
for key, value in person.items():
print(key, value)
del person["city"]words = ["a", "b", "a", "c", "b", "a"]
counts = {}
for word in words:
counts[word] = counts.get(word, 0) + 1
print(counts) # {'a': 3, 'b': 2, 'c': 1}dict a set s hashovaním?Python používa hash tabuľky na rýchle vyhľadávanie kľúčov v slovníku a prvkov v množine.
kľúč → hash → miesto v tabuľke → kontrola kľúčaNemenné vstavané hodnoty, ako sú celé čísla, reťazce a vhodné n-tice, možno použiť ako kľúče slovníka. Zoznam a množina hashovateľné nie sú, pretože sa dajú meniť.
lookup = {"Anna": 20, (48.1, 17.1): "Bratislava"}
# lookup[[1, 2]] = "hodnota" # TypeError: zoznam nie je hashovateľnýHash reťazca sa môže meniť medzi spusteniami Pythonu. Nepoužívajte hash() na trvalé identifikátory ani na kryptografické účely.
Počas uloženia v dict alebo set sa hash kľúča nesmie meniť. Inak tabuľka hľadá kľúč na inom mieste, než kde ho pôvodne uložila.
Preto sú napríklad eťazce a celé čísla vhodné kľúče, ale zoznamy nie: zoznam možno meniť a Python ho preto ani nedovolí použiť ako kľúč.
prices = {"jablko": 1.20, "hruška": 1.50}
print(prices["jablko"])
# prices[["jablko"]] = 1.20 # TypeError: zoznam nie je hashovateľnýRovnaké kľúče musia mať rovnaký hash. Opačne to neplatí: rovnaký hash ešte neznamená, že kľúče sú rovnaké.
Hash tabuľka ukladá dvojice kľúč – hodnota do poľa slotov. Hashovacia funkcia prevedie kľúč na číslo a podľa neho sa vyberie priehradka.
kľúč "meno" → hashovacia funkcia → číslo → slot.Vďaka tomu nemusíme pri hľadaní postupne prechádzať všetky uložené dvojice. Slovník (dict) je v Pythone postavený na hash tabuľke; set používa podobný princíp, ale uchováva iba kľúče.
Slot sa vypočíta pomocou hash funkcie:
priehradka = hash(kľúč) % 8Určíme zvyšok po delení počtom slotov.
Pri vyhľadávaní sa pre ten istý kľúč vypočíta rovnaké miesto a skontroluje sa tam uložený kľúč.
kľúč: Anna Miro
hash % velkost: | |
v v
index: 0 1 2 3 4 5 6 7
tabuľka: [ ] [ ] [ ] [Anna] [ ] [ ] [Miro] [ ]Kolízia nastane, keď dva rôzne kľúče vedú k rovnakému miestu v tabuľke. Hash nie je jedinečný identifikátor kľúča.
kľúč: Jana Miro
hash % velkost: \ |
--> v
index: 0 1 2 3 4 5 6 7
tabuľka: [ ] [ ] [ ] [Anna] [ ] [ ] [Miro] [ ]Pri reťazení každá priehradka odkazuje na zoznam položiek.
index 0: —
index 1: ("Eva", 18) → ("Filip", 21)
index 2: ("Jana", 20)
index 3: —Pri otvorenom adresovaní sú všetky položky uložené priamo v poli. Ak je vypočítaná priehradka obsadená, algoritmus skúsi ďalšiu podľa určitého pravidla. Postupnosť skúšaných miest sa nazýva sondovanie.
hash(kľúč) → obsadené miesto → skús ďalšie miesto → nájdi voľné miestoPri vyhľadávaní treba prejsť rovnakú postupnosť miest až po nájdenie kľúča alebo po miesto, ktoré ukazuje, že kľúč v tabuľke nie je.
Pri lineárnom sondovaní sa skúšajú po sebe idúce priehradky. Ak je tabuľka veľká m a prvé miesto je i, ďalšie pokusy môžu byť:
i, (i + 1) % m, (i + 2) % m, (i + 3) % m, ...Je jednoduché a dobre využíva voľné miesta, ale susedné položky majú tendenciu vytvárať dlhšie súvislé zhluky. Pri vkladaní a hľadaní potom môže byť potrebné preskúmať viac priehradiek.
i + 1², i + 2², i + 3². Môže obmedziť tvorbu súvislých zhlukov.Každý postup potrebuje starostlivo zvolený vzorec a veľkosť tabuľky, aby sondovanie vedelo nájsť voľné miesto a aby vyhľadávanie prechádzalo tie isté miesta ako vkladanie.
Pri oboch prístupoch môže veľa kolízií zhoršiť výkon. Ide o všeobecné techniky hash tabuliek; konkrétne jazyky a knižnice si vyberajú vlastnú implementáciu.
Pri dobre rozložených hash hodnotách stačí skontrolovať len malú časť tabuľky, preto je vyhľadávanie, vloženie a odstránenie priemerne O(1).
Preto priemerné O(1) opisuje typické správanie, nie záruku pre každý vstup.
dequecollections.deque umožňuje efektívne pridávať a odoberať prvky na začiatku aj na konci.
from collections import deque
items = deque(["B", "C"])
items.appendleft("A")
items.append("D")
print(items.popleft()) # A
print(items.pop()) # DNa opakované odoberanie zo začiatku nepoužívajte list.pop(0): vyžaduje posun prvkov a stojí O(n).
Zásobník pracuje podľa princípu LIFO (Last In, First Out): posledný vložený prvok vyberieme ako prvý.
Predstavte si kopu tanierov: nový tanier položíme navrch a zvrchu ho aj odoberieme. Miesto pridávania a odoberania nazývame vrchol zásobníka.
Po vložení A, B, C: push(D): pop() vráti D:
+-------+
| D | <- vrchol
+-------+ +-------+ +-------+
| C | <- vrchol | C | | C | <- vrchol
+-------+ +-------+ +-------+
| B | | B | | B |
+-------+ +-------+ +-------+
| A | <- dno | A | <- dno | A | <- dno
+-------+ +-------+ +-------+V Pythone na zásobník zvyčajne stačí zoznam. Za vrchol zvolíme jeho koniec, preto používame append() a pop() bez indexu.
stack = []
stack.append("A") # push: ["A"]
stack.append("B") # push: ["A", "B"]
print(stack[-1]) # B: pozri na vrchol bez odobratia
top = stack.pop() # pop: vráti "B", zostane ["A"]pop() aj stack[-1] vyvolajú IndexError, ak je zásobník prázdny; pred použitím možno skontrolovať if stack:.
Pridanie na koniec má amortizovanú zložitosť O(1); odobratie z konca tiež amortizovane O(1). Nahliadnutie na vrchol má O(1).
Chceme overiť správne párovanie a vnorenie zátvoriek (), [] a {}. Napríklad ([]) je správne, ale ([)] nie, hoci počty zátvoriek sú rovnaké.
Text čítame zľava doprava. Zásobník uchováva otváracie zátvorky, ktoré ešte neboli uzavreté.
Prečo LIFO? Najskôr musíme uzavrieť naposledy otvorenú zátvorku, až potom vonkajšiu.
Pre vstup ([]) vyzerá zásobník takto; vrchol je vpravo:
Znak Operácia Zásobník (dno -> vrchol)
start prázdny
( push ( (
[ push [ ( [
] pop [ : pár [] sedí (
) pop ( : pár () sedí prázdny
koniec prázdny zásobník -> správne uzátvorkovaniePri ([)] narazíme na ), ale na vrchole je [: typy nesedia.
Pri ()) príde posledná ) na prázdny zásobník. Pri (() na konci zostane neuzavretá (.
def brackets_balanced(text):
stack = []
pairs = {")": "(", "]": "[", "}": "{"}
for char in text:
if char in "([{":
stack.append(char)
elif char in pairs:
if not stack: # uzatváracia bez otváracej
return False
if stack.pop() != pairs[char]:
return False # nesprávny typ zátvorky
return not stack # nezostali neuzavreté?Ostatné znaky ignorujeme. Ide o kontrolu uzátvorkovania obyčajného textu; funkcia nerozlišuje reťazcové literály ani komentáre programovacieho jazyka.
print(brackets_balanced("a * (b + [c])")) # True
print(brackets_balanced("([)]")) # False: nesprávne vnorenie
print(brackets_balanced("())")) # False: nadbytočná )
print(brackets_balanced("(()")) # False: neuzavretá (
print(brackets_balanced("")) # True: žiadne zátvorkyPre text dĺžky n je časová zložitosť O(n): každý znak prečítame raz a každú zátvorku vložíme a odoberieme najviac raz.
Pomocná pamäť je v najhoršom prípade O(n), napríklad ak vstup obsahuje iba otváracie zátvorky. Počas spracovania veľkosť zásobníka zodpovedá počtu práve neuzavretých zátvoriek.
Fronta pracuje podľa princípu FIFO (First In, First Out): prvý vložený prvok vyberieme ako prvý.
Predstavte si rad pri pokladni: nový zákazník sa zaradí na koniec, obsluhujeme zákazníka na začiatku. Fronta teda pridáva a odoberá prvky na opačných koncoch.
Po vložení A, B, C:
začiatok koniec
+-----+-----+-----+
| A | B | C |
+-----+-----+-----+
enqueue(D): pridaj na koniec
začiatok koniec
+-----+-----+-----+-----+
| A | B | C | D |
+-----+-----+-----+-----+
dequeue(): odober zo začiatku, vráti A
začiatok koniec
+-----+-----+-----+
| B | C | D |
+-----+-----+-----+Ďalej vyberieme B, potom C a D. Zásobník by po vložení A, B, C, D vybral ako prvé D.
dequeV Pythone použijeme collections.deque: pridávame sprava cez append() a odoberáme zľava cez popleft().
from collections import deque
queue = deque()
queue.append("A") # enqueue: deque(["A"])
queue.append("B") # enqueue: deque(["A", "B"])
print(queue[0]) # A: pozri na začiatok bez odobratia
first = queue.popleft() # dequeue: vráti "A", zostane deque(["B"])append() a popleft() majú zložitosť O(1). Pri list.pop(0) by sa ostatné prvky posúvali, čo stojí O(n).
popleft() aj queue[0] vyvolajú IndexError, ak je fronta prázdna. Pred použitím ju môžeme skontrolovať cez if queue:.
deque sa hodí pre bežnú frontu v jednom vlákne. Modul queue.Queue poskytuje synchronizáciu pri zdieľaní fronty medzi vláknami.
Aplikácia pri registrácii používateľa vytvorí uvítací e-mail a zaradí ho do fronty. Spracovateľ postupne vyberá čakajúce správy a odosiela ich.
Operácia Čakajúce správy (začiatok -> koniec)
pridaj e-mail pre Annu [Anna]
pridaj e-mail pre Borisa [Anna, Boris]
odober a odošli e-mail pre Annu [Boris]
pridaj e-mail pre Cyrila [Boris, Cyril]
odober a odošli e-mail pre Borisa [Cyril]
odober a odošli e-mail pre Cyrila []Fronta oddeľuje vznik úlohy od jej vykonania. Samotná deque však nespúšťa spracovanie na pozadí; v nasledujúcej ukážke sa všetko vykonáva postupne v jednom vlákne.
from collections import deque
emails = deque()
def enqueue_email(recipient):
emails.append((recipient, "Vitajte!"))
def send_email(recipient, subject):
# Simulácia odoslania: iba vypíšeme správu.
print(f"Odosielam pre {recipient}: {subject}")
enqueue_email("anna@example.com")
enqueue_email("boris@example.com")
recipient, subject = emails.popleft()
send_email(recipient, subject) # najskôr Anna
enqueue_email("cyril@example.com") # pribudne za Borisa
while emails: # kým nie je fronta prázdna
recipient, subject = emails.popleft()
send_email(recipient, subject) # potom Boris a CyrilUkážka vypíše:
Odosielam pre anna@example.com: Vitajte!
Odosielam pre boris@example.com: Vitajte!
Odosielam pre cyril@example.com: Vitajte!FIFO určuje poradie odoberania úloh. Pri viacerých súčasných odosielateľoch sa poradie dokončenia môže líšiť; ani poradie doručenia do schránok tým nie je zaručené.
Pri skutočnom odosielaní treba riešiť aj chyby: ak správu odoberieme a odoslanie zlyhá, samotná deque ju nevráti. Úlohy uložené iba v pamäti sa pri ukončení procesu stratia. Trvalé uloženie a opakovanie neúspešných pokusov sú ďalšie časti návrhu.
Spracovanie n správ vykoná O(n) operácií fronty; čas samotného odosielania počítame osobitne. Pamäť fronty závisí od počtu práve čakajúcich správ.
Prioritná fronta vyberá prvok podľa priority, nie podľa času vloženia. V nasledujúcom príklade menšie číslo znamená vyššiu prioritu.
import heapq
tasks = []
heapq.heappush(tasks, (2, 0, "pridaj testy"))
heapq.heappush(tasks, (1, 1, "oprav chybu"))
heapq.heappush(tasks, (2, 2, "napíš dokumentáciu"))
priority, order, task = heapq.heappop(tasks)
print(task) # oprav chybuPoradové číslo rozlíši úlohy s rovnakou prioritou bez porovnávania ich názvov.
heap)Halda sa hodí, keď často vkladáme prvky a opakovane vyberáme najmenší (alebo najvyššie prioritný podľa zvoleného kódovania) prvok.
list je univerzálny usporiadaný zoznam; vkladanie na začiatok je pomalé.dict a set používajú hashovanie a bežne poskytujú rýchle členstvo a vyhľadávanie.deque je vhodný na fronty a operácie na oboch koncoch.