Adatszerkezetek

Tömbök

Pythonban a 2-dimenziós tömböket listák listájával, a 3-dimenziósakat listák listájának listájával... tudjuk legegyszerűbben reprezentálni:

In [1]:
M = [[1, 2], [3, 4]]

Tömb egy elemét így érhetjük el:

In [2]:
print(M[0], M[0][1])

[1, 2] 2
In [3]:
# 3x2x2-es tömb
M = [[[1, 2], [3, 4]], [[5, 6], [7, 8]], [[0, 9], [0, 0]]]
M[2][0][1]
Out[3]:
9

Írjunk olyan függvényt, mely kiír egy 2D tömböt táblázatszerűen ilyesmi formában:

1   2
3   4
In [4]:
def tomb_kiir(M):
    for i in range(len(M)):
        for j in range(len(M[i])):
            print(M[i][j], end='\t')   # TAB karakter
        print()

Vigyázzunk, M[i, j] az M[i][j] helyett itt nem működik!

In [5]:
tomb_kiir([[1, 2, 3, 3.5], [4, 5, 6, 6.5], [7, 8, 9, 9.5]])

1	2	3	3.5	
4	5	6	6.5	
7	8	9	9.5

Bonyolultabb adatszerkezetek

Törzsvásárlói kedvezményt szeretnénk adni a vásárlóinknak. Adott a nevük (egyedi, string) és az eddigi vásárlásaik végösszege (egyenként). Minden ügyfélhez egy lista tartozik, melynek első eleme a személy neve, a második egy lista a vásárlások összegéről, például:

["Anett", [54, 23, 12, 56, 12, 71]]

A kedvezményt a következő módon adnánk:

Összes vásárlás > 200: 10%

Összes vásárlás > 500: 15%

Összes vásárlás > 1000: 20%

Írjuk meg a függvényt, mely megkapja a vásárlók listáját (elemei, mint a fenti "Anett" lista) és visszaad egy listát melyben 2 elemű listák vannak, az első elem a vásárló neve, a második a kedvezménye. Pl:
["Anett", 10]

Hogyan fogjunk neki? Bontsuk részfeladatokra!

  1. A szummából eldönteni a kedvezményt
  2. Vásárló listából kinyerni a vásárlások szummáját
  3. Az egészet elvégezni a teljes vásárló listára

Kétféle képpen lehet haladni (wikipedia top-down_bottom-up_design):

  • top-down: először a fő feladatot oldam meg, úgy hogy az alfeladatokat megoldottnak tekintem
  • bottom-up: először az alfeladatokat oldom meg, azokból állítom össze a fő programot (függvényt)
In [6]:
# top-down

def kedvezmenyek(vasarlok):
    kedvezmenylista = []
    for vasarlo in vasarlok:
        kedvezmenylista.append(kedvezmeny(vasarlo))
    return kedvezmenylista

def kedvezmeny(vasarlo):
    nev = vasarlo[0]
    osszeg = 0
    for vasarlas in vasarlo[1]:
        osszeg += vasarlas
    return [nev, osszegbol_kedvezmeny(osszeg)]

def osszegbol_kedvezmeny(osszeg):
    if osszeg > 1000:
        return 20
    if osszeg > 500:
        return 15
    if osszeg > 200:
        return 10
    return 0
In [7]:
kedvezmenyek([["Anett", [54, 23, 12, 56, 12, 71]], 
              ["Hagrid", [111, 545, 343, 56, 12, 66]], 
              ["Béla", [11, 3, 12, 1, 12, 55]],
              ["Not_a_wizard", [54, 222, 65, 56, 43, 71]]])
Out[7]:
[['Anett', 10], ['Hagrid', 20], ['Béla', 0], ['Not_a_wizard', 15]]

Rendezett sorozat (tuple)

