Összetett adatszerkezetek

List comprehension

Nagyon gyakoriak a listákat feldolgozó algoritmusok. Ha minden szám négyzetére van szükségünk:

szamok = [8, 6, 9, -7, 5]
negyzetszamok = []
for x in szamok:
    negyzetszamok.append(x ** 2)

Amikor a lista összes elemét sztringgé akarjuk alakítani:

szamok = [8, 6, 9, -7, 5]
sztringek = []
for x in szamok:
    sztringek.append(str(x))
print("Adatok:", ", ".join(sztringek))

Erre azért volt itt szükségünk, mert a sztringek .join() művelete csak sztringek listáját kaphatja paraméterként. Egész számok listájára TypeError típusú kivételt dob.

Általában véve, ilyen felépítésű kódunk van:

regi_lista = [ ... ]
uj_lista = []
for elem in regi_lista:
    uj_lista.append(valami_muvelet(elem))

A fenti példák valahogy így foghatók meg általánosságban. Van egy listánk, és szeretnénk létrehozni egy új listát. Az új listában ugyanazon sorrendben lesznek az elemek, mint a régiben, de minden elemmel csinálunk valamit. Mindegyiket négyzetre emeljük, mindegyikből kivonunk egyet, mindegyiket sztringgé alakítjuk, és így tovább.

A fenti algoritmusok írhatók le röviden az ún. list comprehension nyelvi elemmel. Ez magától felépít egy új listát, kiértékelve a megadott lista összes elemére a kifejezést. Vagyis ezzel egy leképezést (map) lehet megvalósítani: régi elemek → új elemek.

Négyzetszámok:

szamok = [8, 6, 9, -7, 5]
negyzetszamok = [x ** 2 for x in szamok] # [64, 36, 81, 49, 25]

print(negyzetszamok)

Minden elem sztringgé alakítva:

szamok = [8, 6, 9, -7, 5]
sztringek = [str(x) for x in szamok]     # ["8", "6", "9", "-7", "5"]

print("Adatok:", ", ".join(sztringek))   # Adatok: 8, 6, 9, -7, 5

A leképezés (list comprehension) szintaxisa általában:

[kifejezés for változónév in lista]

Gyakori művelet az is, hogy egy listát szűrni (filter) szeretnénk: vagyis előállítani egy új listát, amelyekben csak az eredeti lista bizonyos tulajdonságú elemei szerepelnek. Ha csak a pozitív számokra van szükségünk:

szamok = [8, 6, 9, -7, 5]
pozitivak = []
for x in szamok:
    if x > 0:
        pozitivak.append(x)

A list comprehension kifejezéseknek van egy opcionális befejező részük, amellyel szűrést valósíthatunk meg. Az if kulcsszó leírása után megadhatunk egy feltételt; az előálló listában csak azok az elemek fognak szerepelni, amelyekre ez igaz értékű. Ebben ugyanúgy a for mellett megadott változónevet használjuk. Pl. a listából csak a pozitív számokat felhasználva, azoknak a négyzetgyökét tesszük a másik listába:

szamok = [100, -7, 25, -64, 16]
gyokok = [x ** 0.5 for x in szamok if x > 0]    # [10, 5, 4]
print(gyokok)

Ha csak szűrni szeretnénk, leképezni nem, akkor a for elé, a leképezés helyére egyszerűen a változónevet írjuk. Így keletkezhet az elsőre kicsit furcsának ható x for x kódrészlet:

szamok = [8, 6, 9, -7, 5]
pozitivak = [x for x in szamok if x > 0]    # [8, 6, 9, 5]
print(pozitivak)

Ebben tehát:

• for x in szamok, vegyük a szamok lista összes elemét, nevezzük őket egyesével x-nek,
• if x > 0, de csak azokkal foglalkozzunk, amelyek pozitívak,
• x, ne csináljunk velük semmit, változatlanul tegyük be őket az új listába.

Feladat: állítsuk elő a prímszámok listáját 2-től 100-ig!

Ehhez felsoroljuk egy ciklussal a számokat 2-től 100-ig, és ha prímszám, betesszük azokat egy listába.

„Soroljuk fel ... és ha ..., akkor tegyük egy listába”, ez egy list comprehension kifejezést juttat eszünkbe. Ebben a felsorolt számok: minden szám 2-től 100-ig, vagyis range(2, 100+1) a vizsgálandó tartomány. Mit teszünk a listába? Magát a számot, tehát x for x in ... alakú lesz, leképezés nincs. Szűrni viszont kell, mert csak a prímszámokra vagyunk kíváncsiak: if prim(x)-et írunk a kifejezés végére.

def prim(szam):
    for oszto in range(2, szam):
        if szam % oszto == 0:
            return False
    return True

primek = [x for x in range(2, 100 + 1) if prim(x)]
print(primek)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Emlékezzünk vissza a mátrixokra, azaz kétdimenziós listákra! Itt tulajdonképp listák listájáról van szó. Ezek létrehozásánál figyelni kell arra, hogy a sorok listájába ne ugyanannak a sornak, azaz ne ugyanannak a listának a referenciáját tegyük bele sokszor:

def create_matrix_EZ_NEM_MUKODIK(w, h):
    return [[0] * w] * h

Helyette a sort létrehozó kifejezést is ki kell értékelni sokszor, hogy az sok sort, azaz sok listát hozzon létre. Nézzük meg, ez hogyan nézne ki ciklusokkal kifejtve!

def create_matrix(w, h):
    matrix = []
    for y in range(h):
        row = []
        for x in range(w):
            row.append(0)
        matrix.append(row)
    return matrix

def create_matrix(w, h):
    matrix = []
    for y in range(h):
        row = [0 for _ in range(w)] # [0, 0, 0, 0, ...]
        matrix.append(row)
    return matrix

def create_matrix(w, h):
    return [[0 for _ in range(w)] for _ in range(h)]

A gyorsrendezésben egy vezérelemnél (a rendezendő számsor egy tetszőlegesen választott eleménél) kisebb, nagyobb és azzal egyenlő elemeket válogattunk szét három listába. Utána pedig ezeket fűztük össze.

def gyorsrendez(lista):
    if len(lista) < 2:
        return lista
    return (
        gyorsrendez([x for x in lista if x < lista[0]])
        + [x for x in lista if x == lista[0]]
        + gyorsrendez([x for x in lista if x > lista[0]])
    )

Listák szűrésével ez ilyen egyszerű. A szétválogatást a szűrések x < vezer, x == vezer és x > vezer kifejezései elvégzik.

Milyen tárolót tehetünk a list comprehension kifejezésbe?

Például listát:

szamok = [1, 2, 3, 4, 5] # lista
negyzet = [x ** 2 for x in szamok]

Vagy fájlt, ha soronként szeretnénk haladni:

with open("szamok.txt") as f:
    szamsor = [int(s) for s in f] # fájl

Esetleg range típusú objektumot:

negyzetszamok = [x ** 2 for x in range(1, 10)] # range
print(negyzetszamok)

Bármit, amit amúgy is használhatnánk for ciklusban.

Beépített adatszerkezetek

Rendezett n-es (tuple)

Rögzített számú adatelemeket tároló immutábilis objektum.

t = (5, 9)

print(t[0], t[1])   # 5  9

Írjuk meg a függvényt, amelyik visszaadja egy lista legkisebb és legnagyobb elemét!

def minmax(szamok):
    """Visszadja: (legkisebb, legnagyobb)."""
    min = max = szamok[0]
    for i in range(1, len(szamok)):
        if szamok[i] < min: min = szamok[i]
        if szamok[i] > max: max = szamok[i]
    return (min, max) # tuple

Ennek a függvénynek két visszatérési értéke is van, a minimum és a maximum indexe. Az indexek meghatározása után becsomagolja azt egy tuple objektumba, így vissza tudja adni mindkettőt egyszerre, mert amúgy csak egyetlen objektum lehet a visszatérési érték.

Honnan fogja tudni a hívó, hogy melyik a minimum és maximum indexe? Kvázi sehonnan: a visszaadott tuple 0. eleme a minimum, és 1. eleme a maximum. Ezt onnan tudjuk csak, hogy a függvény dokumentációja jelzi ezt, és a függvény neve is valamennyire utal erre (ezért lett minmax(), és nem maxmin()).

szamsor = [67, 91, 28, 58, 26, 66, 5, 68, 42, 69]

t = minmax(szamsor)  # tuple
print("Legkisebb:", t[0], "legnagyobb:", t[1])

(min, max) = minmax(szamsor) # kicsomagolás
print(min, max) # 5  91

Függvényekből visszakapott, esetleg tárolókból kivett tuple objektumok esetén jó szokás kicsomagolni azokat külön változókba. Ezt mutatja az alsó két sor, ahol látszólag a min és max nevű változókat tartalmazó tuple-nek adunk értéket. Ez a szintaxis azt jelenti, hogy mindkét változót létrehozzuk, és azokba betesszük az értékül adott, a függvénytől származó tuple által visszaadott adatokat. Ilyenkor az abban tárolt adatok rendre bekerülnek a min és max változókba. Így legalább tudjuk, melyik mit jelent, és nem sorszám szerint kell hivatkozni rájuk.

Van néhány olyan kontextus, ahol zárójelek használata nélkül is tuple típusú adattal dolgozunk. Leggyakoribb esetek az értékadások és a return utasítás. Például egy függvényből két értéket visszaadva elhagyhatjuk a zárójeleket, hiszen az ott leírt vesszők miatt egyértelmű, hogy több adatról van szó, és automatikusan tuple jön majd létre. Ugyanilyen az értékadás is:

def minmax(szamok):
    # ...
    return min, max     # return (min, max)

(a, b) = (b, a)         # megcseréli a tartalmukat

a, b = b, a             # ugyanazt jelenti

Vigyázat!

Ahol amúgy is vesszővel elválasztott adatoknak kell megjelenniük, ott nem hagyhatjuk le a zárójeleket!

f(5, 7)     # két int a paraméter

f((5, 7))   # egy tuple a paraméter

szamok = [1, 2, 3, 4]  # négy szám tárolódik

szavak = [
  ("alma", "apple"),
  ("körte", "pear"),
]                      # két tuple tárolódik

turtle.pencolor("yellow")
turtle.pencolor((1, 0.5, 0.7))

Néha a programunkba beépítenénk valamilyen adatokat, és nem szeretnénk emiatt külön típusokat definiálni. Ilyenkor is jól jöhet a tuple. Az alábbi példában egy futóverseny eredményét tároljuk: a lista minden eleme egy helyezést és egy nevet rögzít. Az egyes elemek tuple típusúak, amelyben a 0. indexű adatelem a helyezés, az 1. indexű pedig a név.

verseny = [
    (4, "Jó Áron"),
    (3, "Break Elek"),
    (2, "Dil Emma"),
    (1, "Kasza Blanka"),
    (4, "Am Erika"),
]

for helyezes, nev in sorted(verseny):
    print(f"{helyezes}. helyezett: {nev}")

1. helyezett: Kasza Blanka
2. helyezett: Dil Emma
3. helyezett: Break Elek
4. helyezett: Am Erika
4. helyezett: Jó Áron

A ciklus ezen a tárolón iterál végig, minden tuple-t kicsomagolva a nev és a helyezes nevű változóba. A listázásban ráadásul a dobogósok kerültek előre: ezt a sorted() függvény biztosítja. Láthatóan valójában nem az eredeti tárolón, hanem annak rendezett változatán iterálunk.

Hogyan lehetséges ez? A rendezésben a sorted() függvény tuple elemeket kellett összehasonlítson. Ezekre értelmezve vannak az összehasonlító, relációs operátorok is. A tuple-ök összehasonlítása az adatelem szerint halad egyesével. Úgy dolgozik, ahogy a dátumokat vagy az időpontokat szoktuk összehasonlítani: előbb az első adatelemet nézve, és utána haladva tovább a többiek felé. Pl. (5, 7) < (6, 3), mert az 5 kisebb mint a 6, tehát az első elem alapján eldőlt. Ugyanakkor (5, 7) > (5, 2), mert az első elempár megegyezik (az 5-ösök), ezért megnézi a másodikat is, és 7 > 2. Ezt a módszert lexikografikus sorrendnek nevezzük (lexicographical order).

Jelen esetben ez a helyezések szerinti sorrendet jelentette, mert a helyezést tettük a tuple elejére. Kivétel a negyedik helyet, ahol holtverseny alakult ki, ott pedig ábécé szerinti sorrendet kaptunk.

Az enumerate() függvény tárolók bejárásában segít. (Valójában ez egy konstruktor, az enumerate osztály konstruktora, de ez a használat szempontjából lényegtelen.) Ennek segítségével egy tárolót úgy járhatunk be a for ciklussal, hogy az indexeket is látjuk. A működés azon alapszik, hogy az enumerate egy iterálható tárolót ad, amelyből tuple típusú objektumokat kapunk. Ezek első eleme egy index, második pedig az érték:

szavak = ["alma", "körte", "barack"]
for t in enumerate(szavak):
    print(t)

(0, 'alma')
(1, 'körte')
(2, 'barack')

Láthatóan itt a kiírt elemek tuple típusúak lettek, párban mutatják az indexet és a tárolt értéket.

Általában ezt úgy használjuk, hogy a for ciklus fejlécében, a változónevet megadó helyen két változónevet adunk meg, vagyis egyből egy tuple-t. Ezt zárójelek nélkül szokás írni.

szavak = ["alma", "körte", "barack"]
for index, szo in enumerate(szavak):
    print(f"{index}. szó: {szo}")

0. szó: alma
1. szó: körte
2. szó: barack

Lényeg tehát az, hogy így for ciklussal iterálhatunk, és indexeket is látunk!

A Python nyelv beépítve tartalmaz egy halmaz típust, a set osztályt. Ez támogatja a szokásos halmazműveleteket: betehetünk, kivehetünk egy elemet, illetve képezhetjük a halmazok metszetét, unióját is.

s = set(["magyar", "angol", "német"])  # 3 elemű halmaz
s = {"magyar", "angol", "német"}
s = set()           # üres halmaz, vigyázat: {} mást jelent!

# lekérdezések: eleme-e, nincs benne
print("angol" in s)
print("japán" not in s)

# módosítók: betesz, kivesz
s.add("olasz")
s.remove("német")

# halmazműveletek: metszet, unió, különbség, delta
s1 & s2
s1 | s2
s1 - s2
s1 ^ s2

A halmazműveletek láthatóan úgy működnek, hogy az osztály megfelelő operátorait megvalósították. Mivel a matematikában használt metszet ∩ és unió ∪ operátorok itt nem léteznek, helyettük az & ÉS, illetve a | VAGY operátorok használatosak. Ezt könnyű megjegyezni: az & ÉS operátor adja a metszetet: olyan elemeket keres, amelyek benne vannak az első ÉS a második halmazban benne vannak. A | VAGY operátor pedig az uniót adja, olyan elemeket keresve, amelyek az első VAGY a második halmazban szerepelnek. A - különbség magától értetődő. A ^ (kalap, angolul caret) operátorral jelölt delta műveletet viszonylag ritkán használjuk. Ez azokat az elemeket adja, amelyek csak az egyik, vagy csak a másik halmazban szerepelnek (mint az XOR művelet).

A feladatunk a következő – valójában ismerős laborról. Kapunk két szövegfájlt, amelyek egy-egy közlekedési járat megállóinak neveit tartalmazzák. A kérdésünk az, hogy át lehet-e szállni egyik járatról a másikra, azaz van-e közös megálló. Ha nincs, akkor nem lehet átszállni. De akár az is előfordulhat, hogy a két járat több helyen találkozik, vagy néhány megállón keresztül párhuzamosan haladnak, ilyenkor több átszállási lehetőség is van.

Déli pályaudvar
Széll Kálmán tér
...
Deák Ferenc tér !
...
Örs vezér tere

Újpest-Központ
...
Deák Ferenc tér !
...
Határ út
Kőbánya-Kispest

Ha rájövünk a matematikai modellre, akkor a feladat megoldása nagyon egyszerű. Valójában két halmaz közös elemeire kérdez rá a feladat, azaz a megállónevek, mint halmazok metszetére. Így a dolgunk csak annyi, hogy a két járat adatait beolvassuk egy-egy halmazba, és a halmazokat metsző & operátor megadja az eredményt.

with open('m2.txt') as f:
    m2 = {line.rstrip('\n') for line in f}
with open('m3.txt') as f:
    m3 = {line.rstrip('\n') for line in f}

print(m2 & m3)

A fájlok beolvasása iterálással történik: a for line in f kifejezéssel megkapjuk a fájl egyes sorait. Tudjuk, hogy ezeknek a végén ott van az újsor karakter: \n, így azt még levágjuk. A {... for line in f} kifejezések tulajdonképpen ugyanolyan leképezést adnak meg, mint amiket a listáknál láttunk. A példán azt is megfigyelhetjük, hogy az így előálló sztringeket nem feltétlenül kell listába tenni (akkor szögletes zárójelpárba [] csomagoltuk volna a kifejezést), hanem mehetnek halmaz típusú tárolóba is (kapcsos zárójelpár {}). Így a beolvasás után a metszetet egyből megkaphatjuk.

{'Deák Ferenc tér'}

Milyen gyors a halmaz?

A halmazműveletek viszonylag gyorsak. A halmaz mögött hash tábla van, így az eleme-e művelet átlagosan O(1), azaz konstans időben elvégezhető. A metszet, unió és további műveletek pedig átlagos esetben lineárisak.

Mi tehető bele?

Eleme lehet bármi, ami hash-elhető. Ehhez a hash() függvényt használja.

hash(123)       # egész szám
hash(456.78)    # valós szám
hash("almafa")  # sztring
hash((1, 2))    # tuple

A hash() függvény a beépített típusokat mind ismeri, és tud hozzájuk olyan egész számot rendelni, amelyik jól szórja majd a hash táblában azokat. Kérdés, hogy mi a helyzet akkor, ha saját típust szeretnénk használni. Mi történik, ha törteket tennénk a halmazba, vagy pontokat? Alapértelmezés szerint a halmaz az objektumok identitására fog figyelni, vagyis elvileg így betehetnénk két olyan tört objektumot a halmazba, amelyeknek értéke megegyezik (pl. mindkettő 1/2), de az identitásuk nem (két különálló objektum).

Hasonlóan a beépített str() függvényhez és az operátorokhoz, a hash() függvény viselkedése is megadható a saját osztályainkhoz. Ez azt jelenti, hogy létrehozhatunk egy új típust (pl. tört, pont, dátum, ...), és azokhoz is a hash() függvény hozzá tud rendelni majd egy egész számot – és ha így van, akkor olyan elemeket is használhatunk majd a halmazban.

Hogy írunk meg egy ilyet? Az objektumunk tartalmát vizsgálva elő kell állítanunk egy olyan számot, amelyik indexnek használható a hash táblában. Ez egy egész szám kell legyen, amelyik jól szórja majd az adatokat. Szerencsére ehhez a hash függvények rejtelmeiben nem kell elmerülnünk, elég, ha visszavezetjük az adatainkat egy olyan típusra, amelyik beépítetten, „gyárilag” már hashelhető. Legegyszerűbb ilyen típus a tuple. Tehát ha pl. hashelhetővé szeretnénk tenni a racionális szám osztályunkat, akkor hasheljük a (számláló, nevező) tuple-t. Ha egy dátumot, akkor hasheljük az (év, hónap, nap) tuple-t, és már készen is vagyunk.

Egy dologra figyelnünk kell: arra, hogy a hash táblában ütközés is lehet. Ezért nem csak a __hash__() függvényt, hanem az egyenlőségvizsgálatot, vagyis az __eq__() operátort is meg kell valósítanunk (a == b). Ezzel keres a halmaz, amikor ütköző hash értékű elemek között kell kutakodnia (egy vödörben), ahogyan az Algoritmusok és gráfok tárgyból is szerepelt.

import math

class Tort:
    def __init__(self, szaml, nev):
        lnko = math.gcd(szaml, nev)
        self.szaml = szaml // lnko
        self.nev = nev // lnko

    def __hash__(self):
        return hash((self.szaml, self.nev)) # tuple!

    def __eq__(a, b):
        return a.szaml == b.szaml and a.nev == b.nev

s = {Tort(10, 12), Tort(3, 4), Tort(3, 4)}
print(len(s))               # 2
print(Tort(20, 24) in s)    # True
print(Tort(1, 2) in s)      # False

A fenti példában a halmazba látszólag három elemet teszünk, de az valójában csak két különböző szám, mert a második és a harmadik objektum értéke ugyanannyi: 3/4. A két egyforma törtben a számlálók és nevezők is egyformák lettek, bár két különálló objektumról van szó. Viszont a hash értékek is ugyanazok, mert úgy definiáltuk a __hash__() függvényt, hogy az objektumok értékét, a számlálót és a nevezőt vegye figyelembe. Hasonló a helyzet a keresésnél: 20/24 valójában megegyezik a 10/12-vel, mert mindkettőnek 5/6 az értéke, így az in operátor megtalálja azt a halmazban. Az 1/2-t nem, de azt be sem tettük.

A lista (tömb) adatokat tárol. Az egyes eltárolt adatelemek a listában sorban vannak: megőrzik azt a sorrendet, ahogyan betettük őket. Az elemekre hivatkozni pedig indexekkel tudunk, indexekkel jelöljük meg, melyik elemre van szükségünk. Ezek mindig természetes számok, 0-tól a lista mérete–1-ig.

Néha az eltárolandó adatainkat máshogy szeretnénk elérni. Vegyünk példának egy bevásárlólistát. A táblázat azt az információt tárolja, hogy miből mennyit szeretnénk venni. Az egyes sorok sorrendje lényegtelen, mert bármilyen sorrend esetén végül ugyanazok a termékek kerülnének a kosarunkba. Keresni mindig a tétel neve szerint fogunk a táblázatban; az adat, amire kíváncsiak leszünk, az pedig vásárolandó mennyiség. Más szempont szerinti keresés nem érdekel minket. Például nem keressük az A betűvel kezdődő termékeket, mert a boltban nem ábécében vannak elrendezve. Nem kérdezzük azt, hogy miből kell öt kg-ot venni, mert haszontalan kérdés, nem segít a kosár tartalmának összeállításában.

Keresések

• Mennyi almát kell venni?
• Mennyi dinnyét kell venni?
• Miből kell öt kg-ot venni? Haszontalan kérdés.

Az itt látható tároló kulcs–érték párokat tárol (key, value). Ennek lényege, hogy egy adott kulcs (itt a gyümölcs neve) alapján szeretnénk könnyen és gyorsan megtalálni az ahhoz tartozó értéket (itt a mennyiség). A kulcsnak egyértelműen azonosítania kell a táblázat egyik sorát, vagyis minden kulcs legfeljebb egyszer szerepelhet a táblázatban. Nem írunk bele olyat, hogy almából 2-t és megint csak almából 1-et vennénk, mert akkor nem lenne egyértelmű, mennyit kell vásárolni. Ugyanakkor az értékek többször is szerepelhetnek, hiszem előfordulhat, hogy két különféle termékből ugyanannyi darabra van szükségünk.

A kulcs–érték párok tárolóját a programozásban szótárnak (dictionary) nevezzük. Ez a név onnan alakult ki, hogy a szótárban is egy konkrét szó alapján keresünk mindig, hogy megtaláljuk az ahhoz társított információt: jelentések, szinonimák, példamondatok stb. Ezeket a Python is szótárnak nevezi, a típus neve: dict. Más programozási nyelvek esetén gyakori a map elnevezés is, mert a tároló leképezi (mapping) a kulcsot az értékre.

Pythonban egy szótár, azaz dict típusú tárolót legegyszerűbben úgy hozhatunk létre, hogy kapcsos zárójelek között felsoroljuk a kulcs–érték párokat, közöttük kettősponttal. Ez a leggyakoribb forma. A zárójelpár akár lehet üres is, és olyankor üres szótár jön létre, amelybe később tehetünk majd elemeket. (Csak zárójelben: ezért nem lehet üres halmazt, azaz set típusú tárolót kapcsos zárójelekkel létrehozni. Amikor már van legalább egy elem, egyértelművé válik, melyikről van szó: ha kettőspontok is vannak, akkor szótárról, ha nincsenek, akkor halmazról.)

bevasarlolista = {
    "alma": 2,      # kulcs: hashelhető
    "körte": 1,
    "barack": 5,
}

Üres szótárat a dict() konstruktorhívással, vagy egyszerűen egy üres kapcsos zárójelpárral tudunk létrehozni: {}. Az egyes elemeknek a hozzáadása és elérése az indexelő operátorral történik. A második példában pontosan ugyanaz a szótár jön létre, mint az első, rövidebb szintaxist használva.

bevasarlolista = dict()     # vagy röviden: {}
bevasarlolista["alma"] = 2
bevasarlolista["körte"] = 1
bevasarlolista["barack"] = 5

Harmadik lehetőségünk, hogy megadunk egy listát, amelynek elemei a szótár tartalmát adják. Ebben az esetben a lista minden eleme egy tuple kell legyen, amelyek a kulcs–érték párokat tartalmazzák.

bevasarlolista = dict([
    ("alma", 2),
    ("körte", 1),
    ("barack", 5),
])

Az első forma egyébként pont az, ahogyan a print() függvény is megjeleníti a szótárat, vagyis ahogyan az sztringgé konvertáláskor megjelenik.

print(bevasarlolista)

{'alma': 2, 'körte': 1, 'barack': 5}

A dict egyébként belül hash táblát használ, a halmazhoz hasonlóan. Az adatelérés sebessége is ennek megfelelően a halmazéval megegyező: átlagos esetben O(1), azaz a szótárban tárolt elemek számától független. Ha saját típust használunk a szótár kulcsainak (pl. időpontot), akkor itt is figyelni kell arra, az egyenlőség mit jelent. A __hash__() és az __eq__() függvényekre szükség lehet, különben az objektumok identitására figyel a szótár.

A szótár elemeit legegyszerűbben az indexelő operátorral érhetjük el. Az indexelés lehetővé teszi az elemek írását és olvasását is – kicsit úgy érezhetjük, mintha egy listáról lenne szó, de egész számok helyett tetszőlegesen más adatokkal is indexelhetjük azt, pl. sztringgel. Törölni is ugyanúgy lehet, a del operátorral.

bevasarlolista = {
    "alma": 4,
    "körte": 1,
    "barack": 5,
}

print(len(bevasarlolista))      # 3
print(bevasarlolista["alma"])   # 4
print("alma" in bevasarlolista) # True

del bevasarlolista["alma"]
bevasarlolista["szilva"] = 7

try:
    print(bevasarlolista["papaja"])
except KeyError as e:
    print("Nincs benne")               # Nincs benne

print(bevasarlolista.get("papaja", 0)) # 0

Szintén a listához hasonlóan, ha nem létezik az adott kulcsú elem, a szótár is kivételt dob indexeléskor. Itt a kivétel típusa KeyError. Ha hiányzó kulcs esetén helyettesítenénk a tárolóból vett értéket egy alapértelmezettel, akkor a .get(kulcs, alapérték) függvényt használhatjuk. Jelen esetben a függvényhívás értéke 0 lesz, mert a "papaja" sztring nem szerepel a kulcsok között. Ettől ez a kulcs nem fog bekerülni egyébként a tárolóba; írni értékadással tudunk bele, a .get() nem módosítja a tartalmát.

Ha iterálni szeretnénk a szótár elemein, azaz egy ciklussal látni szeretnénk az összeset (pl. kiírás céljából), arra több lehetőségünk is van.

Az „alap” for ciklus a szótáron iterálás esetén a szótár kulcsait adja, nem pedig az értékeit. Természetesen ez az értékek elérését is lehetővé teszi, hiszen csak meg kell indexelni a tárolót: bevasarlolista[kulcs].

bevasarlolista = {
    "alma": 4,
    "körte": 1,
    "barack": 5,
}

for kulcs in bevasarlolista:    # kulcsok
    ertek = bevasarlolista[kulcs]
    print(kulcs, ertek)

for ertek in bevasarlolista.values():   # értékek
    print(ertek)
print("Összesen:", sum(bevasarlolista.values()))

for kulcs, ertek in bevasarlolista.items():   # tuple-k
    print(f"{kulcs}: {ertek} kg")

alma 4
körte 1
barack 5
4
1
5
Összesen: 10
alma: 4 kg
körte: 1 kg
barack: 5 kg

alma: 4 kg
körte: 1 kg
barack: 5 kg

Ha csak az értékekre vagyunk kíváncsiak, a kulcsok lényegtelenek, akkor a .values() függvényhívást használhatjuk. Ez egy listához hasonlóan viselkedő tárolóban visszaadja csak az értékeket. A középső példa sum() függvényhívása így összegzi, hány kg gyümölcsöt vásárolunk összesen.

Legkényelmesebb a dict bejárásakor úgy dolgozni, hogy a kulcsokat és az értékeket is látjuk a ciklusban. Ez az .items() függvényhívással érhető el. Ekkor az iterálás során tuple típusú elemeket kapunk, amelyek (kulcs, érték) formában megadják a szótár elemeit. Legjobb ezt a for ciklus fejlécében egyből kicsomagolni két változóba, ahogy az enumerate() kapcsán is láttuk.

Feladat: készítsünk szavakról statisztikát! Melyik hányszor szerepel?

Emlékezzünk vissza a bináris fák kapcsán erre a példára! A beolvasott szavakból egy keresőfát építettünk, egyrészt azért, mert nem tudtuk előre, hány darab lesz, másrészt pedig mert gyorsan meg akartuk őket találni. Minden szó csak egyszer került be a fába, és minden szó mellé egy darabszámot jegyeztünk föl.

A fával tehát egy kulcs–érték párt építettünk tulajdonképpen. A dict ismeretében egyszerűbben is megoldható a feladat, hiszen az pont ezt tudja: adott kulcsok ismeretében eltárolni az azokhoz rendelt értékeket, és azokat gyorsan visszakereshetővé tenni. A kulcsok itt a szavak, az értékek pedig az előfordulások számai lesznek.

A feladat megoldása a dict segítségével ilyen rövid:

alma
alma
körte

alma: 2 db
körte: 1 db

elofordulas = {}

szo = input()
while szo != "":
    if szo in elofordulas:
        elofordulas[szo] += 1
    else:
        elofordulas[szo] = 1
    szo = input()

for szo, db in elofordulas.items():
    print(f"{szo}: {db} db")

Figyelnünk kell arra az esetre, amikor a szó még nincs a szótárban. Ilyenkor a kiolvasó indexelés KeyError hibát dobna, és csak írni szabadna (új adatot betenni) arra az indexre. Márpedig a += 1-es sor kiolvasást is tartalmaz, a meglévő értékhez adnánk hozzá 1-et. Ezért bekerült a kódba egy esetszétválasztás: ha a szót már láttuk, vagyis szerepel kulcsként (szo in elofordulas), akkor növelhető a hozzá tartozó számláló. Ha még nem, akkor az egy első előfordulás, és 1-et teszünk a tárolóba.

