Szathmáry László honlapja @ DEIK

Dinamikus tömb

A Python lista adatszerkezete egy dinamikus tömb. Más nyelvekben is van dinamikus tömb, ilyen pl. Java-ban az ArrayList.

A feladat most az, hogy írjunk egy osztályt, amivel egy dinamikus tömböt valósítunk meg.

Ismétlésképp: egy dinamikus tömb valójában egy statikus tömböt használ az implementációjában. Amikor ez a tömb betelik, s újra meghívjuk az "append()" metódust, akkor a következő játszódik le: egy nagyobb tömböt foglal le, az eddigi elemeket átmásolja a nagyobb tömbbe, majd a nagyobb tömbbe beteszi az új elemet, a régi tömböt pedig törli. Ha mindezt elrejtjük egy osztályban, akkor mindez transzparens módon fog végbemenni.

Python-ban nem tudunk statikus tömböt létrehozni, ezért a numpy külső csomagot fogjuk használni. Példa statikus tömbre:

>>> import numpy as np
>>>
>>> a = np.empty(4, dtype='object')
>>> a
array([None, None, None, None], dtype=object)
>>>
>>> a[0] = 3
>>> a[1] = 'hello'
>>> a
array([3, 'hello', None, None], dtype=object)
>>>
>>> a[4] = 4
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: index 4 is out of bounds for axis 0 with size 4
>>>

Mint látható, egy 4 méretű statikus tömböt hoztunk létre, amibe bármilyen típusú elem betehető.

Feladat

Bővítsük ki az alábbi forráskódot úgy, hogy az osztályunk egy dinamikus tömböt valósítson meg.

#!/usr/bin/env python3

import numpy as np

class MyList:
INITIAL_CAPACITY = 4
MULTIPLIER = 2

def __init__(self):
self._array = np.empty(MyList.INITIAL_CAPACITY, dtype='object')
self._capacity = MyList.INITIAL_CAPACITY
self._size = 0

def append(self, value):
# TODO
pass

def __len__(self):
return self._size

def __str__(self):
return str(self._array[:self._size])

def main():
lst = MyList()
print(lst)
print(len(lst))

##############################################################################

if __name__ == "__main__":
main()

Implementáljuk az "append()" metódust. A "main()" függvényt bővítsük ki további tesztesetekkel. Mi történik, ha 4-nél több elemet szúrunk be? Írjuk meg a "pop()" metódust is, ami a legutolsó elemet eltávolítja és egyben vissza is adja annak az értékét.

20190406b