Már megismerkedtünk a karakterláncokkal (sztringekkel) és listákkal, mint összetettebb adatszerkezetekkel. A szám-n-es vagy tuple megadása kerek zárójelek közt vesszőkkel elválasztva, vagy a tuple() függvénnyel adható meg:

In [8]:
t = (1, 5, 6, 2, 1)
print(t[2])
type(t)

6
Out[8]:
tuple
In [9]:
l = [1, 2, 3]
t = tuple(l)
print(t)

(1, 2, 3)

A tuple bejárható (iterable) típus, a for ciklus működik:

In [10]:
for e in t:
    print(e, end=" ")

1 2 3

Az elemei nem változtathatók meg (hasonlóan a sztringhez, és ellentétben a listával), azaz értékadás az elemeire nincs megengedve. A rendezett sorozat (tuple) nem változtatható típus (immutable):

In [11]:
t[1] = 4

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-11-87b0f225887f> in <module>
----> 1 t[1] = 4

TypeError: 'tuple' object does not support item assignment

Bizonyos helyzetekben a zárójel el is hagyható:

In [12]:
# ez is tuple (rendezett sorozat)
x = 2, 3, 4
print(x)

(2, 3, 4)
In [13]:
# itt két tuple egyenlősége az x = 2, y = 3 értékadásokkal ekvivalens
x, y = 2, 3
print(x)
print(y)

2
3

1-hosszú tuple nem összetévesztendő a sima zárójellel, ennek érdekében az utolsó (és egyben első) elem után vesszőt rakunk.

In [14]:
print(type((1)))    # itt (1) és 1 ugyanazt jelenti, egy egész számot
print(type((1,)))   # (1,) egy tuple, melynek egyetlen eleme van
print(type(()))     # üres rendezett sorozat

<class 'int'>
<class 'tuple'>
<class 'tuple'>

Változtatható és nem változtatható adatszerkezetek

A tuple-k úgy működnek, mint a listák egy kivétellel. A listák elemei változtathatók (mutable), a tuple elemei nem változtathatók (immutable). Egy tuple elemei csak úgy változtathatók meg, ha újra létrehozzuk, hasonlóan a string-ekhez:

In [15]:
s = ("l", "e", "l", "e", "t")
print(s[2])
s = s[:2] + ("h",) + s[3:]
s

l
Out[15]:
('l', 'e', 'h', 'e', 't')
In [16]:
for e in s:
    print(e, end=' ')

l e h e t
In [17]:
s[2] = "l"

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-17-29c9f6e304a0> in <module>
----> 1 s[2] = "l"

TypeError: 'tuple' object does not support item assignment

Szótárak

A szótárakat képzelhetjük úgy, mint kulcs-érték párok tárolóit. Egy szótár kulcsa bármilyen megváltoztathatatlan adatszerkezet lehet, akár egyszerű, mint egy egész vagy valós szám, akár egy tuple, vagy egy string, de például a lista nem.

Létrehozhatjuk kapcsos zárójellel { } vagy a dict() függvénnyel.

In [18]:
# hány állatod van?
d = {"kutya": 2, "aranyhal": 6}
type(d)
Out[18]:
dict

Értékként bármilyen adattípus szerepelhet, nem kell megváltoztathatatlannak lennie. Szótárba új elemet úgy vehetünk fel, ha egy új kulcshoz hozzárendelünk egy értéket:

In [19]:
# egy hím, két nőstény
d["macska"] = [1, 2]
d
Out[19]:
{'kutya': 2, 'aranyhal': 6, 'macska': [1, 2]}

Üres szótár is létrehozható:

In [20]:
d = {}
d2 = dict()
In [21]:
d
Out[21]:
{}
In [22]:
d2
Out[22]:
{}

Egy szótáron belül többféle típusú kulcs is lehet. Szótár konvertálható kételemű listák listájából is:

In [23]:
d = dict([[5, "öt"], ["pi", 3.14159]])
d[(1, 5)] = "tuple"
d["ma"] = "kedd"
print(d)

