Údajové štruktúry v Pythone

Základné štruktúry

zoznam - list
slovník - dict
množina - set

Zoznam je dynamické pole

Dynamické pole pre ukladanie usporiadaných prvkov.

Alokácia a dealokácia je automatická.

Pridanie na začiatok a na koniec.

Dĺžka zoznamu nie je fixná, vieme pridávať na začiatok, koniec aj do stredu.

Uvoľnenie prvkov pomocou del:

del pole[:]

Čo je to asociatívne pole?

Zovšeobecnenie zoznamu, kde namiesto číselných indexov používame kľúče ľubovoľného hashable typu

Slovník

Chceme rýchlo:

vložiť hodnotu,
nájsť hodnotu podľa kľúča,
zistiť, či sa prvok nachádza v množine,
odstrániť hodnotu.
asociatívne pole

Indexujeme pomocou reťazcov, nie čísel

mapovanie kľúč = hodnota

Poradie kľúčov nemusí byť definované

kľúč → hodnota

Príklady v Pythone:

dict
set

person = {
    "name": "Anna",
    "age": 20
}

print(person["name"])

Slovníky sa používajú pri:

reprezentácii entít (records),
počítaní výskytov,
cache,
indexovaní dát,
kontrole duplicít,
rýchlom vyhľadávaní podľa kľúča.

Príklad: počítanie výskytov

words = ["a", "b", "a", "c", "b", "a"]

counts = {}

for word in words:
    counts[word] = counts.get(word, 0) + 1

print(counts)

Výstup:

{'a': 3, 'b': 2, 'c': 1}

Príklad: kontrola duplicít

def has_duplicates(items):
    seen = set()

    for item in items:
        if item in seen:
            return True
        seen.add(item)

    return False

Použitie set umožňuje rýchlu kontrolu členstva.

Implementácia slovníka: Hash tabuľka

Hash tabuľka používa pole priehradiek.

Hash funkcia premení kľúč na index v poli.

kľúč ──hash funkcia──> číslo ──mod veľkosť tabuľky──> index

Príklad:

"Anna" ──hash──> 73421 ──% 10──> 1

Hodnota sa uloží na index 1.

Pri dobrej hash funkcii majú tieto operácie priemerne zložitosť:

O(1)

lebo počet operácií na vyhľadanie je konštantný, nezávisí od počtu prvkov v tabuľke.

Hash funkcia

Hash funkcia priradí vstupu číselnú hodnotu.

Dobrá hash funkcia:

je rýchla,
rovnakému vstupu dá vždy rovnaký výsledok,
rovnomerne rozkladá kľúče po tabuľke,
minimalizuje kolízie.

print(hash("Anna"))
print(hash("Peter"))

Jednoduchý príklad hash funkcie

Pre reťazec môžeme sčítať kódy znakov.

def simple_hash(text, size):
    total = 0
    for ch in text:
        total += ord(ch)
    return total % size

print(simple_hash("Anna", 10))
print(simple_hash("Peter", 10))

Toto je jednoduché, ale nie veľmi kvalitné riešenie.

Príklad lepšej hash funkcie

Často sa používa postupné násobenie a pripočítavanie znakov.

def polynomial_hash(text, size):
    h = 0
    for ch in text:
        h = h * 31 + ord(ch)
    return h % size

print(polynomial_hash("Anna", 10))
print(polynomial_hash("Peter", 10))

Číslo 31 pomáha rozložiť podobné reťazce na rôzne hodnoty.

Kolízia

Kolízia nastane, keď dva rôzne kľúče dostanú rovnaký index.

"Anna"  ──> index 1
"Adam"  ──> index 1

Kolíziám sa nedá úplne vyhnúť.

Hash tabuľka preto musí mať spôsob, ako ich riešiť.

Riešenie kolízií: reťazenie

Pri reťazení má každá priehradka zoznam prvkov.

index 0: []
index 1: [("Anna", 20), ("Adam", 21)]
index 2: []

Vyhľadávanie:

vypočítaj index,
prejdi zoznam na danom indexe,
nájdi správny kľúč.

Riešenie kolízií: otvorené adresovanie

Pri otvorenom adresovaní sa pri kolízii hľadá iné voľné miesto v tabuľke.

Jednoduchá stratégia:

ak je index obsadený, skús index + 1

"Anna" → index 1
"Adam" → index 1 obsadený → index 2

Tento postup sa nazýva lineárne skúšanie.

Riešenie kolízií: ďalšie stratégie

Okrem reťazenia a lineárneho skúšania existujú aj:

kvadratické skúšanie,
dvojité hashovanie,
zväčšenie tabuľky a prehashovanie.

Prehashovanie znamená:

vytvoriť väčšiu tabuľku,
znovu vypočítať index pre každý kľúč,
presunúť prvky do novej tabuľky.

Load factor

Hash tabuľka plytvá pamäťou.

Koľko pamäte potrebujem?

Load factor vyjadruje, ako plná je hash tabuľka.

load factor = počet prvkov / veľkosť tabuľky

Príklad:

počet prvkov = 7
veľkosť tabuľky = 10
load factor = 0.7

Čím je tabuľka plnšia, tým viac rastie riziko kolízií.

Prečo sledovať load factor?

Ak je load factor príliš vysoký:

pribúda kolízií,
vyhľadávanie sa spomaľuje,
tabuľka sa musí zväčšiť.

Bežný postup:

ak load factor prekročí hranicu → zväčši tabuľku

Potom sa prvky prehashujú do väčšej tabuľky.

Mini implementácia

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.items = [[] for _ in range(size)]

    def _index(self, key):
        return hash(key) % self.size

    def set(self, key, value):
        index = self._index(key)
        bucket = self.items[index]

        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return

        bucket.append((key, value))

Vyhľadanie v mini hash tabuľke

class HashTable:
    # ...

    def get(self, key):
        index = self._index(key)
        bucket = self.items[index]

        for k, value in bucket:
            if k == key:
                return value

        raise KeyError(key)

Používa reťazenie: každá priehradka obsahuje zoznam dvojíc.

Zásobník a fronta

Pri paralelnom a asynchrónnom programovaní potrebujeme často ukladať úlohy, ktoré sa majú vykonať neskôr.

Na to používame dátové štruktúry:

Stack (zásobník)
Queue (fronta)

Zásobník (Stack)

Princíp:

Posledný vložený prvok sa vyberá ako prvý.

LIFO

LIFO = Last In, First Out

Príklad:

Pridaj A
Pridaj B
Pridaj C

Vyber → C
Vyber → B
Vyber → A

Vizualizácia:

| C | ← vrchol
| B |
| A |
-----

Pripomína stoh tanierov.

Abstraktné operácie zásobníka

push(x)   # vloženie
pop()     # odstránenie vrchného prvku
peek()    # zistenie vrchného prvku
is_empty()
size()

Implementácia pomocou listu

stack = []

stack.append(10)
stack.append(20)
stack.append(30)

print(stack.pop())

Výstup:

Vlastná implementácia

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

Fronta (Queue)

Princíp:

Prvý vložený prvok sa vyberá ako prvý.

FIFO

FIFO = First In, First Out

Príklad:

Pridaj A
Pridaj B
Pridaj C

Vyber → A
Vyber → B
Vyber → C

Vizualizácia:

A B C
↑   ↑
out in

Pripomína radu v obchode.

Operácie fronty

enqueue(x)
dequeue()
front()
is_empty()

Implementácia pomocou queue.Queue

from queue import Queue

q = Queue()

q.put("A")
q.put("B")
q.put("C")

print(q.get())

Výstup:

Prioritná fronta

Niektoré úlohy sú dôležitejšie než ostatné.

Príklady:

operačný systém
plánovač procesov
nemocničný systém

Princíp

Každý prvok má prioritu.

(A, 3)
(B, 1)
(C, 2)

Vyberá sa najvyššia priorita:

B
C
A

Implementácia

from queue import PriorityQueue

pq = PriorityQueue()

pq.put((3, "Low"))
pq.put((1, "High"))
pq.put((2, "Medium"))

while not pq.empty():
    print(pq.get())

Výstup:

(1, 'High')
(2, 'Medium')
(3, 'Low')

Halda

Prioritná fronta sa často implementuje pomocou haldy.

Halda je stromová dátová štruktúra, ktorá dodržiava pravidlo:

rodič má vyššiu alebo rovnakú prioritu ako jeho potomkovia

V min-halde je najmenší prvok vždy v koreni.

Prioritná fronta pomocou haldy

Prioritu uložíme ako prvú hodnotu v dvojici.

import heapq

tasks = []

heapq.heappush(tasks, (3, "napíš dokumentáciu"))
heapq.heappush(tasks, (1, "oprav chybu"))
heapq.heappush(tasks, (2, "pridaj testy"))

while tasks:
    priority, task = heapq.heappop(tasks)
    print(priority, task)

Najmenšie číslo má najvyššiu prioritu.

Kedy použiť haldu?

Halda je vhodná, keď často potrebujeme:

vkladať nové prvky,
opakovane vyberať prvok s najvyššou prioritou,
nechceme po každej zmene triediť celý zoznam.

Nie je vhodná, keď potrebujeme rýchlo vyhľadávať ľubovoľný prvok podľa hodnoty.