11. hét: ládarendezés, hash táblák

Czirkos Zoltán, Frey Balázs · 2020.11.21.

Ládarendezés. Hash táblák építése.

Felkészülés a laborra:

1. Ládarendezés egész számokra

Ez az algoritmus szerepelt előadáson is. Vigyázz: nem az a kérdés, hogy ki tudod-e onnan másolni a kódot, hanem az, hogy meg tudod-e írni magad!

A ládarendezés (leszámláló rendezés) nem hasonlítja össze az egyes elemeket egymással, hanem nagyságuk szerint csoportosítja őket.

Lássuk a legegyszerűbb esetet, rendezzünk egy listát egész számokkal!

5 4 8 4 0 6 4 8 9

Ebben a listában 0 és 9 között vannak számok. Fogunk egy másik listát, amelyben leszámláljuk, hogy melyikből hány darab szerepel:

0123456789
1000311021

Ebből az információból egy új lista állítható elő, amelyik rendezett lesz. Nem kell hozzá mást tenni, mint 1 db 0-st, 3 db 4-est, 1 db 5-öst, 1 db 6-ost, 2 db 8-ast és 1 db 9-est tenni bele:

0 4 4 4 5 6 8 8 9

Írj programot, amely generál egy 0...99 véletlenszámokból álló, 100 elemű listát, majd a fenti algoritmussal rendezi azt! Ellenőrizd az eredményt „szemrevételezéssel”! (Jobb előbb tesztelni olyan kicsi bemeneten, amire a futási eredmény könnyen ellenőrizhető.) Ha működik, próbáld ki nagyobb listára is, akár 10000 vagy 100000 eleműre, és ellenőrizd az eredményt! Ehhez érdemes egy rendezett_e() függvényt írni.

Fogd az előző programod, és a ládarendezést tedd át egy függvénybe! Vegye át a függvény a szokásos módon a rendezendő listát paraméterként.

Megoldás

Az alábbi megoldás megkeresi a legkisebb és a legnagyobb számot a listából, így automatikusan méretezni tudja a számlálók listáját. Ehhez még jobb lenne egy dict, de később szerepel majd a tananyagban.

Itt van egy buktató: a leszámlálás után új listát kell előállítani. A függvényben viszont nem írható lista = []-t, mert az új listát hoz létre, és a függvény paraméterében lévő referenciát módosítja, nem az eredetit. Mindenképp del lista[:] kell. Vagy a meglévő lista elemeit kell felülírni, elvégre is pont ugyanannyi lesz benne, mint rendezés előtt. Az utóbbi kicsit gyorsabb; az előbbivel egyszerűbb a kód, ezért azt mutatja a mintamegoldás.

import random
 
def rendezes_leszamlalassal(lista):
    minimum = min(lista)
    maximum = max(lista)
    db = [0] * (maximum - minimum + 1)
    for x in lista:
        db[x - minimum] += 1
 
    del lista[:]
    for i in range(len(db)):
        for _ in range(db[i]):
            lista.append(i + minimum)
 
def main():
    db = 10000
    l1 = []
    for i in range(db):
        l1.append(random.randint(0, 99))
 
    rendezes_leszamlalassal(l1)
    print(l1)
 
main()

2. Hash tábla: vödrös hash

Emlékezz vissza az Algoritmusok és gráfok tárgyban tanult hash táblákra! Azon belül is most konkrétan a vödrös hash-re. Ennek lényege az volt, hogy ütközések esetén az ütköző elemeket egy listába tesszük:

Implementálj egy ilyen hash táblát! Az egyszerűség és a szemléletesség kedvéért a megvalósítás működjön a következőképp:

  • A hash tábla tároljon sztringeket. Tételezd fel, hogy a sztringekben csak ékezet nélküli, kisbetűs szavak vannak, például „alma”, „korte” és „barack”.
  • A hash függvény legyen a szó első betűjének ábécébeli sorszáma: a=0, b=1, c=2 és így tovább. Emlékezz vissza a karakterkódok kezelésére, ilyesmivel már találkoztál.
  • Az ütközéseket könnyű elképzelni: minden ugyanolyan betűvel kezdődő szó ütközés lesz (pl. „alma”, „ananasz” és „avokado”). De ez nem baj, ennek kezelésére valók a vödrök.