{5: 'öt', 'pi': 3.14159, (1, 5): 'tuple', 'ma': 'kedd'}

A szótár kulcsai bejárhatók egy for ciklussal:

In [24]:
for kulcs in d:
    print(kulcs, ":", d[kulcs])

5 : öt
pi : 3.14159
(1, 5) : tuple
ma : kedd

Az előbbi vásárló adatbázis így nézne ki szótárral:

In [25]:
vasarlok = {"Anett": [54, 23, 12, 56, 12, 71],
            "Hagrid": [111, 545, 601],
            "Béla": [11, 3, 12, 1, 12, 55],
            "Not_a_wizard": [54, 222, 165, 56]}
print(vasarlok)
print()
print(vasarlok["Béla"])

{'Anett': [54, 23, 12, 56, 12, 71], 'Hagrid': [111, 545, 601], 'Béla': [11, 3, 12, 1, 12, 55], 'Not_a_wizard': [54, 222, 165, 56]}

[11, 3, 12, 1, 12, 55]

Feladat: Írjunk olyan programot, mely minden vásárlónra eltárolja a kedvezményét is.

In [26]:
# szótárral

def kedvezmenyek(vasarlok):
    for vasarlo in vasarlok:
        vasarlok[vasarlo] = {"v": vasarlok[vasarlo]}
        vasarlok[vasarlo]["k"] = kedvezmeny(vasarlok[vasarlo]["v"])
        print(vasarlo, vasarlok[vasarlo]["k"])  
        
def kedvezmeny(vasarlo):
    osszeg = 0
    for vasarlas in vasarlo:
        osszeg += vasarlas
    return osszegbol_kedvezmeny(osszeg)

def osszegbol_kedvezmeny(osszeg):
    if osszeg > 1000:
        return 20
    if osszeg > 500:
        return 15
    if osszeg > 200:
        return 10
    return 0
In [27]:
kedvezmenyek(vasarlok)

Anett 10
Hagrid 20
Béla 0
Not_a_wizard 10
In [28]:
vasarlok.keys()
Out[28]:
dict_keys(['Anett', 'Hagrid', 'Béla', 'Not_a_wizard'])
In [29]:
vasarlok.values()
Out[29]:
dict_values([{'v': [54, 23, 12, 56, 12, 71], 'k': 10}, {'v': [111, 545, 601], 'k': 20}, {'v': [11, 3, 12, 1, 12, 55], 'k': 0}, {'v': [54, 222, 165, 56], 'k': 10}])
In [30]:
for i in vasarlok.values():
    print(i)

{'v': [54, 23, 12, 56, 12, 71], 'k': 10}
{'v': [111, 545, 601], 'k': 20}
{'v': [11, 3, 12, 1, 12, 55], 'k': 0}
{'v': [54, 222, 165, 56], 'k': 10}
In [31]:
sorted(vasarlok)
Out[31]:
['Anett', 'Béla', 'Hagrid', 'Not_a_wizard']

Hash függvény

Hogyan keres gyorsan a kulcsalapján, ha a kulcsok különféle típusúak lehetnek?

Több beépített python függvény és algoritmus is (mint például a dict) használja a hash() függvényt, mely minden objektumhoz egy adott bithosszúságú egész számot rendel. Ezeket a hash-értékeket használja az elemek gyors eléréséhez. Hogy a szótárban a kulcs hash-elhető legyen, nem változhat, ezért a kulcs nem lehet mutable objektum, például lista!

A számítástechnika és a kriptográfia más területein is fontos (mind alkalmazásban, mind elméletben) Haladó adatszerkezetek és algoritmuselemzési technikák, Friedl Katalin.

Mit csinál egy hash:

  • adathoz egy természetes számot rendel (fix adatábrázolás: 64, 128, 256 ... biten)
    • függvény, vagyis determinisztikus és adott bemenetre egyértelmű
  • kicsi az esélye az ütközésnek, azaz különböző objektumhoz ritkán kapunk azonos értéket nagyjából egyedi (kevés különböző értéknek ugyanaz a hash értéke)
  • gyorsan számítható

Ezen felül extra elvárások lehetnek (kriptográfiai hash):

  • ne lehessen visszaállítani a hash-ből az adatot (legalábbis a próbálkozásnál könnyebben)
  • (pszeudo) véletlenszerű
  • adathoz és hash-hez ne lehessen azonos hash-ű más adatot generálni (próbálkozásnál könnyebben)

Néhány hash érték, ami lekérhető a hash() függvénnyel:

In [32]:
print(hash((1, 5)))
print(hash(5), hash(0), hash(False), hash(True))
print(hash((5,)))
print(hash("kutya"))
print(hash("kutyb"))
print(hash("mutya"))

3713081631939823281
5 0 0 1
3430023387570
3578292127648814972
-1739193958564598876
-5532518628675707043

Minden immutable objektum hashelhető (azaz alkalmazható rá a hash() függvény).

In [33]:
hash([1, 2])

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-33-4b420d0158ba> in <module>
----> 1 hash([1, 2])

TypeError: unhashable type: 'list'

Alkalmazásai

  • checksum (fájl hash)
  • adatok tárolása gyors eléréssel (dict)
  • pszeudorandom szám generátor (kriptográfia)

Gyűjteményes adattípusok bejárása, függvényei

Bejárható (iterable) az olyan adattípus, mely egyesével vissza tudja adni az összes értékét. Az eddig megismert bejárható adattípusok:

  • list
  • tuple
  • str
  • dict

Bejárásra a for ciklus használható (ezt már előbb láttuk).

Több hasznos művelet alkalmazható egyes bejárható típusokra:

In [34]:
# ismétlés (szótárra nem)
print("kutya "*3)
print((1, 2, 3)*3)
print([1, 2, 3]*3)

kutya kutya kutya 
(1, 2, 3, 1, 2, 3, 1, 2, 3)
[1, 2, 3, 1, 2, 3, 1, 2, 3]
In [35]:
# összefűzés, konkatenálás (szótárra nem)
(1, 2) + (2, 4, 6)
Out[35]:
(1, 2, 2, 4, 6)

Több hasznos beépített függvény van ami egyes bejárható objektumokra alkalmazható.

sum: egy bejárható objektum elemeinek összege

sorted: visszaad egy rendezett listát

any: értéke True, ha van igaz értékű elem, és ha ilyet talál, leáll a kiértékelés

all: értéke True, ha minden elem értéke igaz

max: a legnagyobb elemet adja vissza

min: a legkisebbet

In [36]:
# mind igaz-e (logikai többváltozós "és")
all((False, True, True))
Out[36]:
False
In [37]:
all((0, 1, 1))
Out[37]:
False
In [38]:
# igaz-e valamelyik (logikai többváltozós "vagy")
any((False, True, True))
Out[38]:
True
In [39]:
any((0, 1, 1))
Out[39]:
True
In [40]:
# ezek a hamis értéket adók (ez True lenne, ha volna köztük True)
any((0, 0.0, None, False, [], {}, (), ""))
Out[40]:
False
In [41]:
# Ezek mind True értéket adnak
all((1, 5.2, True, [0], [False], {0:0}, (0,), "a"))
Out[41]:
True
In [42]:
# összeg (számokra van, sztringekre nem)
sum((1, 2, 3))
Out[42]:
6
In [43]:
min((3, 1, 4))
Out[43]:
1
In [44]:
sorted((3, 1, 4))
Out[44]:
[1, 3, 4]
In [45]:
# az speciális/ékezetes betűket a végére rendezi
sorted("vitorlázó")
Out[45]:
['i', 'l', 'o', 'r', 't', 'v', 'z', 'á', 'ó']
In [ ]: