Számos esetben lehet szükség arra, hogy egy sorozat elemei közül a minimális értékűt kiválasszuk és meghatározzuk, hogy ez a sorozatban hol található. Ha az elemek egy iterátorból származnak, akkor a „hol” a sorrendpozíciót, ha pedig egy sorozattípusú konténerobjektumban állnak rendelkezésre, akkor az indexet jelenti.
Ha csak a minimumértékre lenne szükség, akkor egyszerű lenne a dolog, mert a min() beépített függvényt használhatjuk, ami nem csak konténert, hanem általánosabban, egy iterálható objektumot képes fogadni. Ennek nagyméretű adathalmaznál jelentősége van, mert így nem kell a teljes adatsort egy konténerben a memóriában tárolni (ha egyáltalán azt a memóriakapacitás engedi).
A helyzet azzal válik egy kicsit összetettebbé, hogy a minimumérték sorozatbeli helyét is tudni akarjuk. Ha a min() függvényt az előbb említett módon használjuk, vagyis a sorozatot adjuk argumentumnak, akkor a gond, hogy a végén az adatokat szolgáltató iterátor kimerül, és ezért a pozíciómeghatározás mint második lépés nem tehető meg. Ha tehát a min() függvényt így akarjuk használni, akkor a pozíció megállapításához az adatsort előzetesen el kell tárolni valamilyen sorozattípusú konténerben (list, tuple, deque). Ha ez megvan, akkor e konténer index() metódusnak átadva a min() függvénnyel meghatározott minimális értéket, megkapjuk annak helyét (indexét).
Ez az eljárás tehát extra memóriát igényel és két keresési lépésben határozza meg az igényelt adatokat: először a minimumértéket a teljes sorozaton végighaladva, majd az indexet szintén a teljes sorozatból.
Kérdés, hogy van-e más megoldás a minimumérték és minimumhely meghatározására? Igen van, több is.
Eljárhatunk úgy is, hogy bár eltároljuk a sorozatot, de a min() függvénnyel nem a minimális elemet határozzuk meg, hanem előbb a minimális indexet. Ezt úgy tesszük, hogy a min() argumentumaként egy olyan range objektumot adunk, amely a sorozat elemszámával megegyező indexértékeket ad ki, a key paraméternek pedig a sorozat __getitem__ metódusobjektumát. A minimálértékhez tartozó index ismeretében a minimumértéket egyszerűen elemkikéréssel kapjuk meg.
Az előző egy változata, ha a sorozatot és a range objektumot „összezipeljük”, vagyis a zip() függvényt ezekkel meghívjuk és az így kapott iterátort adjuk át a min() függvénynek. Az eredmény a minimumértéket és -indexet tartalmazó kételemű tuple lesz.
Megoldható a feladat úgy is, hogy használjuk a min() függvényt, azonban nem kell tárolni a sorozatot és egyetlen lépésben kapjuk meg a minimumot és annak pozícióját. Ezt úgy érhetjük el, hogy a min() argumentuma az enumerate(sorozat). Ekkor a minimumkeresés ismérve az enumerate() által szolgáltatott kételemű tuple konténerek második eleme lesz. Ezt a key paraméterrel határozhatjuk meg lambdafüggvénnyel vagy az operator modul itemgetter függvényével.
Olyan megoldások is lehetnek, amelyek nem használják a min() függvényt.
Az egyik ilyen, amikor a sorozatot kétszer is tároljuk: egy tuple és egy list konténerben. Bár ez pazarlónak tűnik, de az az értelme, hogy a list sort() metódusa – amellyel a „Rendezéshez a sorted() függvényt vagy a list.sort() metódust használjuk?” című bejegyzésben is foglalkoztunk – gyors rendezést nyújt, és ezt követően a lista első eleme lesz a minimális érték. Ezt az eredeti sorrendet megörző tuple index() metódusának átadva megkapjuk a minimumhoz tartozó indexet.
Másik olyan módszer, ahol nem használjuk a min() függvényt és nem is kell tárolni a sorozatot az, hogy egy ciklusban végighaladunk a sorozat elemein és megvizsgáljuk, hogy az-e az éppen aktuális minimális érték. Ha nem, akkor továbbhaladunk. Ha igen, akkor ezt tesszük meg aktuális minimumnak. Ha a ciklusokat számláljuk, akkor a minimális érték indexét is meg tudjuk a végén kapni. A ciklusszámlálást megvalósíthatjuk egy változó értékének explicit növelésével vagy a ciklusban az enumerate(sorozat) iterátorból kérjük ki az index és érték elemeket.
A fent felsorolt megoldási változatoknak megfelelő függvények definícióit alább láthatjuk:
|
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 87 88 89 90 91 92 93 94 95 96 97 98 99 |
# modul: min_functions from operator import itemgetter from collections import deque from typing import Sequence def minimum1_loop_inc_index(iterable): itr = iter(iterable) try: min_value = next(itr) except StopIteration: raise ValueError('Üres sorozat.') min_value_index, i = 0, 1 for item in itr: if item < min_value: min_value = item min_value_index = i i += 1 return min_value_index, min_value def minimum1_loop_enumerate(iterable): itr = iter(iterable) try: min_value = next(itr) except StopIteration: raise ValueError('Üres sorozat.') min_value_index = 0 for i, item in enumerate(itr, 1): if item < min_value: min_value = item min_value_index = i return min_value_index, min_value def minimum2_tuple(iterable): seq: Sequence = tuple(iterable) if not seq: raise ValueError('Üres sorozat.') min_value = min(seq) min_value_index = seq.index(min_value) return min_value_index, min_value def minimum2_list(iterable): seq: Sequence = list(iterable) if not seq: raise ValueError('Üres sorozat.') min_value = min(seq) min_value_index = seq.index(min_value) return min_value_index, min_value def minimum2_deque(iterable): seq: Sequence = deque(iterable) if not seq: raise ValueError('Üres sorozat.') min_value = min(seq) min_value_index = seq.index(min_value) return min_value_index, min_value def minimum2_inplace_sort(iterable): seq: Sequence = tuple(iterable) if not seq: raise ValueError('Üres sorozat.') lst = list(seq) lst.sort() min_value = lst[0] min_value_index = seq.index(min_value) return min_value_index, min_value def minimum3_min_enum_itemgetter(iterable): return min(enumerate(iterable), key=itemgetter(1)) def minimum3_min_enum_lambda(iterable): return min(enumerate(iterable), key=lambda t: t[1]) def minimum3_min_range_getitem(iterable): seq: Sequence = tuple(iterable) if not seq: raise ValueError('Üres sorozat.') min_value_index = min(range(len(seq)), key=seq.__getitem__) min_value = seq[min_value_index] return min_value_index, min_value def minimum3_min_zip(iterable): seq: Sequence = tuple(iterable) if not seq: raise ValueError('Üres sorozat.') min_value, min_value_index = min(zip(seq, range(len(seq)))) return min_value_index, min_value |
A függvénynevekben szereplő azonos számok a függvénytörzsben alkalmazott megoldási módszerek hasonlóságára utal: az 1-es csoportban nem tároljuk a sorozatot és ciklust alkalmazunk, a 2-es csoportban tároljuk a sorozatot és két keresési lépésben határozzuk meg a minimális értéket és annak pozícióját. A 3-as csoport függvényei mind használják a min() függvényt és egy keresési lépésben határozzák meg a minimális értéket és annak pozícióját.
A kérdés, hogy ezek közül melyiket válasszuk?
Az egyik szempont a memóriahasználat. Ha hosszú az adatsorozat (pl. fájlból olvassuk be), és amelynek egyben történő tárolása a felhasználható memóriát túllépné, akkor azok a függvények jönnek szóba, amelyek nem tárolják a sorozatot.
A másik szempont a futási idő. Ez szintén nagyméretű adathalmaz esetén fontos. Ezt azonban a függvények definíciójából nem tudjuk megítélni, ezért mérni kell. A végrehajtási idők vizsgálatára a következő tesztprogramot használjuk.
|
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 |
# Python 3.13 from typing import Iterable from timeit import timeit from enum import Enum from min_functions import (minimum1_loop_inc_index, minimum1_loop_enumerate, minimum2_tuple, minimum2_list, minimum2_deque, minimum2_inplace_sort, minimum3_min_enum_itemgetter, minimum3_min_enum_lambda, minimum3_min_range_getitem, minimum3_min_zip) class MinPosition(Enum): FIRST = 0 MIDDLE = 1 LAST = 2 def test_running_times(iterable: Iterable, min_position: MinPosition): """Az első argumentumként megadott sorozat minimumértékét és annak pozícióját számolja ki az egyes beimportált minimum számoló függvényekkel, és méri a számításhoz szükséges időt. Kiírja a függvény nevét, a minimumérték pozícióját (indexét) és a minimimuméréket egy tuple-ban, valamint a számítási időt. A második argumentummal lehet meghatározni, hogy a minimumérték a sorozat első, középső vagy utolsó eleme legyen. Ez, az adott függvényben alkalmazott számítási módszertől függően, befolyásolhatja a futási időt. """ sequence = list(iterable) if min_position == MinPosition.FIRST: sequence.sort() elif min_position == MinPosition.MIDDLE: min_val = min(sequence) min_val = sequence.pop(sequence.index(min_val)) # Ha több, azonos minimumérték lenne, akkor csak egyet hagyunk meg és ezt helyezzük a sorozat közepére. for _ in range(sequence.count(min_val)): sequence.remove(min_val) sequence.insert(len(sequence) // 2, min_val) elif min_position == MinPosition.LAST: sequence.sort(reverse=True) results = [(min_func.__name__, min_func(sequence), timeit('min_func(sequence)', globals=locals(), number=10)) for min_func in [obj for name, obj in globals().items() if name.startswith('minimum') and callable(obj)]] for result in sorted(results, key=lambda t: t[2]): print('{:30}\t{}\t{:.3f}'.format(*result)) data_sequence = range(10_000_000) print(f'A sorozat hossza: {len(data_sequence):_}') print('\n-- A minimum a legelső érték --') test_running_times(data_sequence, MinPosition.FIRST) print('\n-- A minimum a középső érték --') test_running_times(data_sequence, MinPosition.MIDDLE) print('\n-- A minimum az utolsó érték --') test_running_times(data_sequence, MinPosition.LAST) |
A teszt eredményeit két sorozathosszra az alábbi táblázatokban foglaltuk össze eltérő színekkel jelölve a hasonló futási idő teljesítményű függvényeket.
Látható, hogy mindkét sorozathossz esetén a 2-es csoport függvényei állnak az élen. Ezeket követik az 1-es, majd a 3-as csoport függvényei. Az eredmény annyiban meglepő, hogy a 2-es csoport a tárolási és két keresési idő ellenére bizonyul a leggyorsabbnak. Tehát, ha a memóriafelhasználás nem kritikus szempont, akkor érdemes ezek közül választani. Az eredmények alapján pedig konkrétan azt, amelyben a sorozat tárolására tuple konténer szolgál. Ha a memóriahasználat szempont, akkor az 1-es csoport mindkét függvénye megfelelő, bár az enumerate() használatával működő általában egy kicsivel nagyobb futási időt mutat.
Ha az adathalmaz nagyméretű, azaz a sorozat meglehetősen hosszú, a memóriafelhasználás jelentős lehet azoknál a függvényeknél, amelyek belül eltárolják a sorozatot. Ennek ellenére ezeket a függvényeket sem kell elvetni végleg. Ugyanis a sorozatot darabokban, szakaszokban is feldolgozhatjuk. Ilyenkor a teljes sorozat minimuma a részsorozatot minimumából a legkisebb érték lesz. A minimális érték teljes sorozatbeli pozícióját pedig ki lehet számolni a részsorozaton belüli indexet és a részsorozatokat számláló változó értékét, valamint a részsorozat hosszát felhasználva. Ezt a feldolgozási eljárást valósítja meg az alább látható programban a min_using_chunks() függvény. Ennek a sorozaton kívül meg lehet adni a használni kívánt minimum-meghatározó függvényt, valamint a részsorozat hosszát.
|
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 |
# Python 3.13 from operator import itemgetter from typing import Iterable from timeit import timeit from enum import Enum from itertools import batched from min_functions import (minimum1_loop_inc_index, minimum1_loop_enumerate, minimum2_tuple, minimum2_list, minimum2_deque, minimum2_inplace_sort, minimum3_min_enum_itemgetter, minimum3_min_enum_lambda, minimum3_min_range_getitem, minimum3_min_zip) class MinPosition(Enum): FIRST = 0 MIDDLE = 1 LAST = 2 def min_using_chunks(value_sequence, minimum_func, chunk_length=5000): """Meghatározza az első argumentumban megadott sorozat minimumértékét és annak pozícióját a második argumentummal megadott minimumszámoló függváénnyel úgy, hogy a sorozatot szakaszokra bontja, meghatározza az egyes szakaszok minimumát, majd veszi ezek minimumát és ennek pozícióját az eredeti sorozatban. A szakaszhosszt a harmadik argumentummal lehet beállítani. """ chunk_minimums = [] # Tárolja az egyes szakaszok minimumhelyét és minimumértékét. for chunk_index, chunk in enumerate(batched(value_sequence, chunk_length)): # A megadott minimumszámoló függvénnyel meghatározzuk a szakasz minimumot és annak szakaszon belüli pozícióját. min_value_index_in_chunk, min_value_in_chunk = minimum_func(chunk) # Meghatározzuk a szakaszminimum pozícióját az eredeti sorozatban, majd ezt és a szakaszminimumot eltároljuk. chunk_minimums.append((chunk_index * chunk_length + min_value_index_in_chunk, min_value_in_chunk)) # Vesszük az egyes szakaszok minimumértékét és ezzel valamint ennek eredeti sorozatbeli pozíciójával visszatérünk. return min(chunk_minimums, key=itemgetter(1)) def test_running_times(iterable: Iterable, min_position: MinPosition): """Az első argumentumként megadott sorozat minimumértékét és annak pozícióját számolja ki az egyes beimportált minimum számoló függvényekkel, és méri a számításhoz szükséges időt. A számítást nem egy menetben a teljes sorozaton végzi el, hanem a min_using_chunks() függvény segítségével úgy, hogy a sorozatot szakaszokra bontja, meghatározza az egyes szakaszok minimumát, majd veszi ezek minimumát és ennek pozícióját az eredeti sorozatban. Kiírja a függvény nevét, a minimumérték pozícióját (indexét) és a minimimuméréket egy tuple-ban, valamint a számítási időt. A második argumentummal lehet meghatározni, hogy a minimumérték a sorozat első, középső vagy utolsó eleme legyen. Ez, az adott függvényben alkalmazott számítási módszertől függően, befolyásolhatja a futási időt. """ sequence = list(iterable) if min_position == MinPosition.FIRST: sequence.sort() elif min_position == MinPosition.MIDDLE: min_val = min(sequence) min_val = sequence.pop(sequence.index(min_val)) # Ha több, azonos minimumérték lenne, akkor csak egyet hagyunk meg és ezt helyezzük a sorozat közepére. for _ in range(sequence.count(min_val)): sequence.remove(min_val) sequence.insert(len(sequence) // 2, min_val) elif min_position == MinPosition.LAST: sequence.sort(reverse=True) results = [(min_func.__name__, min_using_chunks(sequence, min_func), timeit('min_using_chunks(sequence, min_func)', globals=locals() | globals(), number=10)) for min_func in [obj for name, obj in globals().items() if name.startswith('minimum') and callable(obj)]] for result in sorted(results, key=lambda t: t[2]): print('{:30}\t{}\t{:.3f}'.format(*result)) data_sequence = range(10_000_000) print(f'A sorozat hossza: {len(data_sequence):_}') print('\n-- A minimum a legelső érték --') test_running_times(data_sequence, MinPosition.FIRST) print('\n-- A minimum a középső érték --') test_running_times(data_sequence, MinPosition.MIDDLE) print('\n-- A minimum az utolsó érték --') test_running_times(data_sequence, MinPosition.LAST) |
Az ilyen módon meghatározott minimumérték és minimumhely számítási időszükségletét az előbbi program további soraival teszteljük. Az eredményeket az alábbi táblázatok foglalják össze az előző tesztnél alkalmazott sorozathosszakra. A relatív sorrend majdnem ugyanaz, mint az előző esetben azzal az eltéréssel, hogy most az egyértelmű befutó az a 2-es csoportba tartozó függvény, amely a list.sort() metódust alkalmazza.
Megfigyelhető, hogy a relatív sorrend majdnem ugyanaz, mint az előző esetben azzal az eltéréssel, hogy most az egyértelmű befutó az a 2-es csoportba tartozó függvény, amely a list.sort() metódust alkalmazza.
A beépített sorozattípusú konténereket, továbbá a beépített függvényeket, köztük a min() függvényt is, a Python tudásépítés lépésről lépésre című e-könyv „Beépített konténerobjektumok”, illetve „Beépített függvények” fejezetei ismertetik. Iterálható objektumokkal a „Kérem a következőt!” – iterálható objektumok című fejezet, iterárokkal az „Iterátorok és elemeik kinyerésének nyelvi megvalósítása” fejezet foglalkozik. A végrehajtási idő mérésével pedig a „Készétel fogyasztás – a szabványos könyvtár moduljainak használata” fejezeten belül a „A programvégrehajtás felfüggesztése és a futási idő mérése” című alfejezet.