Zadanie skúšky z 14.2.2019

Implementujte metódy asociatívneho poľa pomocou otvoreného hašovania, v ktorom sa kolízie riešia zreťazovaním - ukladaním do vedierok (bucket). Kľúčmi v asociatívnom poli budú len celé čísla, preto hašovacia funkcia bude z tohto celého čísla počítať len zvyšok po delení veľkosťou tabuľky. Tabuľka sa bude resizovať len v tom prípade, keď počet kľúčov presiahne (bude väčší) ako 90% veľkosti tabuľky. Samotné vedierka realizujte jednosmerným spájaným zoznamom (linked list) tak, že v každom prvku _Item sa okrem kľúča a hodnoty (_key a _value) nachádza aj referencia na nasledovný prvok vo vedierku (_next).

Na riešenie úlohy použite deklarácie v súbore skuska.py z úlohového servera L.I.S.T. kde

  • inicializácia __init__ nastaví počiatočnú veľkosť hašovacej tabuľky _table; prvkami tejto tabuľky budú buď None (voľný prvok) alebo objekt typu _Item
  • metóda add, ak daný kľúč existuje, zmení mu v tabuľke hodnotu, ak neexistuje, najprv do tabuľky (do príslušného vedierka) vloží dvojicu key, value; ak je teraz tabuľka viac ako na 90% obsadená, tabuľka sa resize na dvojnásobok plus 1
  • nemeňte _Item a _hash, môžete dodefinovať ďalšie pomocné metódy
  • metóda print slúži len na pomoc pri ladení, pri testovaní sa nepoužije
class ChainHashMap:
    class _Item:
        def __init__(self, key, value, next=None):
            self._key, self._value, self._next = key, value, next

        def __repr__(self):
            return repr(self._key) + ':' + repr(self._value)

    #------------------

    def __init__(self, capacity=11):
        # kazdy prvok je bud None (volne),
        #   alebo je typu _Item (obsahuje key, value a nasledovnika)
        self._table = ...

    def _hash(self, key):
        return key % len(self._table)

    def valueof(self, key):
        # pre dany key vrati value alebo vyvola KeyError
        raise KeyError

    def add(self, key, value=None):
        # ak existuje dany key, zmeni value
        # ak neexistuje, do tabulky prida dvojicu key, value
        # ak je tabulka viac ako na 90% obsadena, tabulka sa resize na dvojnasobok + 1
        ...

    def delete(self, key):
        # pre dany kluc vyhodi dvojicu key, value alebo vyvola KeyError
        raise KeyError

    def __len__(self):
        # vrati pocet klucov
        return 0

    def __iter__(self):
        # vrati generator vsetkych klucov
        ...

    def print(self):
        for index, bucket in enumerate(self._table):
            print(index, end=' ')
            while bucket:
                print(bucket, end=' -> ')
                bucket = bucket._next
            print(None)

Váš program môžete testovať napr. takto:

if __name__ == '__main__':
    a = ChainHashMap(10)
    pole = [(55,'a'),(42,'b'),(15,'c'),(60,'d'),(78,'e'),
            (35,'f'),(22,'g'),(10,'h'),(11,'i'),(15,'j')]
    for key, value in pole:
        a.add(key, value)
    a.print()

    a = ChainHashMap(5)
    d = {}
    for i in 3, 16, 5, 11, 23, 25, 15, 18, 15, 14, 25:
        try:
            a.add(i, a.valueof(i) + 1)
        except KeyError:
            a.add(i, 1)
        d[i] = d.get(i, 0) + 1
    set1 = {(it, a.valueof(it)) for it in a}
    set2 = set(d.items())
    print('=== druhy test', set1 == set2)
    a.print()

Výpis potom bude takýto:

0 10:'h' -> 60:'d' -> None
1 11:'i' -> None
2 22:'g' -> 42:'b' -> None
3 None
4 None
5 35:'f' -> 15:'j' -> 55:'a' -> None
6 None
7 None
8 78:'e' -> None
9 None
=== druhy test True
0 11:1 -> None
1 23:1 -> None
2 None
3 14:1 -> 25:2 -> 3:1 -> None
4 15:2 -> None
5 16:1 -> 5:1 -> None
6 None
7 18:1 -> None
8 None
9 None
10 None

Aby ste mohli spúšťať skúškové testy, program uložte do súboru skuska.py.

Riešenie odovzdajte na úlohový server L.I.S.T..

Praktická časť končí o 11:00 a skúška ďalej pokračuje od 12:00 vyhodnotením v kancelárii m162.



© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.