Számos esetben lehet szükség egy egész számokból álló sorozat feldolgozására. Az ilyen értékek nem ritkán számtani sorozat elemei lehetnek. Többek között ilyenek például egy Unicode blokk egymást követő kódpontjai, egy statisztikai adatsorban az évszámok, vagy akár a menetrendekben a percben mért indulási idők.
A kérdés az, hogy ha van egy iterálható objektum, ami egész számokat szolgáltat, hogyan bizonyosodjunk meg arról, hogy ezek a sorozatértékek számtani sorozatot alkotnak vagy sem. Ehhez célszerű felidézni a számtani sorozat definícióját és az ebből következő képleteket, amelyeket alább foglaltuk össze:
Az itt látható mindegyik összefüggés használható olyan ellenőrzőfüggvény definiálására, amely a sorozatot, illetve az azt szolgáltató iterálható objektumot fogadja, és True értékkel tér vissza, ha a sorozatértékek egy számtani sorozat elemei. E függvény megvalósítására több változatot mutatunk alább. A közös mindegyikben, hogy a differenciát az első két elemből számítják. Az ezt követő logika és implementáció azonban már eltér.
|
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 |
# Python 3.10+ from itertools import pairwise, islice, tee from typing import Iterable def is_arithmetic_sequence1(iter_obj: Iterable) -> bool: iterator = iter(iter_obj) item1, item2 = next(iterator), next(iterator) d = item2 - item1 previous_item = item2 for current_item in iterator: if current_item - previous_item != d: return False previous_item = current_item return True def is_arithmetic_sequence2(iter_obj: Iterable) -> bool: iterator = iter(iter_obj) item1, item2 = islice(iterator, 2) d = item2 - item1 for item, item_next in pairwise(iterator): if item_next - item != d: return False return True def is_arithmetic_sequence3(iter_obj: Iterable) -> bool: iterator = iter(iter_obj) item1, item2 = islice(iterator, 2) d = item2 - item1 return all(item_next - item == d for item, item_next in pairwise(iterator)) def is_arithmetic_sequence4(iter_obj: Iterable) -> bool: iterator = iter(iter_obj) item1, item2 = next(iterator), next(iterator) d = item2 - item1 return all(item == item1 + n * d for n, item in enumerate(iterator, 2)) # TESZT print('------------- Sorozatelemek konténerekből --------------') seq1, seq2 = [2, 4, 6, 8, 10], [2, 4, 6, 10] for is_arithmetic_sequence in (is_arithmetic_sequence1, is_arithmetic_sequence2, is_arithmetic_sequence3, is_arithmetic_sequence4): print('{:18} számtani sorozat: {}'.format(str(seq1), 'igen' if is_arithmetic_sequence(seq1) else 'nem')) print('{:18} számtani sorozat: {}'.format(str(seq2), 'igen' if is_arithmetic_sequence(seq2) else 'nem')) # Eredmény mindegyik függvény esetében: # [2, 4, 6, 8, 10] számtani sorozat: igen # [2, 4, 6, 10] számtani sorozat: nem print('------------- Sorozatelemek iterátorokból --------------') for is_arithmetic_sequence in (is_arithmetic_sequence1, is_arithmetic_sequence2, is_arithmetic_sequence3, is_arithmetic_sequence4): iterators1 = tee(seq1) # Két iterátor előállítása, amelyek a 2, 4, 6, 8, 10 sorozatot szolgáltatják. iterators2 = tee(seq2) # Két iterátor előállítása, amelyek a 2, 4, 6, 10 sorozatot szolgáltatják. print('{:18} számtani sorozat: {}'.format(str(list(iterators1[0])), 'igen' if is_arithmetic_sequence(iterators1[1]) else 'nem')) print('{:18} számtani sorozat: {}'.format(str(list(iterators2[0])), 'igen' if is_arithmetic_sequence(iterators2[1]) else 'nem')) # Eredmény mindegyik függvény esetében: # [2, 4, 6, 8, 10] számtani sorozat: igen # [2, 4, 6, 10] számtani sorozat: nem |
Az első három változat az első, rekurzív képletet használja, a negyedik viszont az utolsó, nem rekurzív képletet.
Az első függvényben a két szomszédos érték különbségének vizsgálata egy olyan szokásos for-ciklusban történik, amelyben az aktuálishoz képesti előző sorozatelem egy segédváltozó ciklusonkénti felülírásával van tárolva.
A második függvény hasonló elvet követ, de itt egyszerűsítjük a ciklusszervezést bevetve az itertools modul pairwise() függvényét. Ez az argumentumként megadott iterálható objektumból páronként szolgáltat értéket mégpedig úgy, hogy a következő pár első eleme az előző pár második eleme lesz. És ez a működési mód az, amely most pontosan illik a feladatunkhoz. De, ha ezért amúgy is be kell importálni az itertools modult, akkor az első két sorozatelem kinyerésére a két next() hívás helyett használjuk az islice() függvényt.
A harmadik függvényben tovább egyszerűsítjük a kódot. Továbbra is használjuk a pairwise()-t, de az eddigi explicit ciklus helyett az iteráció most az all() beépített függvény argumentumában történik, és az all() eredményével térünk vissza.
A negyedik változatban a számtani sorozat n. elemének meghatározására szolgáló nem rekurzív képletet alkalmazzuk. Az implementáció az előzőhöz hasonlóan kevés kódsort igényel, ráadásul nem szükséges az itertools modul eszköztárából semmit igénybe venni.
A példatesztek igazolják, hogy mindegyik függvény az elvárásoknak megfelelően működik.
A működéshez Python 3.10+ szükséges.
Alkalmazási példa
Az ellenőrzőfüggvények használatának bemutatására vegyünk egy alkalmazási példát. Tegyük fel, hogy valamilyen forrásból származó, és egy iterálható objektumon keresztül kikérhető egész számok sorozatát kell feldolgozni az alkalmazásunkban. Ráadásul ezt a program több pontján kell megtenni, ezért a sorozatot tárolni kell mindaddig, amíg minden feldolgozási fázis le nem fut. Ha hosszú sorozatról van szó, akkor jó lenne, ha a tárolás a legkevesebb memóriafelhasználással járna. Ezt az igényt a következő módon fogjuk teljesíteni.
Mivel egész számok sorozatáról van szó, ezért ezt kihasználhatjuk olyan módon, hogy a számokat nem list vagy tuple típusú konténerekben tartjuk, hanem számok tárolása esetén memóriatakarékosabb array típusú tömbben, amit a szabványos könyvtár array modulja kínál. E tömb létrehozásakor meg kell adni egy, a tárolni kívánt értékekhez illeszkedő egykarakteres típuskódot, amely meghatározza, hogy hány bájton lesznek tárolva az elemek. Vagyis ezáltal elérhetjük, hogy az egész számok sorozata az ábrázolásukhoz szükséges minimumnál ne foglaljon több memóriát.
Ezen felül is tudunk még a memóriahasználatban megtakarítást elérni, ha nem csak azt használjuk ki, hogy a sorozat elemei egészek, hanem megvizsgáljuk, hogy nem alkotnak-e számtani sorozatot. Miért jó ez? Azért mert, ha minden érték egy számtani sorozat eleme, akkor a sorozat tárolása helyett használhatunk egy olyan range objektumot, amely pontosan a szóbanforgó sorozat elemeit szolgáltatja kevés memóriafelhasználás mellett, mert a range nem tárolja az elemeket, hanem kikéréskor állítja elő.
Tehát nem kell mást tenni, mint egy olyan függvényt definiálni, ami a sorozatot, pontosabban az azt szolgáltató iterálható objektumot fogadja és egy sorozattípusú konténert (vagy egy array, vagy egy range objektumot) ad vissza. Legyen e függvény neve convert_iterable_to_sequence.
A függvény megvalósítása elsőre nem tűnik nagy kihívásnak, mert első lépésben az argumentumból származó sorozatról el kell dönteni, hogy számtani sorozat-e vagy sem. Ehhez a vizsgálathoz használjuk az előbb tárgyalt ellenőrző függvények egyikét. Ha számtani sorozatról van szó, akkor második lépésként előállítjuk és visszaadjuk a megfelelő range objektumot vagy, ha pedig nem számtani sor, akkor az array példányt.
Van azért egy apró megoldandó részfeladat. Az array példány előállításához meg kell határozni azt a típuskódot, amely a minimális memóriaigényt biztosítja. Mivel nem ismerjük előre a sorozatértékeket, ezért az array példányt nem lehet egy fix típuskóddal létrehozni. Hanem az értékek ismeretében kell a nekik megfelelő típuskódot meghatározni. Ezt egy külön, typecode_for_minsize_array nevű függvényben végezzük el, ami a következőt teszi: az egész értékekhez megadható típuskódokon sorban végighalad a legkisebb elemmérethez tartozótól a legnagyobbig, és megpróbálja az aktuálissal létrehozni a tömböt. Ha ez nem sikerül, akkor lép a következő, hosszabb elemméretet biztosító típuskódra. Amelyikkel már sikerül a tömb létrehozása, azzal a típuskóddal tér vissza.
Még egy dologra kell figyelni. A számsorozat iterátorból is származhat, ami egy teljes kiolvasás után kimerül. Viszont a sorozatelemeket a convert_iterable_to_sequence függvényben a különböző műveletekhez többször kell felhasználni. Ezért a sorozatértékeket a függvényen belül szükséges ideiglenesen eltárolni. Ez átmenetileg növeli ugyan a memóriaigényt, de az így lefoglalt memória a függvény lefutása után felszabadul.
Mindezeket figyelembe véve most már elkészíthetjük a convert_iterable_to_sequence() függvényt. Ennek, valamint az általa használt typecode_for_minsize_array() és is_arithmetic_sequence() segédfüggvény definíciója alább látható. A tesztsorok mutatják, hogy ha számtani sorozat elemeiről van szó, akkor előáll a megfelelő range objektum, ha pedig nem ilyenek az értékek, akkor egy, az értékekhez igazodó legkisebb memóriaigényű array példányban tárolódnak.
|
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 |
from array import array from typing import Iterable, Sequence, Callable def is_arithmetic_sequence(iter_obj: Iterable[int]) -> bool: """Visszatérési értéke akkor True, ha az argumentumként megadott iterálható objektum által szolgáltatott elemek számtani sorozatot alkotnak. """ iterator = iter(iter_obj) item1, item2 = next(iterator), next(iterator) d = item2 - item1 return all(item == item1 + n * d for n, item in enumerate(iterator, 2)) def typecode_for_minsize_array(*numeric_values: int) -> str: """Az array modul array típusú konténerének létrehozásához megadandó olyan típuskóddal tér vissza, amely biztosítja az argumentumként megadott egész értékek e tömbben való legkisebb memóriaigényű tárolását. """ for typecode in 'bBhHiIlLqQ': # Az egész értékekhez megadható típuskódok. # Megpróbáljuk mindig a kisebb elemmérettel létrehozni a tömböt. Ha ez nem sikerül, akkor # lépünk a következő, hosszabb elemméretet biztosító típuskódra. # Amelyikkel már sikerül a tömb létrehozása, azzal térünk vissza. Ha az értékek közül egy vagy több egyik # egészekre vonatkozó méretbe sem fér bele, akkor hibaüzenettel térünk vissza. try: array(typecode, numeric_values) return typecode except OverflowError: pass raise ValueError('A megadott értékek legalább egyike kívül esik az egész számok ábrázolási tartományán.') Predicate = Callable[[Iterable[int]], bool] def convert_iterable_to_sequence(iter_obj: Iterable[int], arithmetic_sequence_checker: Predicate = is_arithmetic_sequence) -> Sequence: """Az argumentumként megadott iterálható objektum által szolgáltatott egész számok sorozatát adja vissza egy array típusú konténerben, ha azok nem alkotnak számtani sorozatot. Ha pedig az értékek egy számtani sorozat elemei, akkor egy megfelelő range objektum lesz a visszatérési érték. """ # Az argumentum elemeire többször lesz szükség, és ha az argumentum egy iterátor, akkor az kimerülhet. # Ezért a sorozatértékeket ideiglenesen eltároljuk. Az így lefoglalt memória a függvény lefutása után felszabadul. integers = tuple(iter_obj) if arithmetic_sequence_checker(integers): d = integers[1] - integers[0] return range(integers[0], integers[-1] + (1 if d >= 0 else -1), d) return array(typecode_for_minsize_array(*integers), integers) # TESZT if __name__ == '__main__': seq1, seq2 = [2, 4, 6, 8, 10], [2, 4, 6, 10] gen1, gen2 = (n for n in [-180012, -103423, -26834, 49755]), (k for k in [-180012, -103423, -26834, 49750]) print(convert_iterable_to_sequence(seq1), convert_iterable_to_sequence(seq2)) print(convert_iterable_to_sequence(gen1), convert_iterable_to_sequence(gen2)) # Eredmény: # range(2, 11, 2) array('b', [2, 4, 6, 10]) # range(-180012, 49756, 76589) array('i', [-180012, -103423, -26834, 49750]) |
A bemutatott programkódokban az itertools és array modulok használatán volt elsődlegesen a hangsúly. Ezekről 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 „Speciális iterátorok”, valamint „Memóriahatékony számtömb – array” című alfejzetekben lehet részletekbe menően olvasni példákkal illusztrálva a használatot.