Množiny
Pomocí bitových operátorů lze reprezentovat množinu. Mějme množinu čísel od 0 do 7 (univerzum). Libovolnou podmnožinu bychom mohli reprezentovat jako bitový vektor. 1 = obsahuje prvek na dané pozici, 0 = neobsahuje. Uvažujme následující množiny:
A = {1,2,7}, B = {5,6,7}, C = {0,1,2,3,4,5,6,7}, D = ∅
// Reprezentace mnozin v pameti
7 6 5 4 3 2 1 0
A = 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0
B = 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0
C = 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
D = 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Tato reprezentace nám umožní velice jednoduše a hlavně rychle vypočítat průnik dvou množin. Poslouží nám k tomu operace & (bitový součin).
Příklad
A ∩ B = {1,2,7} ∩ {5,6,7} = {7}
// Prunik pomoci bitoveho soucinu
1 0 0 0 0 1 1 0
&
1 1 1 0 0 0 0 0
---------------
1 0 0 0 0 0 0 0
Můžeme tedy reprezentovat množinu která obsahuje hodnoty od 0 do 7 jako přirozené číslo.
set_a = 134
set_b = 224
intersection = set_a & set_b; // 128
V jazyce Python vytvořte modul bitset s následujícími funkcemi.
Vytvoření funkce
# Alokace prazdné množiny
def create_bitset(size)
# Alokace množiny o velikosti size a obsahující hodnoty ze seznamu values.
def create_bitset_with_values(size, values)
# Alokace mnoziny o velikosti size a obsahujici hodnoty 0 az upto - 1
def create_bitset_with_range(size, upto)
Základní operace
# Vlozi prvek do mnoziny
def insert(bitset, element)
# Odebere prvek v z mnoziny
def remove(bitset, element)
# Funkce pro test, zda je prvek v mnozine.
# Funkce vraci True pokud prvek v mnozine je a jinak False
def contains(bitset, element)
Pokročilé operace
# Prunik dvou mnozin. Pokud má jedna z množin větší size i tak
# provedeme operaci, ale výsledná množina bude mít size větší množiny
def intersection(left, right)
# Sjednoceni dvou mnozin. Pokud má jedna z množin větší size i tak
# provedeme operaci, ale výsledná množina bude mít size větší množiny
def union(left, right)
# Rozdil dvou mnozin. Operaci provedeme pouze pokud size(left) >= size(right)
def difference(left, right)
# Test podmnoziny vraci True pokud je left podmnozinou right jinak False.
def is_subset(left, right)
Prace se soubory
Funkce load_bitset_if musí být schopna zpracovat libovolně velké soubory. Příklad takového souboru si můžete stáhnout zde (soubor bude dodán). Množiny jsou v souboru uložené ve formátu fimi (viz příklad).
# Mějme množinu A = {1, 3, 5, 7, 9, 20}
# Do souboru ji zapišeme takto:
1 3 5 7 9 20
# Ulozi pole mnozin do souboru kde kazda mnozina je na jednom radku
def save_bitsets_to_file(file, bitsets)
# Nacte n mnozin ze souboru ulozenych funkci save_bitsets_to_file
def load_bitsets(file)
# Nacte ze souboru pouze mnoziny splnujici predikat condition
def load_bitsets_if(condition, file)
Řešení uložte do souboru bitset.py
Bodování
Za úkol je možné získat 20 bodů kde student obdrží body za:
- Implementaci funkcí pro vytvoření množin: až 3 body
- Implementaci zakladních operací funkcí: až 3 body
- Implementaci pokročilých operací: až 7 bodů
- Implementaci práci se soubory: až 7 bodů
- Nedodržení konvencí jazyka Python (konvence naleznete zde) : -10 bodů.
- Nedělení kódu do jednotlivých funkcí: až -10 bodů.
- Používání "magických kosntant": -2 body.
- Nedodržení názvů funkcí: -10 bodů.
- Použítí nepovolených knihoven: -10 bodů.
- Nesprávné použití globálních proměnných: -5 bodů
- Vysoká paměťová náročnost: -10 bodů
- Duplicitní kód: -10 bodů
- Vedlejší efekt ve funkcích u kterých se nepředpokládá: -10 bodů
- Použití jiných konstrukcí které nebyly probrány na seminářích: -10 bodů
Hotové řešení zašlete do 17:00 31. 5. 2022 SEČ na email: roman.vyjidacek@upol.cz s predmětem ZPP2_02. Posílejte pouze soubory bitset.py jako samostaný soubor. Při pozdním odevzdáním bez předchozí domluvy nebo opisování bude student ohodnocen 0 body.