Informatika1-2014/eloadas4

A MathWikiből

Tartalomjegyzék

Gyűteményes adatszerkezetek, adatstruktúrák

Érdemes a Python saját tutoralját is elolvasni.

Listák

Ugyanúgy lehet szeletelni (slice), mint a karakterláncot:

>>> x = [1, 2, 3, 4]
>>> x[1]
2
>>> x[2:]
[3, 4]
>>> x[0::2]
[1, 3]
>>> x[:]
[1, 2, 3, 4]
>>> x[-1:-3]
[]
>>> x[-1:-3:-1]
[4, 3]
>>> x[-1::-1]
[4, 3, 2, 1]

Ugyanúgy lehet összeadni, többszörözni, mint a karakterláncot, de a lista változtatható (mutable):

>>> x = [1, 2, 3, 4]
>>> x[:2]*2 + x[-1:]
[1, 2, 1, 2, 4]
>>> x[:2]*2 + x[-1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only concatenate list (not "int") to list

Az értékadás (=) csak objektumhivatkozással jár, nem történik adatmásolás. Ennek következtében egy y = x parancs után, ahol x lista (vagy valamilyen más gyűjteményes adattípus), az y ugyanarra az objektumra fog mutatni. Így ha megváltoztatjuk x-et vagy y-t, változik a másik is. Az objektumhivatkozások megtörténhetnek egy szinttel mélyebben is, a (z = x[:] kód esetén az x elemeire mutató hivatkozások másolódnak, de ekkor sem jön létre a teljes objektumról másolat. Ezt hívjuk sekély másolásnak (shallow copy).


Egy másik példa sekély másolásra:

Mély másolás (deep copy), amikor valóban új példány keletkezik az objektumból:

import copy
w = copy.deepcopy(x)



Listák kezelése, metódusai

Lista létrehozható értékadással, [] az üres lista. A range parancs is listát ad vissza:

>>> range(3)
[0, 1, 2]
>>> range(3, 6)
[3, 4, 5]
>>> range(1,10,3)
[1, 4, 7]

A lehetséges metódusok például kiírhatók TAB billentyűvel ipythonban:

In [31]: x = range(1,5); x
Out[31]: [1, 2, 3, 4]
 
In [32]: x.append(99); x
Out[32]: [1, 2, 3, 4, 99]
 
In [33]: x.
x.append   x.extend   x.insert   x.remove   x.sort     
x.count    x.index    x.pop      x.reverse  
 
In [33]: x.extend([1,1,1]); x
Out[33]: [1, 2, 3, 4, 99, 1, 1, 1]
 
In [34]: x.count(1); x
Out[34]: [1, 2, 3, 4, 99, 1, 1, 1]
 
In [35]: x.index(2)
Out[35]: 1
 
In [36]: x.insert(4,5); x
Out[36]: [1, 2, 3, 4, 5, 99, 1, 1, 1]
 
In [37]: x.pop(5); x
Out[37]: [1, 2, 3, 4, 5, 1, 1, 1]
 
In [38]: x.re
x.remove   x.reverse  
 
In [38]: x.reverse(); x
Out[38]: [1, 1, 1, 5, 4, 3, 2, 1]
 
In [39]: x.remove(1); x
Out[39]: [1, 1, 5, 4, 3, 2, 1]
 
In [40]: x.sort(); x
Out[40]: [1, 1, 1, 2, 3, 4, 5]

Listaértelmezés

Írjuk egy listába a 100-nál kisebb nem negatív négyzetszámokat! Egy megoldás:

>>> negyzetek = []
>>> for x in range(10):
        negyzetek.append(x**2)
 
>>> negyzetek
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Egy egyszerű -- igazi Pythonos -- megoldás:

>>> negyzetek = [x**2 for x in range(10)]

Rövid listák létrehozásának egyszerű módja a listaértelmezés. Általános alakja:

[expression for expr in sequence1
            if condition1
            for expr2 in sequence2
            if condition2 
            ...
            for exprN in sequenceN
            if conditionN]

Kis programrészek helyettesíthetők vele. Például soroljuk fel az 1890 és 1915 közé eső szökőéveket!

szoko = []
for ev in range(1890, 1922):
    if (ev%4 == 0 and ev%100 != 0) or (ev%400 == 0):
        szoko.append(ev)
print szoko
[1892, 1896, 1904, 1908, 1912, 1916, 1920]

Lépésenként egyre összetettebb listaértelmezéssel állítsuk elő ugyanezt:

>>> szoko = [ev for ev in range(1890, 1915)]
>>> szoko    # ez még az összes év
[1890, 1891, 1892, 1893, 1894, 1895, 1896, 1897, 1898, 1899, 1900, 1901, 1902, 1903, 1904, 1905, 1906, 1907, 1908, 1909, 1910, 1911, 1912, 1913, 1914]
>>> szoko = [ev for ev in range(1890, 1915) if ev%4 == 0]
>>> szoko    # ez a 4-gyel osztható évek listája
[1892, 1896, 1900, 1904, 1908, 1912]
>>> szoko = [ev for ev in range(1890, 1915) 
                if (ev%4 == 0 and ev%100 != 0) or ev%400 == 0]
>>> szoko
[1892, 1896, 1904, 1908, 1912]


del utasítás

A del utasítással törölhetők elemek, a lista tartalma vagy az egész lista:

>>> l = range(2,7)
>>> del l[2]; l
[2, 3, 5, 6]
>>> del l[:]; l
[]
>>> del l
>>> l
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'l' is not defined

Sorozat (tuple)

Változtathatatlan (immutable), mint a karakterlánc, műveletei: szeletelés [], összefűzés (+), szorzás (*), összehasonlítás, tagsági viszony (in, not in)

>>> t = ()
>>> t
()
>>> t = 1, 5, 5, 5, 3   # itt elhagyható a zárójel
>>> t
(1, 5, 5, 5, 3)
>>> t[1]
5
>>> t.index(3)
4
>>> t.count(5)
3
>>> t[0] = 9
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

Maga nem változtatható, de változtatható elemei lehetnek:

>>> t = [1,2], [3,4,5], 6
>>> t
([1, 2], [3, 4, 5], 6)

Az üres és az 1-hosszú sorozat kényes dolog, mert a ()-jeleket másra is használjuk:

>>> t=()
>>> t
()
>>> t = (3)
>>> type(t)
<type 'int'>
>>> t = 3,
>>> type(t)
<type 'tuple'>

A sorozatba való be- és kicsomagolás:

>>> t = 2, 3, 4
>>> t
(2, 3, 4)
>>> x, y, z = t
>>> x, y, z
(2, 3, 4)
>>> x
2

Halmaz (set)

A halmaz rendezetlen, duplikált elemek nélküli gyűjteményes adattípus. Tagsági viszony gyorsabb ellenőrzésére, duplikált elemek törlésére használható. A matematikai halmazműveletek használhatók.

>>> a = set('matematika'); a
set(['a', 'e', 'i', 'k', 'm', 't'])
>>> b = set('matek'); b
set(['a', 'e', 'k', 'm', 't'])
>>> a - b     # halmazok különbsége
set(['i'])
>>> b - a
set([])
>>> a | b     # halmazok uniója (vagy)
set(['a', 'e', 'i', 'k', 'm', 't'])
>>> a & b     # halmazok metszete (és)
set(['a', 'm', 'k', 'e', 't'])
>>> a ^ b     # halmazok szimmetrikus differenciája (kizáró vagy)
set(['i'])

Bevitelnél a kapcsos zárójel is használható, kivéve az üres halmazt:

>>> t = {1, 2, 3, 4}
>>> type(t)
<type 'set'>
>>> t
set([1, 2, 3, 4])
>>> t = {}
>>> type(t)
<type 'dict'>


A listaértelmezéshez hasonlóan van halmazértelmezés is:

>>> {x for x in 'asztrológia' if x not in 'asztronómia'}
set(['l', 'g'])


Szótár (dict)

A szótár kulcs-érték párokból álló halmaz. Nem a 0, 1, 2,... számokkal van indexelve, mint a sorozat vagy a karakterlánc, hanem bármilyen nem változtatható objektumokkal. Ezeket nevezzük kulcsnak. A kulcs tehát lehet szám, karakterlánc, sorozat, de nem lehet lista. A kulcshoz tartozó érték bármi lehet. Egy szótárban minden kulcsból csak egy lehet.

>>> tel = {'Laci': 1243, 'Ági': 2221, 'Zoli': 3321}
>>> type(tel)
<type 'dict'>
>>> tel['Laci']
1243
>>> tel = dict([('Laci',1243), ('Ági',2221), ('Zoli',3321)])
>>> tel['Laci']
1243
>>> tel = dict(Laci=1243, Ági=2221, Zoli=3321)
  File "<stdin>", line 1
    tel = dict(Laci=1243, Ági=2221, Zoli=3321)
                          ^
SyntaxError: invalid syntax
>>> tel = dict(Laci=1243, Agi=2221, Zoli=3321)
>>> tel['Agi']
2221

A listaértelmezésnek szótárakra is van változata:

>>> {x: x**3 for x in (11, 12, 13)}
{11: 1331, 12: 1728, 13: 2197}

Hasító tábla (hash table)

Általában a hash tábla (hash table, hasító tábla) egy olyan adatszerkezet, amely egy hash függvény (hasító függvény) segítségével állapítja meg, hogy melyik kulcshoz milyen érték tartozik. A Python dict adattípusa hash tábla. A hash függvény minden objektumhoz egy véges tartományba eső egész számot rendel. A hash tábla kezelésekor kezelni kell az esetleges ütközéseket, azaz azokat az eseteket, amikor két különböző kulcshoz azonos hash-érték tartozik. A Python a hash függvény értékkészletébe eső egészeken az identikus leképezés, tehát

>>> hash(1)
1
>>> hash(1.0)
1
>>> hash(1123)
1123
>>> hash(-1123)
-1123
>>> hash(1111111111111111111111111111)
497554224548382901

Így e függvényhez könnyű ütközést kreálni (a születésnapi paradoxon is besegít), de a gyakorlatban nagyon ritka, és a hash tábla kezelés föl van ilyen esetekre készülve (a kriptográfiai célokra használt hash függvényt úgy kell megkonstruálni, hogy ütközést belátható időn belül ne lehessen könnyen találni).

>>> hash(0.1)
2576882278
>>> hash(2576882278)
2576882278

Csak változtathatatlan (immutable) objektumoknak lehet hash értéke:

>>> l = [1, 2]     # változtatható (mutable)
>>> c = "hash"     # változtathatatlan (immutable)
>>> hash(c)
7799588877615763652
>>> hash(l)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
Személyes eszközök