A „Nagyméretű adathalmazok rendezése” című korábbi bejegyzésben szereplő programban egy adott memóriakorláttal rendelkező részsorozat listák (chunk list) előállítására volt szükség. E listák felépítéséhez és méretük behatárolásához azonban nem a tényleges memóriahasználatukat vizsgáltuk a sys modul getsizeof() függvényét használva, hanem a rendezendő sorozatban szereplő karakterek száma alapján becsültük. E bejegyzésben ennek okát járjuk körül.
Az egyszerűség kedvéért most nem fájlból vesszük a karakterláncokból álló sorozatelemeket, hanem egy data_sequence nevű listából, amelynek elemeit úgy állítjuk elő, hogy egy 10 karakterből álló karakterláncot adott számmal ismétlünk elemtöbbszöröző művelettel. Az így előálló lista részlistáit fogjuk képezni, de ezeket sem írjuk most ki fájlba, hanem egy listában gyűjtjük.
Első lépésben készítünk egy olyan függvényt, amely az argumentumként kapott konténerobjektum memóriafelhasználását adja vissza bájtokban mérve. Ebben a sys modul getsizeof() függvényét használjuk fel. Ennek segítségével állapítjuk meg a megadott konténerobjektum, valamint az elemei memóriaigényét. E kettő összege lesz a visszatérési érték. Itt kihasználtuk, hogy az elemek karakterláncok, vagyis nem összetett objektumok. Ha azok lennének, akkor a komponensek memóriaszükségletét is meg kellene határozni. E memory_consumption nevű függvény definíciója a következő:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
from collections.abc import Collection from sys import getsizeof from timeit import timeit def memory_consumption(container: Collection) -> int: """Visszaadja a megadott konténerobjektum és elemeinek együttes memóriaigényét bájtokban, feltételezve, hogy az elemek nem összetett objektumok. """ container_obj_size = getsizeof(container) total_size_of_items = sum(getsizeof(e) for e in container) return container_obj_size + total_size_of_items |
Ezt követően egy olyan függvényt definiálunk, amely egy átadott sorozatot olyan elemszámú részlistákra bontja, amelyek memóriafelhasználása nem haladja meg a második argumentumban meghatározott bájtban mért értéket. A részlistákat a függvény egy listában adja vissza. E create_chunks nevű függvény definíciója látható alább. A függvénytörzs logikája nem bonyolult és a kommentek is segítik a megértést. Az is látható, hogy miként használjuk a részlisták memóriaigényének vizsgálatára a memory_consumption() függvényt.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
def create_chunks(sequence, memory_limit_by_chunk=100 * 1024) -> list[list[str]]: """Az első argumentum adatsorozatát olyan elemszámú részlistákra (chunk_list) bontja, amelyek memóriafelhasználása nem haladja meg a második argumentumban meghatározott bájtban mért értéket. """ chunk_lists = [] # A korlátozott memóriaigényű részlistákat tároló lista. chunk_list = [] # Mindaddig építünk fel egy részlistát, amíg a memóriafelhasználása nem haladja meg a korlátot. # Ha meghaladta, akkor a részlistát eltároljuk és egy új részlistát építünk. for item in sequence: chunk_list.append(item) mc = memory_consumption(chunk_list) # A chunk_list memóriafelhasználása. if mc > memory_limit_by_chunk: chunk_list.pop() chunk_lists.append(chunk_list) chunk_list = [item] chunk_lists.append(chunk_list) return chunk_lists |
A függvénydefiníciók után elsőként a működés helyességét teszteljük. Megnézzük, hogy hány részlista állt elő, valamint ellenőrizzük, hogy ezek elemszámainak összege megegyezik-e az eredeti sorozat elemszámával. Végül kiírjuk, hogy mennyi az egyes részlisták memóriafoglaltsága. Ezek az utolsó kivételével megegyeznek, mert a sorozatelemek azonosak. Az utolsó részlistáét külön is megjelenítjük, mert az eltérhet a többitől.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# Működési teszt. (Python 3.13) data_sequence = ['abcdefghij'] * 10_000 chunks = create_chunks(data_sequence) print('A részlisták száma: {}'.format(len(chunks))) print('Összelemszám: {:_}'.format((len(chunks) - 1) * len(chunks[-2]) + len(chunks[-1]))) print('Utolsó részlista memóriafoglalása: {} bájt, a többieké egyenként: {} bájt'.format(memory_consumption(chunks[-1]), memory_consumption(chunks[-2]))) # Eredmények: # A részlisták száma: 6 # Összelemszám: 10_000 # Utolsó részlista memóriafoglalása: 81158 bájt, a többieké egyenként: 102386 bájt |
A teszt második fázisában a részlisták előállításának futási idejét mérjük a bemeneti sorozat hosszának és a memóriakorlát mértékének függvényében.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
# Futási idő teszt. for itemcount in (10_000, 20_000): data_sequence = ['abcdefghij'] * itemcount print('Elemek száma: {:_}'.format(len(data_sequence))) print('Részlista memória limit \t futási idő') for limit in range(10, 110, 10): print('\t{} kB \t {:.2f} sec'.expandtabs(14).format(limit, timeit('create_chunks(data_sequence, memory_limit_by_chunk=limit*1024)', globals=globals(), number=1))) # Eredmények: # Elemek száma: 10_000 # Részlista memória limit futási idő # 10 kB 0.12 sec # 20 kB 0.23 sec # 30 kB 0.33 sec # 40 kB 0.43 sec # 50 kB 0.55 sec # 60 kB 0.65 sec # 70 kB 0.75 sec # 80 kB 0.87 sec # 90 kB 0.96 sec # 100 kB 1.07 sec # Elemek száma: 20_000 # Részlista memória limit futási idő # 10 kB 0.23 sec # 20 kB 0.46 sec # 30 kB 0.67 sec # 40 kB 0.87 sec # 50 kB 1.09 sec # 60 kB 1.31 sec # 70 kB 1.54 sec # 80 kB 1.75 sec # 90 kB 1.97 sec # 100 kB 2.15 sec |
A kapott eredményekből látható, hogy a futási idő mindkét tényezővel egyenesen arányos, azaz O(n) komplexitású. Ez azt eredményezi, hogy százezres vagy milliós nagyságrendű bemeneti elemszámnál a futási idő nagyon hosszú lesz, ráadásul minél nagyobb a részlisták megengedett memóriakorlátja, annál hosszabb. Ez utóbbi pedig azért gond, mert ha például a részlistákat a memóriában akarjuk hatékonyan rendezni, akkor a hosszabb részlisták a kívánatosak.
E hátrány kiküszöbölésére egy másik megközelítést alkalmazunk.
Nem a részlista tényleges memóriaigényét ellenőrizzük folyamatosan a felépítése során, hanem előzetesen meghatározzuk, hogy a bementi sorozatnak mekkora az egy elemére jutó fajlagos memóriaigénye. Majd ezt megszorozzuk az épülő részlista aktuális elemszámával (hosszával). Bár ez nem a tényleges memóriafoglaltságot adja, de annak egy jó közelítését kapjuk. Amit viszont nyerünk, hogy a futási idő a memóriakorlát értékével most már nem lesz arányos, mert az elemszámkikérés az elemszámtól független, azaz O(1) komplexitású művelet.
Mindezt kódban alább követhetjük.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
from collections.abc import Collection from sys import getsizeof from timeit import timeit def memory_consumption(container: Collection) -> int: """Visszaadja a megadott konténerobjektum és elemeinek együttes memóriaigényét bájtokban, feltételezve, hogy az elemek nem összetett objektumok. """ container_obj_size = getsizeof(container) total_size_of_items = sum(getsizeof(e) for e in container) return container_obj_size + total_size_of_items def create_chunks(sequence, memory_limit_by_chunk=100 * 1024) -> list[list[str]]: """Az első argumentum adatsorozatát olyan elemszámú részlistákra (chunk_list) bontja, amelyek az egy elemre jutó átlagos memóriafelhasználásból becsült memóriafelhasználása nem haladja meg a második argumentumban meghatározott bájtban mért értéket. """ memory_size_per_item = memory_consumption(sequence) / len(sequence) # Egy elemre jutó átlagos memóriafelhasználás. chunk_lists = [] # A korlátozott memóriaigényű részlistákat tároló lista. chunk_list = [] # Mindaddig építünk fel egy részlistát, amíg a becsült memóriafelhasználása nem haladja meg a korlátot. # Ha meghaladta, akkor a részlistát eltároljuk és egy új részlistát építünk. for item in sequence: chunk_list.append(item) mc = len(chunk_list) * memory_size_per_item # A chunk_list becsült memóriafelhasználása. if mc > memory_limit_by_chunk: chunk_list.pop() chunk_lists.append(chunk_list) chunk_list = [item] chunk_lists.append(chunk_list) return chunk_lists # Működési teszt. (Python 3.13) data_sequence = ['abcdefghij'] * 10_000 chunks = create_chunks(data_sequence) print('A részlisták száma: {}'.format(len(chunks))) print('Összelemszám: {:_}'.format((len(chunks) - 1) * len(chunks[-2]) + len(chunks[-1]))) print('Utolsó részlista memóriafoglalása: {} bájt, a többieké egyenként: {} bájt'.format(memory_consumption(chunks[-1]), memory_consumption(chunks[-2]))) # Eredmények: # A részlisták száma: 6 # Összelemszám: 10_000 # Utolsó részlista memóriafoglalása: 78863 bájt, a többieké egyenként: 102845 bájt # Futási idő teszt. for itemcount in (1000_000, 10_000_000): data_sequence = ['abcdefghij'] * itemcount print('Elemek száma: {:_}'.format(len(data_sequence))) print('Részlista memória limit \t futási idő') for limit in range(10, 110, 10): print('\t{} kB \t {:.2f} sec'.expandtabs(14).format(limit, timeit('create_chunks(data_sequence, memory_limit_by_chunk=limit*1024)', globals=globals(), number=1))) # Eredmények: # Elemek száma: 1_000_000 # Részlista memória limit futási idő # 10 kB 0.22 sec # 20 kB 0.22 sec # 30 kB 0.22 sec # 40 kB 0.22 sec # 50 kB 0.22 sec # 60 kB 0.22 sec # 70 kB 0.22 sec # 80 kB 0.22 sec # 90 kB 0.22 sec # 100 kB 0.22 sec # Elemek száma: 10_000_000 # Részlista memória limit futási idő # 10 kB 2.10 sec # 20 kB 2.10 sec # 30 kB 2.15 sec # 40 kB 2.19 sec # 50 kB 2.18 sec # 60 kB 2.19 sec # 70 kB 2.15 sec # 80 kB 2.16 sec # 90 kB 2.15 sec # 100 kB 2.18 sec |
Az előző esethez alkalmazott teszteket elvégezve látványos csökkenést tapasztalhatunk futási időben (több milliós bemeneti elemszámnál is pár másodperc a futási idő), és megfigyelhető az is, hogy ez az idő a részlistákra megengedett memóriakorláttól független.
Ez az oka, hogy a „Nagyméretű adathalmazok rendezése” című korábbi bejegyzésben szereplő programban ez a megközelítés lett megfelelően adaptálva.
A memóriaigény megállapításával a Python tudásépítés lépésről lépésre című e-könyv „Készétel fogyasztás – a szabványos könyvtár moduljainak használata” fejezet „Objektumok memóriafoglaltságának meghatározása” című alfejezete foglalkozik. A végrehajtási idő mérésével pedig a „A programvégrehajtás felfüggesztése és a futási idő mérése” című alfejezet.