A táblát halmazként fogjuk használni: be lehet tenni, ki lehet venni egy szót, és megnézni, hogy épp benne van-e a szó a táblában. Valósítsd meg az alábbi függvényeket:

  • hash_tabla_letrehoz(): létrehoz és visszaad egy hash táblát, ahol maga a táblázat létre van már hozva, és üres elemeket tartalmaz. (Vagyis egy olyan listát kell csinálnod, ami üres listákat tartalmaz. Hasonló lesz ez a kétdimenziós listához, de itt a belsők kezdetben üresek.) Vajon hány elemű lesz a tábla, ha a fenti hash függvényt használod?
  • hash_tabla_betesz(tabla, szo): betesz egy szót a táblába. Ha már benne van, nem csinál semmit.
  • hash_tabla_debug(tabla): kiírja a hash tábla tartalmát a kimenetre olyan formában, hogy az segítse a hibakeresést.
  • hash_tabla_benne_van(tabla, szo): megadja, hogy egy szó benne van-e a táblában. Ügyelj arra, hogy az ütközések miatt a vödrökben keresni kell majd.
  • hash_tabla_kivesz(tabla, szo): kivesz egy szót a hash táblából. Ha nincs benne, nem csinál semmit.
  • hash_tabla_listaz(tabla): kiírja a táblában tárolt összes szót ömlesztve.

Ha a kapott sztring alkalmatlan a hasheléshez (nem az „a...z” karakterek valamelyikével kezdődik), dobj kivételt! Ügyelj arra, hogy ne duplikáld a hash számító kódot, inkább írj egy függvényt hozzá!

Teszteld a kapott programod, ellenőrizd a helyes működését! Tegyél a hash tábládba azonos betűvel, és eltérő betűvel kezdődő szavakat is!

Megoldás
def hash_fuggveny(szo):
    if ord(szo[0]) < ord('a') or ord(szo[0]) > ord('z'):
        raise ValueError("Ékezet nélküli kisbetűvel kezdődjenek a szavak")
    return ord(szo[0])-ord('a')


def hash_tabla_letrehoz():
    tabla = []
    for _ in range(ord('z') - ord('a') + 1):
        tabla.append([])
    return tabla


def hash_tabla_betesz(tabla, szo):
    idx = hash_fuggveny(szo)
    if szo not in tabla[idx]:
        tabla[idx].append(szo)


def hash_tabla_debug(tabla):
    for i in range(len(tabla)):
        print(chr(i+ord('a')), end=": ")
        for j in range(len(tabla[i])):
            print(tabla[i][j], end=" ")
        print()


def hash_tabla_benne_van(tabla, szo):
    idx = hash_fuggveny(szo)
    return szo in tabla[idx]


def hash_tabla_kivesz(tabla, szo):
    idx = hash_fuggveny(szo)
    tabla[idx].remove(szo)


def hash_tabla_listaz(tabla):
    for vodor in tabla:
        for szo in vodor:
            print(szo, end=" ")
    print()


def main():  
    tabla = hash_tabla_letrehoz()
    hash_tabla_betesz(tabla, "alma")
    hash_tabla_betesz(tabla, "korte")
    hash_tabla_betesz(tabla, "szilva")
    hash_tabla_betesz(tabla, "barack")
    hash_tabla_betesz(tabla, "banan")
    hash_tabla_betesz(tabla, "ananasz")
    hash_tabla_betesz(tabla, "bodza")
    hash_tabla_betesz(tabla, "zeller")
    
    hash_tabla_debug(tabla)
    
    print("alma: {}".format("benne van" if hash_tabla_benne_van(tabla, "alma") else "nincs benne"))
    print("citrom: {}".format("benne van" if hash_tabla_benne_van(tabla, "citrom") else "nincs benne"))
    
    hash_tabla_kivesz(tabla, "zeller")
    
    hash_tabla_listaz(tabla)


main()

3. Automatikus tesztek

Az előző feladathoz kitaláltál egy műveletsort, amelyben megadott sorrendben kellett beszúrni, törölni, keresni elemeket a táblában. Például „alma betesz”, „barack betesz”, „alma betesz”, „barack kivesz” stb. Minden lépésnél adott volt, hogy milyen eredményt vársz.

Dolgozd át azt a tesztsorozatot egy automatikus tesztté! Használd ehhez a beépített assert() függvényt! Erre példát mutat az alábbi programocska:

def lnko(a, b):
    """Legnagyobb közös osztó, Euklidész algoritmusával."""
    while b != 0:
        t = b
        b = a%b
        a = t
    return a

def main():
    assert(lnko(30, 12) == 6)
    assert(lnko(12, 30) == 6)
    assert(lnko(35, 2) == 1)
    assert(lnko(3, 2) == 1)

main()

„Rontsd el” a programod, például módosítsd a keresőfüggvényed úgy, hogy mindig hamis értéket adjon! Próbáld ki így a tesztet!

Megoldás
# csak a tesztelő függvény,
# a többit mellé kell másolni az előző feladatból

def main():
    tabla = hash_tabla_letrehoz(26)
    hash_tabla_betesz(tabla, "alma")
    hash_tabla_betesz(tabla, "ananász")
    hash_tabla_betesz(tabla, "barack")
    hash_tabla_betesz(tabla, "dinnye")
    assert(hash_tabla_benne_van(tabla, "alma"))
    assert(hash_tabla_benne_van(tabla, "ananász"))
    assert(hash_tabla_benne_van(tabla, "barack"))
    assert(hash_tabla_benne_van(tabla, "dinnye"))

    hash_tabla_betesz(tabla, "cseresznye")
    assert(hash_tabla_benne_van(tabla, "cseresznye"))
    
    hash_tabla_kivesz(tabla, "ananász")
    assert(not hash_tabla_benne_van(tabla, "ananász"))
    
    hash_tabla_betesz(tabla, "avokádó")
    assert(hash_tabla_benne_van(tabla, "avokádó"))
    
    hash_tabla_betesz(tabla, "zeller")
    hash_tabla_betesz(tabla, "zsiráf")
    assert(hash_tabla_benne_van(tabla, "zeller"))
    assert(hash_tabla_benne_van(tabla, "zsiráf"))
    
    print("ok")

4. Hash tábla: a hash függvény cseréje

Az előző feladatban használt hash függvény nem túl jó. Az mindig a szó első betűjét használja indexnek, viszont pl. sokkal-sokkal több „a” betűvel kezdődő szó van, mint ahány „x” betűvel kezdődő. Így aztán nem szór jól, nem ad nagyjából egyenletes eloszlást a táblázatban.

A Python viszont beépítve tartalmaz egy hash() nevű függvényt, amelyik viszont minden sztringhez egy jó nagy számot ad:

print(hash("alma"))     # 1808484321251193290
print(hash("barack"))   # 2498199152977029591
print(hash("dinnye"))   # -4940521116470653504

A kapott számok esetleg változhatnak is, ahányszor indítjuk a programot, és negatívak is lehetnek. Viszont egy futtatás közben mindig ugyanazok lesznek ugyanarra a sztringre.

Írd át úgy a programod, hogy ezt a hash függvényt használja! Ez már bármilyen sztringre jó, és így lehetővé válik az is, hogy a hash tábla méretét megválasszuk.

  • Emlékezz vissza az Algoritmusok és gráfok tárgyból tanultakra! Hogyan képezzük le a hash függvény értékét a fix méretű táblázat indexeire?
  • Próbáld ki a Python % operátorát, hogy viselkedik, ha negatív számot kap osztandónak!
  • Egészítsd ki a hash_tabla_letrehoz() függvényt egy méretet adó paraméterrel! Vagyis lehessen megadni a függvénynek, hogy mekkora a tábla.
  • Módosítsd a többi függvényt, figyelembe véve a változtatásokat!

Teszteld az így kapott függvényeid működését!

Megoldás
def hash_tabla_letrehoz(meret):
    tabla = []
    for _ in range(meret):
        tabla.append([])
    return tabla


def hash_tabla_betesz(tabla, szo):
    idx = hash(szo) % len(tabla)
    if szo not in tabla[idx]:
        tabla[idx].append(szo)


def hash_tabla_debug(tabla):
    for i in range(len(tabla)):
        print(i, end=": ")
        for j in range(len(tabla[i])):
            print(tabla[i][j], end=" ")
        print()


def hash_tabla_benne_van(tabla, szo):
    idx = hash(szo) % len(tabla)
    return szo in tabla[idx]


def hash_tabla_kivesz(tabla, szo):
    idx = hash(szo) % len(tabla)
    tabla[idx].remove(szo)


def hash_tabla_listaz(tabla):
    for vodor in tabla:
        for szo in vodor:
            print(szo, end=" ")
    print()


def main():  
    tabla = hash_tabla_letrehoz(26)
    hash_tabla_betesz(tabla, "alma")
    hash_tabla_betesz(tabla, "korte")
    hash_tabla_betesz(tabla, "szilva")
    hash_tabla_betesz(tabla, "barack")
    hash_tabla_betesz(tabla, "banan")
    hash_tabla_betesz(tabla, "ananasz")
    hash_tabla_betesz(tabla, "bodza")
    hash_tabla_betesz(tabla, "zeller")
    
    hash_tabla_debug(tabla)
    
    print("alma: {}".format("benne van" if hash_tabla_benne_van(tabla, "alma") else "nincs benne"))
    print("citrom: {}".format("benne van" if hash_tabla_benne_van(tabla, "citrom") else "nincs benne"))
    
    hash_tabla_kivesz(tabla, "zeller")
    
    hash_tabla_listaz(tabla)


main()