Tegyük fel, hogy egy kérdőívet a megkérdezettek különböző helyszíneken töltenek ki. A kérdéseket és a válaszokat fájlba (pl. JSON fájlba) mentik. Ezeket kell összegyűjteni, és az egyes kérdésekre adott összes választ feldolgozni (például a számszerű értékeléseket átlagolni vagy más statisztikai jellemzőt számolni).
Ezt meg lehet úgy oldani, hogy a fájlok tartalmát szótárakba olvassuk be, ahol azok kulcsa az adott kérdés, vagy annak azonosítója, a kulcshoz tartozó érték pedig a válasz (pl. egy szám). Ahhoz, hogy az adott kérdésre adott összes választ könnyen feldolgozhassuk e szótárakat kell összesíteni olyan módon, hogy az eredményül kapott szótárban minden kulcs szerepeljen, és egy adott kulcshoz tartozó válaszok egy, a kulcshoz értékként társított listában legyenek felsorolva. Ha ez rendelkezésre áll, akkor bármelyik kérdéshez (kulcshoz) tartozó adatsor egyszerűen kikérhető és feldolgozható.
Másik példaként vegyünk egy járműflotta kezelő rendszert, amelybe naponta több sofőr is bejegyezheti a megállásait. Ennek alapján meg kell állapítani, hogy egy adott helyszín (például egy elosztó központ) hány alkalommal és mikor volt érintett. Ebben az esetben a helyszín nevét és annak látogatás idejét, egy szótárban lehet tárolni. Utána ezeket kell megfelelően összesíteni, majd az aggregált szótárból a kívánt értéksorozatokat kinyerni és feldolgozni.
Elvonatkoztatva a konkrét példáktól, a feladat tehát az, hogy készítsünk egy olyan függvényt, amely az argumentumként átadott szótárak alapján egy olyan új szótárt állít elő, amely a bemeneti szótárak minden kulcsát tartalmazza, úgy, hogy minden kulcshoz tartozó érték egy lista, amelyben a bemeneti szótárak adott kulcshoz tartozó értékei szerepelnek.
Ha a bemeneti szótárak mindegyike olyan egyedi kulccsokkal rendelkezne, amelyek a többi szótárban nem található, akkor a feladat megoldása könnyű lenne, mert csak egyszerűen egyesíteni kellene a szótárakat, és a listákra se lenne szükség, hiszen egy adott kulcshoz egy adott érték tartozna. De esetünkben nem ez a helyzet, mert a bementeti szótárak kulcsai részben vagy teljesen megegyeznek.
A feladat megoldását jelentő függvény több módon is megvalósítható. Ezek definíciói láthatók alább:
|
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 |
from typing import Hashable, Any from collections import defaultdict, ChainMap from itertools import chain, groupby from operator import itemgetter # A következő függvényváltozatok az argumentumként felsorolt szótárakból egy olyan új szótárat # hoznak létre, amely a felsorolt szótárak minden kulcsát tartalmazza, úgy, hogy minden kulcshoz tartozó # érték egy lista, amelyben a bemeneti szótárak adott kulcshoz tartozó értékei szerepelnek. def merge_dicts_collect_values1(*dictionaries: dict) -> dict[Hashable, list[Any]]: aggregator_dict: dict[Hashable, Any] = {} for d in dictionaries: for key, value in d.items(): if key not in aggregator_dict: aggregator_dict[key] = [] aggregator_dict[key].append(value) return aggregator_dict def merge_dicts_collect_values2(*dictionaries: dict) -> dict[Hashable, list[Any]]: aggregator_dict: dict[Hashable, Any] = {} for d in dictionaries: for key, value in d.items(): aggregator_dict.setdefault(key, []).append(value) return aggregator_dict def merge_dicts_collect_values3(*dictionaries: dict) -> dict[Hashable, list[Any]]: aggregator_dict = defaultdict(list) for d in dictionaries: for key, value in d.items(): aggregator_dict[key].append(value) return dict(aggregator_dict) def merge_dicts_collect_values4(*dictionaries: dict) -> dict[Hashable, list[Any]]: all_keys = set() all_keys.update(*(d.keys() for d in dictionaries)) aggregator_dict: dict[Hashable, list] = {k: [] for k in all_keys} for d in dictionaries: for key, value in d.items(): aggregator_dict[key].append(value) return aggregator_dict def merge_dicts_collect_values5(*dictionaries: dict) -> dict[Hashable, list[Any]]: cm = ChainMap(*dictionaries) aggregator_dict: dict[Hashable, list] = {k: [] for k in cm.keys()} for d in cm.maps: for key, value in d.items(): aggregator_dict[key].append(value) return aggregator_dict def merge_dicts_collect_values6(*dictionaries: dict) -> dict[Hashable, list[Any]]: dict_key = itemgetter(0) dicts_items = (d.items() for d in dictionaries) sorted_items = sorted(chain.from_iterable(dicts_items), key=dict_key) return {k: [t[1] for t in group_iterator] for k, group_iterator in groupby(sorted_items, key=dict_key)} |
Az első változatban először létrehozunk egy, a függvény által majd visszaadott aggregáló szótárat, ami kezdetben üres. Kikérjük az argumentumként felsorolt szótárak kulcs-érték párjait, és ellenőrizzük, hogy az éppen aktuális kulcs szerepel-e az aggregáló szótárban. Ha nem, akkor e kulcsot egy hozzá rendelt üres listával együtt felvesszük mint szótárelemet, majd a listához hozzáadjuk az aktuális bemeneti szótár aktuális kulcsához tartozó értékét. Ha az összes, argumentumként felsorolt szótárral végeztünk, akkor az aggregáló szótárat visszaadja a függvény.
A függvény második és harmadik változatainak logikája nagyon hasonló az előzőhöz azzal az eltéréssel, hogy a kulcstartalmazás ellenőrzést, a lista létrehozását és az értékek listákhoz adását a második változatban a setdefault() metódus használatával, a harmadik változatban pedig a szabványos könyvtár collections moduljában elérhető defaultdict() alkalmazásával egyszerűsítettük. Ez utóbbi esetben ahhoz, hogy dict típust adjon vissza a függvény, a defaultdict() szótárat dict típusra kell konvertálni.
A negyedik függvénynél a lényegi változás az előzőekhez képest, hogy az eredményként visszaadandó szótárt az előtt felépítjük, hogy a kulcsokhoz tartozó értékeket a listákba helyeznénk. Ehhez össze kell gyűjteni az összes lehetséges kulcsot. Az ismétlések kiküszöböléséhez ezt egy halmazban tesszük meg. Ha ismerjük a lehetséges kulcsokat, akkor az aggregáló szótárat létre tudjuk hozni úgy, hogy minden kulcs egy hozzá társított üres listával szerepel benne. Ezt követően a listák értékekkel történő feltöltése a harmadik változathoz hasonlóan történhet.
A ötödik változat alapelve hasonló a negyedikéhez azzal a különbséggel, hogy a lehetséges kulcsok összegyűjtését most a collections modul ChainMap konténerével hajtjuk végre. Ehhez létrehozzuk a ChainMap egy példányát a szótárakkal. Tesszük ezt azért, mert kihasználjuk a ChainMap azon tulajdonságát, hogy ha a példányára a keys() metódust meghívjuk, akkor egyetlen halmazszerű objektumban megkapjuk mindazon kulcsot, amelyek a bemeneti szótárak bármelyikében előfordul. A további kódok az előző változatéval egyeznek.
Az utolsó, hatodik függvényváltozat teljesen más megközelítéssel működik. Először előállítjuk a bemeneti szótárak kulcs-érték párjait kételemű tuple objektumok formájában. Ezt követően kulcsok szerint rendezzük azokat. Az így rendezett tuple sorozatot a kulcsok szerint csoportosítjuk az itertools modul groupby() iterátorával. Ez olyan kételemű iterálható objektumokat szolgáltat, amelynek első eleme a csoportosítási kulcs, a második eleme pedig egy iterátor, amely a csoportosítási kulcsnak megfelelő objektumokat (jelen esetben a kételemű tuple konténereket) adja ki. Ezekből szótárépítő kifejezéssel állítjuk elő az aggregáló szótárat mint visszatérési értéket.
Az egyes függvényváltozatok működését a következő kódsorokkal teszteljük.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Egyesítendő szótárak. dicts = [{'d': 7, 'a': 6}, {'a': 1, 'b': 2}, {'b': 4, 'a': 3, 'c': 5}] # Előállítjuk az aggregált szótárt az egyes függvényimplementációkkal. functions_dicts = [(fn.__name__, fn(*dicts)) for fn in (merge_dicts_collect_values1, merge_dicts_collect_values2, merge_dicts_collect_values3, merge_dicts_collect_values4, merge_dicts_collect_values5, merge_dicts_collect_values6)] # Kiírjuk a kapott aggregált szótárakat, hogy ellenőrizzük minden függvény helyesen hozza-e létre. print('Egyesítendő szótárak: ', *dicts, end='\n\n') print('{:^31}{:^54}'.format('Függvény', 'Egyesített szótár')) for fn_name, dictionary in functions_dicts: print('{:^31}{:^54}'.format(fn_name, str(dictionary))) |
|
1 2 3 4 5 6 7 8 9 10 11 |
Egyesítendő szótárak: {'d': 7, 'a': 6} {'a': 1, 'b': 2} {'b': 4, 'a': 3, 'c': 5} Függvény Egyesített szótár merge_dicts_collect_values1 {'d': [7], 'a': [6, 1, 3], 'b': [2, 4], 'c': [5]} merge_dicts_collect_values2 {'d': [7], 'a': [6, 1, 3], 'b': [2, 4], 'c': [5]} merge_dicts_collect_values3 {'d': [7], 'a': [6, 1, 3], 'b': [2, 4], 'c': [5]} merge_dicts_collect_values4 {'d': [7], 'a': [6, 1, 3], 'b': [2, 4], 'c': [5]} merge_dicts_collect_values5 {'b': [2, 4], 'a': [6, 1, 3], 'c': [5], 'd': [7]} merge_dicts_collect_values6 {'a': [6, 1, 3], 'b': [2, 4], 'c': [5], 'd': [7]} |
A kiírt eredményekből megállapítható, hogy mindegyik függvény helyesen működik. Az, hogy az egyes visszaadott szótárakban a kulcsok sorrendje eltérő lehet nem gond, hiszen szótárak esetén az elemek sorrendje elvben nem számít. Ami fontos, hogy a végeredményként kapott szótárban az összetevő szótárak minden kulcsa szerepel, és az egyes kulcsokhoz tartozó értékek a listákban megjelennek.
Amikor egy adott cél eléréséhez több megoldás is rendelkezésre áll, felmerül a kérdés, hogy ezek közül melyiket használjuk. Választási szempontként gyakran a futási időt és a kód olvashatóságát (mennyire könnyű értelmezni) szokták venni.
Egy kód olvashatóságának megítélése természetesen bizonyos mértékben szubjektív, mert függ a nyelvben való jártasságtól és a tapasztalattól. Mindenesetre a bemutatott hat változat közül az első négy viszonylag könnyen értelmezhető. Az ötödikhez a ChainMap működésének behatóbb ismerete szükséges. És mivel a ChainMap nem tartozik a gyakran használt nyelvi eszközök közé, így a kód nem biztos, hogy elsőre teljesen világos. Mégis a legkevésbé könnyen olvasható az utolsó változat, mert itt a megoldási logika és annak kódbeli leképzése egyaránt összetett.
A futási idő méréséhez első lépésben szükségünk van egy olyan függvényre, amely az aggregálni kívánt szótárakat szolgáltatja. Ennek argumentumként meg kell tudni adni, hogy hány szótárt akarunk létrehozni, valamint azt, hogy egy szótárban hány kulcs legyen. Mivel a tesztelni kívánt hat függvénynek valójában akkor van értelme és haszna, ha a szótárak kulcsai részben vagy egészben fedik egymást, ezért a szótárakat előállító függvényünknek azt is meg kell adni, hogy a szótárakban milyen arányban legyenek azonosak a kulcsok. Az egyszerűség kedvéért a kulcsok csak karakterláncok lehetnek. Ezek hosszát és az alkalmazható karakterek készletét szintén meg lehet adni. Ez utóbbi alapértelmezetten legyen az ASCII kis- és nagybetűk halmaza. E követelményeknek megfelelő, create_dictionaries nevű függvény definícióját láthatjuk alább a generate_unique_keys() segédfüggvénnyel együtt, amely adott számú egymástól eltérő, egyedi karakterláncokat szolgáltat. A függvények működésének megértését a részletes kommentek segítik.
|
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 |
import random import string def generate_unique_keys(num_keys: int, key_length: int = 4, charset: str = string.ascii_letters) -> list[str]: """Egyedi kulcsok listáját állítja elő. Minden kulcs egy megadható karakterkészletből kerül összeállításra véletlenszerű választással. Paraméterek: num_keys : a generálandó egyedi kulcsok száma. key_length : az egyes kulcsok hossza. charset : az a karakterkészlet, amelyből a kulcsok karakterei véletlenszerűen kerülnek kiválasztásra. Alapértelmezetten az ASCII kis- és nagybetűk. Visszatérési érték: egy lista az egyedi kulcsokkal. """ # Addig generáljuk véletlenszerűen az új kulcsokat, amíg el nem érjük a szükséges mennyiséget, ahol # minden kulcs garantáltan egyedi lesz. keys: set[str] = set() while len(keys) < num_keys: keys.add(''.join(random.choice(charset) for _ in range(key_length))) return list(keys) def create_dictionaries(num_dicts: int, num_keys_per_dict: int, common_ratio: float = 0.9, key_length: int = 4, charset: str = string.ascii_letters) -> list[dict]: """Adott számú szótár listájával tér vissza. A létrehozott szótárak kulcsai megadható hosszúságú karakterláncok. A szótárak megegyező számú kulccsal rendelkeznek, amelyek meghatározható arányban azonosak. Paraméterek: num_dicts: A létrehozandó szótárak száma. num_keys_per_dict: Minden egyes szótár összes kulcsának száma (közös + egyedi kulcsok együtt). common_ratio : A kulcsok azon aránya, amely minden szótárban közös lesz. Példa: 0.9 esetén a kulcsok 90%-a minden szótárban azonos. key_length : az egyes kulcsok hossza. charset : az a karakterkészlet, amelyből a kulcsok karakterei véletlenszerűen kerülnek kiválasztásra. Alapértelmezetten az ASCII kis- és nagybetűk. Visszatérési érték: Szótárak listája. Minden szótár ugyanannyi kulcsot tartalmaz és - a közös kulcsok megegyeznek az összes szótárban, - az egyedi kulcsok szótáranként különböznek, - a kulcsok értékei véletlenszerűen generált 0 és 100 közötti egészek. """ # A függvény először legenerál egy olyan kulcshalmazt, amely elegendő mennyiségű egyedi kulcsot # tartalmaz ahhoz, hogy minden szótár megkapja a közös kulcsokat, valamint a saját, csak rá jellemző # egyedi kulcsait. Ezután a kulcsokat felosztja közös és szótárankénti egyedi részekre, majd elkészíti # a szótárakat véletlenszerű, 0 és 100 közötti egész értékekkel. common_key_count = int(num_keys_per_dict * common_ratio) # A szótárakban közös kulcsok száma. unique_key_count = num_keys_per_dict - common_key_count # Az egyes szótárakban az egyedi kulcsok száma. # Összesen szükséges kulcsok száma, amiből majd a közös és az egyedi kulcsokat vesszük. total_key_count = common_key_count + num_dicts * unique_key_count # A szükséges összmennyiségű kulcsok generálása. all_keys = generate_unique_keys(total_key_count, key_length, charset) # A generált kulcsokból a közös, valamint a szótáranként egyedi kulcsok előállítása. common_keys = set(all_keys[:common_key_count]) unique_key_sets: list[set] = [] for i in range(common_key_count, total_key_count, unique_key_count): unique_keys = set(all_keys[i: i + unique_key_count]) unique_key_sets.append(unique_keys) return [{k: random.randint(0, 100) for k in common_keys | unique_key_sets[i]} for i in range(num_dicts)] |
A create_dictionaries() függvényt felhasználó, a futási időket mérő test_dict_aggregation_times() függvény definíciója alább látható. Ennek első paramétere egy karakterláncot fogad, amely a tesztfeltételek kiírására használható. A többi paraméter jelentése megegyezik a create_dictionaries()függvénynél szereplőkkel.
|
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 |
from timeit import timeit from operator import itemgetter def test_dict_aggregation_times(title: str, num_dicts: int, num_keys_per_dict: int, common_ratio: float, key_length): """Tesztfüggvény, amely alkalmas a szótárszám és kulcsszám kombinációk futási idejének tesztelésére.""" print('\n', '-' * 8, title, '-' * 8, end='\n\n') dicts = create_dictionaries(num_dicts, num_keys_per_dict, common_ratio, key_length) # Az aggregáló függvényekkel mért futási idők. measurements = [(fn.__name__, timeit('fn(*dicts)', globals=globals() | locals(), number=100)) for fn in (merge_dicts_collect_values1, merge_dicts_collect_values2, merge_dicts_collect_values3, merge_dicts_collect_values4, merge_dicts_collect_values5, merge_dicts_collect_values6)] # Rendezés a futási idők növekvő sorrendjében. exec_time = itemgetter(1) sorted_measurements = sorted(measurements, key=exec_time) print(f'Szótárak száma: {len(dicts)}, kulcsok száma: {num_keys_per_dict:_}\n') print('{:^31}{:^8}'.format('Függvény', 'Futási idő')) for record in sorted_measurements: fn_name, execution_time = record print('{:^31}{:^8.2e}'.format(fn_name, execution_time)) # Tesztesetek. test_dict_aggregation_times('Kevés szótár, kevés kulcs', 3, 5, 0.85, 6) test_dict_aggregation_times('Kevés szótár, sok kulcs', 3, 5000, 0.85, 6) test_dict_aggregation_times('Sok szótár, kevés kulcs', 100, 5, 0.85, 6) test_dict_aggregation_times('Sok szótár, sok kulcs', 100, 5000, 0.85, 6) |
A tesztelést négy esetre végeztük. Ezekből kettő az, amikor az egyesítendő szótárak száma kicsit, és a szótárak kevés vagy sok kulcsot tartalmaznak. A másik két esetben a szótárak szintén kevés vagy sok kulccsal rendelkeznek, de az aggregálni kívánt szótárak száma viszonylag nagy. Az eredmények a következő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 |
-------- Kevés szótár, kevés kulcs -------- Szótárak száma: 3, kulcsok száma: 5 Függvény Futási idő merge_dicts_collect_values2 1.67e-04 merge_dicts_collect_values1 1.87e-04 merge_dicts_collect_values3 2.26e-04 merge_dicts_collect_values4 2.72e-04 merge_dicts_collect_values5 3.89e-04 merge_dicts_collect_values6 3.92e-04 -------- Kevés szótár, sok kulcs -------- Szótárak száma: 3, kulcsok száma: 5_000 Függvény Futási idő merge_dicts_collect_values2 1.49e-01 merge_dicts_collect_values1 1.67e-01 merge_dicts_collect_values3 1.76e-01 merge_dicts_collect_values4 1.96e-01 merge_dicts_collect_values5 2.28e-01 merge_dicts_collect_values6 5.39e-01 -------- Sok szótár, kevés kulcs -------- Szótárak száma: 100, kulcsok száma: 5 Függvény Futási idő merge_dicts_collect_values3 4.59e-03 merge_dicts_collect_values2 4.76e-03 merge_dicts_collect_values1 4.81e-03 merge_dicts_collect_values4 5.91e-03 merge_dicts_collect_values5 7.52e-03 merge_dicts_collect_values6 1.09e-02 -------- Sok szótár, sok kulcs -------- Szótárak száma: 100, kulcsok száma: 5_000 Függvény Futási idő merge_dicts_collect_values3 4.62e+00 merge_dicts_collect_values1 4.85e+00 merge_dicts_collect_values2 5.09e+00 merge_dicts_collect_values4 5.43e+00 merge_dicts_collect_values5 7.44e+00 |
Az eredménykiírásokból látható, hogy amikor az egyesíteni kívánt szótárak száma kevés, akkor a setdefault() metódust használó függvény bizonyul a leggyorsabbnak, és a függvények végrehajtási idő szerinti sorrendje független a kulcsok számától. Ezzel szemben, ha sok szótárt kívánunk aggregálni, akkor a defaultdict()-et alkalmazó függvény a leggyorsabb. Továbbá, a második és harmadik helyezetteknél van változás attól függően, hogy sok vagy kevés kulcsot tartalmaznak a szótárak.
Azt is megfigyelhetjük, hogy sok szótár esetén a groupby()-t használó megoldás nagyságrenddel rosszabb futási idővel rendelkezik, mint a többi. És mivel ez is volt a legkevésbé olvasható, ezért ez a függvényváltozat ehhez az esethez biztosan nem ajánlott.
Ebben a bejegyzésben a szótárak voltak a fókuszban. Ezekről részleteiben, példákkal magyarázva a Python tudásépítés lépésről lépésre című e-könyvben a „Beépített konténerobjektumok”, a „Konténerekkel végezhető műveletek”, „Beépített típusok nyilvános metódusai” fejezetekben, valamint a „Készétel fogyasztás – a szabványos könyvtár moduljainak használata” fejezeten belül a „Speciális konténer típusok” című alfejezetben lehet olvasni. A futási idő meghatározáshoz pedig a „A programvégrehajtás felfüggesztése és a futási idő mérése” alfejezetet érdemes átnézni.