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]:
M[0][1]
Out[2]:
2
In [3]:
M = [[[1, 2], [3, 4]], [[5, 6], [7, 8]], [[0, 9], [0, 0]]]  # 3x2x2-es tömb
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], "\t",   # TAB karakter
        print
In [5]:
tomb_kiir([[1,2,3],[4,5,6],[7,8,9]])

1 	2 	3 	
4 	5 	6 	
7 	8 	9
In [6]:
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 (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 [7]:
# top-down

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

def kedvezmeny_szamol(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 [8]:
kedvezmeny([["Anett", [54, 23, 12, 56, 12, 71]], 
            ["Bela", [11, 3, 12, 1, 12, 55]],
            ["Hagrid", [111, 545, 343, 56, 12, 66]], 
            ["Not_a_wizard", [54, 222, 65, 56, 43, 71]]])
Out[8]:
[['Anett', 10], ['Bela', 0], ['Hagrid', 20], ['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 [9]:
t = (1, 5, 6, 2, 1)
print t[2]
type(t)

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

(1, 2, 3)
In [11]:
for e in t:
    print e

1
2
3
In [12]:
t[1] = 4

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-12-141c76cb54a2> in <module>()
----> 1 t[1] = 4

TypeError: 'tuple' object does not support item assignment

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

In [13]:
x = 2, 3, 4
print x

(2, 3, 4)
In [14]:
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 [15]:
print type((1))
print type((1,))

<type 'int'>
<type '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 [16]:
s = ("l", "e", "l", "e", "t")
print s[2]
s = ("l", "e", "h", "e", "t")

l
In [17]:
for e in s:
    print e,

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

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-18-335b26526d8f> 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.

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

In [19]:
d = {"kutya": 5}
type(d)
Out[19]:
dict

Értékként bármilyen adattípus szerepelhet, nem kell megváltoztathatatlannak lennie:

In [20]:
d = {}
d["macska"] = [1, 5]

Szótárba új elemet úgy vehetünk fel, ha egy új kulcshoz hozzárendelünk egy értéket:

In [21]:
print d

{'macska': [1, 5]}

Egy szótáron belül többféle kulcs is lehet:

In [22]:
d = dict()
d[5] = 7
d[(1, 5)] = "macska"
print d
d[(1, 5)] = "sajt"
d["macska"] = 3.14
print d

{(1, 5): 'macska', 5: 7}
{(1, 5): 'sajt', 5: 7, 'macska': 3.14}

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

In [23]:
for kulcs in d:
    print kulcs, ":", d[kulcs]

(1, 5) : sajt
5 : 7
macska : 3.14

A szótárak elemeinek sorrendje véletlenszerűnek tűnhet. A háttérben a szótárak tárolási mechanizmusa áll.

A szótárak úgynevezett hash függvényt alkalmaznak, hogy a kulcsokat leképezzék egy véges halmazra. Ezeket a hash-értékeket használja az elemek gyors eléréséhez. A részletek ismertetése nélkül néhány hash érték, ami lekérhető a hash() függvénnyel:

In [24]:
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")
print hash("kutya, macska, kutya, macska, akármi, valami")

3713081631939823281
5 0 0 1
3430023387570
7736109777944507559
7736109777944507556
1523875377516237945
105194640156580037

Hash függvény

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.

Sőt ez nem csak a python-ban használatos, hanem a számítástechnika és 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 (több féle is van):

  • 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ű
  • nagyjából egyedi (kevés különböző értéknek ugyan az 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 próbálkozásnál nem jobban)
  • (pszeudo) véletlenszerű és nem-folytonos legyen
  • adathoz és hash-hez ne lehessen azonos hash-ű más adatot generálni (próbálkozásnál nem jobban)

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. Bejárásra a for ciklus használható (ezt már előbb láttuk).

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

In [25]:
# ismétlés
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 [26]:
# konkatenálás
(1, 2) + (2, 4, 6)
Out[26]:
(1, 2, 2, 4, 6)
In [27]:
# mind igaz-e (logikai többváltozós "és")
print all((False, True, True, True))
print all((0, 1, 1, 1))

False
False
In [28]:
# bármelyik igaz-e (logikai többváltozós "vagy")
any((0, 1, 1, 1))
Out[28]:
True
In [29]:
# "transzponlás"
zip([1, 2, 3], [11, 12, 13], ["a", "b", "c"])
Out[29]:
[(1, 11, 'a'), (2, 12, 'b'), (3, 13, 'c')]
In [30]:
# összeg (számokra van, sztringekre ez nem)
sum((1, 2, 3))
Out[30]:
6
In [ ]: