# Összetett adatszerkezetek

Czirkos Zoltán · 2025.11.20.

List comprehension kifejezések. A set és a dict típus. Vermek és sorok.

# List comprehension

## 2. Listák feldolgozása

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:

Általában
ilyen formájú

    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.

## 3. A list comprehension kifejezés

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]

Vagyis három elemet kell megadnunk:

- Leghátul a lista van, amit fel szeretnénk dolgozni.
- Középen egy változónév, amelyiken keresztül a lista elemeit látjuk. Vegyük észre, hogy az egész list comprehension kifejezés hátsó része teljesen úgy néz ki, mint egy szokványos `for` ciklus, vagyis `for változónév in lista`.
- Legelöl pedig az a kifejezés, amit minden listalemre ki kell értékelni. Ezt nevezhetjük leképezésnek is.

Ezt az egészet pedig becsomagoljuk egy szögletes zárójelpárba, ezzel jelezve, hogy egy listába kerülnek az adatok.

## 4. Szűrés list comprehension kifejezéssel

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:

Csak a
pozitívak

    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.

## 5. Példa: prímszámok 100-ig

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]

## 6. Példa: többdimenziós lista

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:

Nem működik
helyesen

    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

Észrevehetjük, hogy a belső ciklus egy üres listából indulva `.append()`-elgeti a nullákat addig, amíg a megfelelő számú elem nem került a listába. Ez lehet egy list comprehension kifejezés: `range(w)`-szer kell venni, bár nem is a számokat, hanem a nullát. De az elejére írhatunk konstanst is. Vagyis:

    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

Ez tehát létrehozza majd a sorokat, amik mindig új listák lesznek, 0-kkal feltöltve. Megfigyelve a mátrixot, ismét egy olyan kódrészletet látunk, amelyik tökéletes jelölt arra, hogy rövidítsük az eddig megismert módon. `h`-szor kell ugyanis új sort létrehozni, minden alkalommal kiértékelve a `[0 for _ in range(w)]` kifejezést. Vagyis:

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

Kész a mátrixunk. Mivel sehol nem használtuk a változók értékeit – nem volt lényeges, hogy hányadik sorban vagy oszlopban vagyunk, mert attól függetlenül 0-t vagy egyforma sorokat akartunk a listába tenni –, ezért a változónevek mindkét helyen csak alulvonással jelöltek: `_`.

## 7. Példa: gyorsrendezés

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.

41 30 10 28 57 72 68 97 81

    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.

## 8. Háttérben: iterálható objektumok

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.

A `for` ciklusban használható tárolókat, vagy tárolóként viselkedő objektumokat iterálható objektumoknak nevezzük (iterable). Ezek olyan osztályból valók, amelyeknek definiáltak `__iter__()` függvényt. Ennek részleteibe nem megyünk bele: nem fér bele az időbe, és objektumorientált programozással kapcsolatos vonatkozásai vannak, amelyekről a második félévben, az Objektumorientált programozás c. tárgyban lesz szó.

A list comprehension kifejezés egyébként valójában nem az egész kódrészlet, amit leírtunk; valójában csak a szögletes zárójelek közötti rész hoz létre olyan objektumot, amelyik a műveleteket (leképezés, szűrés) végzi. A szögletes zárójel csak annyit jelent, hogy a keletkező értékeket egy listába tesszük be. Ha helyette pl. kapcsos zárójelpárt használnánk, akkor nem lista, hanem halmaz jönne létre. (Halmazokról lásd lentebb.)

# Beépített adatszerkezetek

## 10. Tuple

Gyakran egy programhelyen több adatunk egymás mellé kerül, sokszor csak ideiglenesen. Például szeretnénk egy két visszatérési értékű függvényt csinálni, amelyik megkeresi egy lista minimumát ÉS maximumát is egyszerre. Vagy számpárokkal dolgoznánk, amelyek listák tartományait (kezdő index, befejező index) jelölik meg. Esetleg egy pont koordinátáit tárolnánk (x, y koordináta), de nincs szükségünk sztringgé alakításra, operátorokra, semmi egyébre, ami miatt fontosnak tartanánk egy külön osztályt definiálni.

Ilyen esetben szükségünk van egy tárolóra. De az nem egy lista, mert az kicsit mást jelent: a listában változhat az elemek száma, és megcserélhetőek. A fenti két visszatérési értékű függvényben ez nem igaz: ott az első visszaadott adat a lista minimuma, a másik a maximuma – ezek nem megcserélhetőek (más a jelentésük), és nem változhat a számuk (mindig kettő lesz). Valami más dologról van szó.

### 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

### Mire jó?

- „Ad-hoc objektum”
- Több visszatérési értékű függvény
- Számpárok, pl. indextartomány listában
- Tárolóban index és érték
- Módjával! Mi az, hogy `(5, 9)`?

Ha nem akarunk osztályt létrehozni, akkor egy `tuple` típusú objektumra van szükségünk. A tuple neve magyarul rendezett n-es. (Angolul pedig a tuple szó kiejtése nem „tápl”, hanem „tjúpl”, ezt a legtöbben rosszul mondják. Bár ebben a videóban natív angolul beszélő emberek mondják többféleképpen. Mindenki úgy ejti, ahogy tetszik neki, csak jól használja.)

A `tuple` típusú objektumot a kerek zárójelben felsorolt, vesszővel elválasztott értékekkel hozzuk létre. Az egyes adatokat pedig indexeléssel érjük el, `t[0]` az első adatelem (itt `5`), `t[1]` pedig a második (itt `7`). A `tuple` típusú objektumok immutábilisak; a bennük tárolt referenciák nem változhatnak, sem a számuk, sem az értékük.

A tuple fogalommal algoritmuselméletben, Algoritmusok és gráfok tárgyban is sokat találkozhatunk. A matematikában tuple-nek nevezünk minden olyan „adatcsomagot”, ahol egyszerre több adatot tárolunk egy adatszerkezetben. Gyakran ott az osztályhoz és objektumhoz hasonló értelemben használjuk, mert az algoritmusok leírásánál nem lényegesek a programozási technikák (pl. operátorok definíciója, konstruktorok és társaik). Pythonban ezeket megkülönböztetjük: itt kifejezetten csak akkor szoktunk tuple-ről beszélni, amikor a fentihez hasonló zárójeles kifejezéssel ilyen objektumot hozunk létre.

Fontos, hogy a `tuple` típust csak módjával használjuk, ne erőltessük! Akkor érdemes használni csak, ha lokalizált a kódban: ha közel van egymáshoz a létrehozása és a használata. Ha elkezdünk ide-oda passzolgatni a programunkban `tuple` objektumokat, előbb-utóbb nem fogjuk tudni, mit jelentenek. Mi az, hogy `(5, 9)`? Egy pont x és y koordinátája? Egy tört számlálója és nevezője? 5 óra 9 perc? Ha definiálunk az adataink tárolására osztályokat, akkor ez egyértelmű, mert az objektumoknak ismerjük a típusát is: `Tort(5, 9)` és `Pont(5, 9)`. Ha így teszünk, függvényeink, operátoraink is lehetnek ezekhez az adatokhoz. Név szerint el tudjuk majd érni az adattagokat (számláló, nevező, x, y), nem kell sorszám szerint hivatkozni rájuk.

## 11. Tuple: összetett paraméter és fv. érték

Í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.

## 12. Tuple zárójelek nélkül?

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

Sok Python beépített osztály és modul használ tuple típusú paramétereket. Pl. a teknőcgrafikában a színt mindig egy paraméterrel adjuk meg. Az a paraméter lehet egy sztring is (a szín angol neve), vagy egy tuple is, amely a szín vörös, zöld, kék komponensét adja meg. Miért ilyen sorrendben? Mert ez a szokás:

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

## 13. Tuple, mint ad-hoc tároló

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.

## 14. Az enumerate() használata

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!

## 15. A halmaz típus: class set

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.

    s1 = set(["magyar", "angol", "német"])  # 3 elemű halmaz
    s2 = {"magyar", "angol", "spanyol"}      # ugyanaz, rövidebb írásmód
    s = set()           # üres halmaz, vigyázat: {} mást jelent!

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

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

    # halmazműveletek: metszet, unió, különbség, delta
    s1 & s2 # melyik az a nyelv, amit mindkettő tud?
    s1 | s2 # melyik az a nyelv, amit legalább az egyik tud?
    s1 - s2 # melyik az a nyelv, amit csak az első tud?
    s1 ^ s2 # melyik az a nyelv, amit csak az egyik tud?

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).

## 16. Van-e átszállási lehetőség?

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.

m2.txt

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

m3.txt

    Ú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'}

## 17. Milyen gyors a halmaz?

### Milyen gyors a halmaz?

A halmazműveletek viszonylag gyorsak. A halmaz mögött egy speciális adatszerkezet, az úgynevezett 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. (A hash tábla megvalósításával kapcsolatos részletek nem tartoznak szorosan a tárgyhoz, egy külön kiegészítő anyagba kerülnek.)

Művelet | Python | Lépésszám
--- | --- | ---
Eleme-e | `x in s` | O(1)
Metszet | `s & t` | O(min(len(s), len(t)))
Unió | `s | t` | O(len(s) + len(t))

## 18. A szótár fogalma

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.

Bevásárlólista: kulcs–érték párok
kulcs | érték
--- | ---
alma | 2 kg
körte | 1 kg
dinnye | 5 kg
barack | 2 kg

### 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.

## 19. Szótár (dict) létrehozása Python nyelvben

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.)

I.

    bevasarlolista = {
        "alma": 2,      # kulcs
        "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.

II.

    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.

III.

    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` elérésének sebessége 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.

## 20. A szótár elemeinek elérése

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.

## 21. Iterálás a szótár elemein

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.

## 22. Dict példa – szavak statisztikája

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

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

## 23. Vermek és sorok

sor (queue, FIFO)

verem (stack, LIFO)

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).

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.

## 24. Kétvégű sor (double ended queue, deque)

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

## 25. Tárolók: összefoglalás

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.

## 26. Összefoglalás

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.