Mindez lecserélhető akár egyetlen egy sorra is. A .get(kulcs, alapérték) úgy keres ki egy elemet a szótárból, hogy az alapértéket adja vissza, ha nincs meg a keresett kulcs. Ha 0-nak tekintjük az alapértéket, az pont jó lesz ebben az esetben. Ha nem szerepelt még a szó, akkor az addigi előfordulásai 0-nak számítanak, és ahhoz adunk 1-et hozzá. Ha már szerepelt, akkor az addigi előfordulások számához.

elofordulas[szo] = elofordulas.get(szo, 0) + 1

sor (queue, FIFO)

verem (stack, LIFO)

A láncolt listák kapcsán már szóba jöttek a várakozási sorok és a vermek.

A várakozási sor (queue) olyan sorozattároló, amelynek mindig az egyik végén szúrunk be új adatot, és mindig a másik végéről veszünk el belőle. Az előbbit a sor végének, az utóbbit a sor elejének nevezzük, a hétköznapi várakozási sorok (pl. pénztárgépnél) analógiájára. Várakozási sorban tárolhatunk feldolgozandó adatokat is, ha azokkal a beérkezésük sorrendjében szeretnénk foglalkozni. A sort FIFO-nak is nevezzük, az angolban first in, first out kifejezéssel leírt működés miatt: amelyik elem legelőször bekerült a sorba (first in), az fog először kikerülni onnan (first out). Láttuk azt is, hogy várakozási sort pl. láncolt listával lehet megvalósítani hatékonyan.

A verem (stack) szintén sorozatot tárol, de ezt az egyik végén módosítjuk csak. Amelyik elemet legutoljára betettük (last in), az kerül ki onnan először (first out), innen a LIFO rövidítés. A legutoljára betett elemet, azaz a sorozatnak azt a részét, ahol módosítani lehet azt, a verem tetejének nevezzük (top); a betesz–kitesz műveleteket pedig angolul a push és pop igék jelölik.

kétvégű sor (deque, double ended queue)

Az előbbi két tárolót általánosítja a kétvégű sor (double ended queue). Ennek a nevét angolul deque-nak szokás rövidíteni (ezt a szót „dekk”-nek olvassuk). Ennek az elején is lehet betenni–kivenni elemet, meg a végén is. Mivel így a két szélső elem tulajdonképp egyformán kezelhető, néha nem is a sor elejéről és végéről, hanem a bal és jobb oldaláról beszélünk.

Ha van egy kétvégű sorunk, akkor az szükség esetén akár használható sima várakozási sornak vagy veremnek is, olyan módon, hogy bizonyos műveleteit használjuk csak. Több programozási nyelv (pl. C++, Python) várakozási sora az elemek indexelésére is képes, azaz egy adott sorszámú elemet is elérhetünk bennük, akár a tároló közepéből. Ezeknél a tárolóknál a két végük módosítása O(1) lépésszámú algoritmussal szokott történni, a középen lévő elemek elérése azonban ennél sokkal lassabb lehet, O(n) lépésszámú, ahol n a sor hossza. Ezért ha szükségünk van gyakran a közbenső elemekre, akkor lehet jobb ötlet egyszerű listát (tömböt) használni, mert ott az indexelés O(1) időben történik, bármelyik elemre.

A Python beépítve tartalmaz kétvégű sort: a collections modul deque osztályáról van szó. Ezt használhatjuk collections.deque néven is, vagy egyszerűen az importáláskor megjelölhetjük, hogy röviden deque néven szeretnénk elérni azt.

sor = collections.deque()

# beszúrás
sor.append("alma")          # jobbról
sor.appendleft("körte")     # balról
sor.append("barack")        # jobbról
print(*sor)  # körte alma barack

# elemek elérése, törlése
print("balról, sor[0]:", sor[0])    # balról: körte
print("jobbról, sor[-1]:", sor[-1]) # jobbról: barack
print("jobbról:", sor.pop())        # jobbról: barack
print("balról:", sor.popleft())     # balról: körte

A kétvégű sort ugyanazokkal a függvényekkel tudjuk használni, mint az egyszerű listákat: itt is az .append() és .pop() függvények tesznek be és törölnek ki egy elemet a sorból. Ezek a sor jobb oldali végét módosítják. Ha ugyanezeket a műveletek a bal oldalon végeznénk el, az .appendleft() és .popleft() függvényeket kell használni.

A sorba előbb jobbról az almát, aztán balról a körtét, végül megint jobbról a barackot szúrtuk be. Így a sorrend balról indulva körte, alma, barack lett:

körte alma barack
balról, [0]: körte
jobbról, [-1]: barack
jobbról: barack
balról: körte

Az alábbi csoportosítás az eddig megismert, beépített tárolókat mutatja be használatunk szerint.

Sorozattárolók

• list: egész számmal indexelt
• deque: mindkét végén gyorsan módosítható, sor vagy verem
• tuple: immutábilis, „ad-hoc objektum”

Asszociatív tárolók

• set: halmaz
• dict: kulcs–érték pár

Ez a csoportosítás kétféle tárolót különböztet meg, ahogy azt a listás előadásnál is láttuk: a sorozattárolókat és az asszociatív tárolókat. A sorozattárolók megőrzik az elemek sorrendjét, cserébe általában lassabban lehet keresni bennük. A különbség abban rejlik közöttük, hogy melyiket hogyan lehet módosítani, mely speciális esetekre vannak kihegyezve. Például a listák jól (gyorsan) kezelik az indexelést, a kétvégű sor pedig az elején/végén beszúrást is hatékonyan képes kezelni.

Az asszociatív tárolókban kulcs szerint tudunk keresni. Azaz itt nincsen az elemekhez hozzárendelt index, hanem az elem értéke, tartalma alapján lehet megtalálni azt. A halmazban lényegében csak kulcsok vannak, a szótár pedig ezekhez valamilyen értéket is enged társítani.

Gráfok tárolása

A gráfok alkalmazásairól sok szó esett az Algoritmusok és gráfok tárgyon. Jelölhetik a gráfok csúcsai a városokat, az éleik a közöttük futó utakat. Vagy jelölhetnek a csúcsok felhasználókat, az élek pedig azt, hogy ki kit ismer, mint egy közösségi portálon. Esetleg a csúcsok jelölhetnek függvényeket, az élek pedig azt, hogy melyik függvény melyik másik függvényeket hívja meg; egy ilyen gráf sokat segíthet abban, hogy egy nagy programot áttekintsünk. Vagy a csúcsok egy játékban, pl. sakkban egy játékállást reprezentálnak, az abból kiinduló élek pedig olyan csúcsokba vezetnek, amelyek egy játéklépéssel elérhetőek.

Most a konkrét alkalmazásokkal nem fogunk foglalkozni, csak azzal, hogy a gráfos algoritmusokat, a tárolást és a bejárásokat hogyan valósíthatjuk meg Pythonban. Az ábrázolások (tárolási módszerek) közül is most először csak az éllistás tárolással foglalkozunk (adjacency list), méghozzá egyszerű, irányított gráfokra.

Az éllistás ábrázolásban a csúcsokat megszámozzuk, és betesszük őket egy tömbbe. A tömb minden eleme tehát egy csúcs, és a tömbelemek indexeivel hivatkozni tudunk rájuk. Az egyes csúcsokhoz tartozóan az azokból kiinduló éleket pedig listába tesszük. A fenti gráfon az A jelű csúcsból indul él a B és a C jelű csúcsba; ezért az A csúcs adatait tartozó 0. tömbelem éllistájában szerepel az 1-es és 2-es szám, vagyis onnan indul él az 1-es indexű (B) és a 2-es indexű (C) csúcshoz. C-ből nem megy él sehova, ezért a C csúcs éllistája üres.

Éllistás reprezentáció

Éllistás reprezentáció,
Python sajátosságokhoz igazítva

Miért különböztetjük meg a csúcsok tömbjét és az élek listáját? Mi a jelentősége annak, hogy az egyiknél tömböt, a másiknál listát mondunk? Ha a gráf módosítására gondolunk, akkor hamar megjelenik a különbség. Új élt könnyű behúzni és törölni, a módosítás nincsen hatással a gráf reprezentációjának, vagyis az adatszerkezetnek a többi részére.

Ha azonban a csúcsokat szeretnénk módosítani, főleg, ha egy csúcsot szeretnénk törölni, akkor már nem ilyen egyszerű a feladat. Tegyük fel, hogy a B csúcsot szeretnénk törölni a gráfból, értelemszerűen a belőle kiinduló és az őt célba vevő élekkel együtt. Ehhez nem elég csak simán törölni az 1-es indexű tömbelemet. Ezen felül két további dolgunk is van még:

• Végig kell néznünk az összes éllistát, hogy van-e valahol hivatkozás az 1-es csúcsra (az volt a B). Ha igen, akkor azt is törölni kell.
• Bár a gráfban a csúcsoknak nincs sorrendje (halmaznak tekintjük őket), ebben az ábrázolásban van, mert az éllisták indexek szerint hivatkozzák a csúcsokat. Amiatt is végig kell néznünk a listákat, hogy a B utáni csúcsok indexei megváltoztak. A C csúcs 1-es indexűvé, a D csúcs 2-es indexűvé változik a törlés által, vagyis az összes B utáni csúcs indexei eggyel csökkennek. Ezt a módosítást is végig kell vezetnünk mindenhol.

Emiatt a csúcsok tárolóját fix méretűnek, tömbnek szoktuk tekinteni, az élek listáját pedig változtathatónak, láncolt listának. A csúcsok tömbjében számít a sorrend is (mert az élek sorszám szerint hivatkoznak rájuk), az élek listájában viszont lényegtelen. Nem megoldhatatlan, de hosszadalmas feladat a csúcsok átszámozása.

Tömböt Pythonban a list típussal szoktunk létrehozni, mert ez lehetővé teszi az objektumaink hatékony elérését és indexelését. Érdemes ugyanezt a típust használni az élek listájához is, mert tudjuk, hogy néhány speciális esettől eltekintve (elejére beszúrás, elejéről törlés) ez a leghatékonyabb tároló. Vagyis mindkettőhöz a Python listát használjuk majd.

A gráf tárolására három osztályt definiálunk: a gráfot, a csúcsot és az élt.

class Graf:
    def __init__(self, nev=None):
        self.nev = nev
        self.csucsok = []

class Csucs:
    def __init__(self, nev=None):
        self.nev = nev
        self.elek = []

class El:
    def __init__(self, cel, suly=None):
        self.suly = suly
        self.cel = cel

g = Graf("Térkép")
g.csucsok.extend([Csucs("A"), Csucs("B"), Csucs("C")])
g.csucsok[0].elek.extend([El(1, 10), El(2, 15)])

A Graf osztályunk egy gráf adatait tartalmazza. Az algoritmusok szempontjából leglényegesebb persze a csúcsokat tároló list lesz, de a gráf további adatokat is tartalmazhat, pl. a gráf nevét, vagy amit szeretnénk.

Ugyanez a helyzet a Csucs osztállyal. Az éllista mellett bármilyen adatokat tartalmazhat, jelen esetben ez is egy nevet. Alul látszik is, hogy konstruktorban megadhattuk a csúcsok neveit, így a programban is ugyanaz az A, B és C címke jelöli meg a csúcsokat, mint a rajzon.

Harmadik osztályunk az El. Ennek kötelező adattagja a cél (hova, hányas indexű csúcsba fut az él a gráfban), és az előzőekhez hasonlóan adatokat is tartalmazhat, például az él súlyát.

A gráf felépítése a két lista kitöltéséből áll. (A listák .extend() függvénye olyasmi, mint az .append(), de nem egy, hanem több elemet is hozzá tud adni egyszerre.) Egy dologra kell csak figyelni, az élek indexeire. A példában az A, B, C csúcsokat adtuk hozzá a gráfhoz, tulajdonképp itt kapták meg azok a 0, 1, és 2 indexeket.

g.csucsok[0].nev             # A
g.csucsok[0].elek[1].suly    # A → C, 15

Ezekkel az osztályokkal és adattagokkal elértük azt, hogy a gráf adatait szemléletesen, könnyen érthető kifejezésekkel elérjük. Pl. a g.csucsok[0].nev az első csúcs nevét adja, jelen esetben A-t. A g.csucsok[0].elek[1].suly az egyik él súlyát adja meg, amelyik ebből a csúcsból indul ki – az A → C élről van szó.

A legfontosabb gráfos algoritmusok a gráfbejárások.

A mélységi bejárásban (depth-first search, DFS) mohón haladunk előre az élek mentén addig, ameddig csak lehet, és csak utána fordulunk vissza. Vagyis nem egy csomópont összes élét, összes szomszédját vizsgáljuk előbb, hanem ahogy meglátunk egy szomszédot, egyből megyünk is arra tovább, amíg csak lehet.

A mohó haladás az élek mentén nagyon egyszerűen megvalósítható rekurzióval. Ahogy találunk egy élt v csúcsból w-be, rögtön rekurzívan meghívjuk a bejárást arra a csúcsra, amelyikbe az vezet – így a v csúcsból induló további élek csak akkor fognak sorra kerülni, ha ez a rekurzív hívás már visszatért.

mélységi_bejárás(v):
    v-t bejártnak jelölni
    MINDEN v → w élre:
        HA w nincs bejárva:
            mélységi_bejárás(w)    rekurzió
            <tevékenység v → w élre>
    <tevékenység v csúcsra>

bejárva = ∅
mélységi_bejárás(s)     indítás s-ből

A bejárás közben valamilyen tevékenységet elvégezhetünk a csúcsokra és az élekre is. Pl. kiírhatjuk a csúcsokban tárolt adatot, feljegyezhetjük, milyen úton jutottunk el egy csúcshoz és így tovább. Ezekkel most nem foglalkozunk, csak a pszeudokódban jelöltük a helyüket.

A gráf, amelyet bejárunk, nem biztos, hogy fa. Tehát előfordulhat, hogy egy csúcsba több úton is eljutunk. Erre figyelni kell, mert a bejárásban nem akarunk egy csúcsot többször feldolgozni. Például az alábbi gráfban a 0-s csomópontból két úton is eljuthatunk a 4-es csomóponthoz: a 0→4 éllel közvetlenül, továbbá a 0→1→4 úton is.

A meglátogatott csúcsok megjelölésére azért is szükség van, mert kör lehet a gráfban. Ha erre nem figyelnénk, akkor az élek mentén körbe-körbe mennénk a gráfban, soha nem állna meg az algoritmus. Ez történne a 0→2→5→0 körön. Emiatt tudnunk kell valamilyen módon, hogy melyik csúcsnál jártunk már, és melyiknél nem. A pszeudokód vonatkozó sorai:

v-t bejártnak jelölni
HA w nincs bejárva

Vajon milyen adatszerkezetet használhatnánk ennek a tárolására? Lehetőségeink:

• Tömb: bejárva = [False] * len(csúcsok)
• Halmaz: bejárva = set()
• Szótár: bejárva = dict()
• A csúcsnál: graf.csucsok[v].bejarva

Megoldhatjuk a problémát egy tömbbel (Pythonban: listával). A tömböt kezdetben csupa Hamis értékekkel inicializáljuk, és amikor bejártnak jelölünk egy csúcsot, akkor a hozzá tartozó indexre Igaz értéket kell tenni. Ha a teljes gráfot be szeretnénk járni, akkor praktikusabb a tömbös megoldást választani, mert hatékonyabb lesz. Előre tudjuk, ennek a tömbnek hány eleme van: annyi, amennyi csúcsa a gráfnak.

A halmaz típus is adja magát erre a feladatra. Jártunk-e egy adott helyen: bent van-e a csúcs indexe a halmazban. Végül pedig, eszünkbe juthat a szótár típus. Ebben is ellenőrizni tudjuk, egy adott kulcs szerepel-e a szótárban vagy nem. De itt a kulcsokhoz értékeket is tárolhatunk; valamilyen adatot feljegyezhetünk bejárás közben minden csúcshoz. Pl. honnan érkeztünk oda; hány lépés kellett, hogy eljussunk oda, és így tovább.

Megoldás lehet az is, ha ezt az információt egyszerűen a csúcsnál tároljuk, vagyis a Csucs osztályban létrehozunk erre egy adattagot. Ez nem a legszebb megoldás, de egyszerűsége miatt néha szokták ezt a módszert alkalmazni.

A bejárt elemek nyilvántartásához most halmazt használunk.

A bejáró függvényünk, a melysegi_bejaras_seged() rekurzív. Ez fontos a bejárt elemeket tároló halmaz szempontjából: akármilyen távolra megyünk az eredeti csúcstól, tehát akármelyik rekurzív hívásról van szó, a bejárt csúcsok indexeit tároló halmaz objektumból csak egy példány kell legyen.

Ezt megoldhatnánk úgy is, hogy mindig paraméterként adjunk neki a halmazt, amivel dolgoznia kell, de van ennél jobb megoldás is, mégpedig a következő. A „külső” függvényben, a melysegi_bejaras()-ban létrehozzuk a halmazt. Továbbá definiálunk azon belül egy újabb függvényt, amelyik a bejárást végző rekurzív függvény lesz. Ez látja a külső függvény által definiált változót, és a külső függvény paramétereként látszó gráfot is. Paramétere így csak egyetlen egy kell legyen, a csúcs sorszáma, ez pedig a v nevű.

def melysegi_bejaras(graf, start):
    def melysegi_bejaras_seged(v):
        bejarva.add(v)
        print(graf.csucsok[v].nev) # v csúcs
        for el in graf.csucsok[v].elek:
            w = el.cel
            if w not in bejarva:
                melysegi_bejaras_seged(w) # v→w él

    bejarva = set()
    melysegi_bejaras_seged(start)  # vagy az összesből

Egyébiránt az algoritmus egy az egyben a pszeudokódot valósítja meg, igazítva a gráf felépítéséhez használt típusainkhoz: a Graf, Csucs és El osztályokhoz.

def melysegi_bejaras(graf):
    def melysegi_bejaras_seged(v):
        # ...

    bejarva = set()
    for start in len(graf.csucsok):
        if start not in bejarva:
            melysegi_bejaras_seged(start)

További bejárásokról, pl. a szélességi bejárásról egy külön írásban lehet olvasni.

Az előadáson megismertek alapján:

• Tudni kell list comprehension-t használni.
• Tudni kell tuple-t használni.
• Ismerni kell az enumerate() használatát.
• Tudni halmazt létrehozni, lekérdezni, halmazműveleteket elvégezni.
• Tudni kell szótárt létrehozni, használni, enumerálni.

A gráfok bejárása kiegészítő, ismeretbővítő anyag.