Élelmiszert mindenki szokott vásárolni, és a legtöbben tudják azt is, hogy a polcra kitett azonos márkájú termékek úgy vannak elhelyezve, hogy a fogyaszthatósági idő szerint később lejárók hátrébb, a korábban lejárók előrébb, a vásárlók számára könnyebben elérhetően vannak a polcon. Ez természetes, hiszen, ha nem így lenne, és a később lejárók fogynának hamarabb, akkor megnőne annak kockázata, hogy a lejárati idő után sok terméket le kelljen venni a polcról, ami a boltnak veszteség. Ezért, amint a polcról teljesen vagy nagyrészt elfogynak a kitett áruk, a bolti alkalmazottak pótolják azokat, de úgy, hogy a polcon előről hátrafelé irányban a lejárati dátum szerint növekvő sorrend az új termékek felhelyezésekor, azokkal együtt is fennmaradjon.
A polc feltöltésének ilyen elvárásnak megfelelő módszere nem az szokott lenni, hogy az új termékeket először egyszerűen felrakják a polcra a még ott levők mellé, és utána az egész polcot – amin így összességében akár többszáz termék is lehet – lejárati dátum szerint sorba rendezik. Ugyanis ki lehet használni, hogy a polcon maradt termékek már dátum szerint vannak rendezve. Így a polcfeltöltést végző bolti alkalmazott választhatja például a következő ábrán látható két eljárás valamelyikét.
Az A módszer egy sorban egymás után történő keresést és utána egy behelyezési, beszúrási műveletet igényel, ami a behelyezési pozíciót követő összes termék hátrébb pakolásával jár. Ezért ezt az eljárást lineáris keresésen alapuló beszúrásnak nevezhetjük.
A B-vel jelölt eljárás valójában a felezéses módszerrel történő, más néven bináris keresés egy alkalmazása, ahol a behelyezendő termék pozíciójának megkeresése után itt is egy beszúrási művelet szükséges.
Implementáljuk e két polcfeltöltési eljárást egy-egy függvénnyel.
Ehhez előkészítő lépésként definiálunk egy Food nevű osztályt, amely élelmiszert modellez a termék nevével, árával és lejárati idejével. Hogy a hétköznapi valósághoz még jobban közelítsünk, definiáljuk ennek egy Milk nevű alosztályát, amely a tejet mint élelmiszterterméket képviseli. Azért választottuk ezt, mert ha tudjuk, hogy milyen nevű, illetve márkájú tejet akarunk venni, akkor annak adott az ára, és a polcra feltett tejes dobozok csak a lejárati dátumban fognak eltérni. Ezért kicsi annak a valószínűsége, hogy a vásárlók nagyon összekevernék a polc tartalmát. Ellenpéldaként az előre csomagolt felvágottakat (pl. sonka) lehetne felhozni, ahol ugyanazon márka esetén sem teljesen egységes a minőség (egyik csomagban zsírosabb, másikban soványabb van). Ezért a vásárlók az ízlésük szerint a polcon turkálva kikeresik a számukra megfelelő tartalmú csomagokat. Ez pedig a lejárati sorrend szerinti rendezettséget nagymértékben meg tudja bontani.
Ezek után a két, eltérő termékelhelyezési módszerhez definiáljuk az insert_linear() és az insert_custom_bisect() függvényeket. Ezek első argumentumként egy változtatható konténerobjektumot fogadnak, amely a polcot és annak tartalmát képviseli. A második paraméternek pedig a polcra helyezendő Food típusú élelmiszerpéldányt lehet megadni.
Végül az új termékszállítmánnyal történő polcfeltöltést a restock_shelf() függvénnyel valósítjuk meg. Ennek meg kell adni a polcot képviselő listát, a polcra felpakolandó élelmiszertermékek sorozatát, és a termékelhelyezést végző függvényt. Jelen esetben az előzőekben definiáltak közül valamelyiket.
Mivel mindkét termékelhelyezési eljárás rendezett polcot feltételez, és a vásárlók időközben összekeverhették a termékeket a polcon, ezért a restock_shelf() függvényben első lépésként, az új termékek felhelyezése előtt, a polcon rendet kell rakni a termékek lejárati idő szerinti sorba rendezésével. Itt nem mindegy, hogy milyen mértékben voltak a termékek a polcon összekeverve. Ha csak kicsit, akkor az újrarendezés gyorsan végrehajtható.
Az eddig leírtaknak megfelelő programkódot 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 |
# Python 3.10+ from datetime import date import bisect from typing import Callable, MutableSequence, Iterable class Food: """Élelmiszert névvel, árral és lejárati dátummal modellező osztály. """ def __init__(self, name: str, price: float, expiration_date: date): self.name = name self.price = price self.expiration_date = expiration_date def __repr__(self): return f'{type(self).__name__}({self.name}, {self.price}, {self.expiration_date})' class Milk(Food): """Adott márkájú tejet modellező osztály.""" def insert_linear(shelf: MutableSequence[Food], food_to_place: Food) -> None: """A terméket (food_to_place) lineáris kereséssel (linear search) megtalált helyre szúrja be, megőrizve a polc rendezettségét. A függvény sorban egymás után veszi a polcon levő termékeket, és az első olyan elé szúrja be az új terméket, amelynek későbbi a lejárati ideje. Ha nincs ilyen elem, a termék a polc végére kerül. A függvény feltételezi, hogy a nem üres 'shelf' elemei már lejárati idő szerint növekvő sorrendben vannak. """ for i, food_on_shelf in enumerate(shelf): if food_to_place.expiration_date < food_on_shelf.expiration_date: shelf.insert(i, food_to_place) return shelf.append(food_to_place) def insert_custom_bisect(shelf: MutableSequence[Food], food_to_place: Food) -> None: """A terméket (food_to_place) a lejárati ideje alapján a megfelelő helyre szúrja be a polcon (shelf), megőrizve annak rendezettségét. A beszúrási pontot intervallumfelezéses módszerrel (array bisection / binary search algorithm) határozza meg. A függvény feltételezi, hogy a nem üres 'shelf' elemei már lejárati idő szerint növekvő sorrendben vannak. """ low_index, high_index = 0, len(shelf) while low_index < high_index: mid_index = (low_index + high_index) // 2 if shelf[mid_index].expiration_date <= food_to_place.expiration_date: low_index = mid_index + 1 else: high_index = mid_index shelf.insert(low_index, food_to_place) def insert_bisect(shelf: MutableSequence[Food], food_to_place: Food) -> None: """A terméket (food_to_place) a lejárati ideje alapján a megfelelő helyre szúrja be a polcon (shelf), megőrizve annak rendezettségét. A beszúrási pontot intervallumfelezéses módszerrel (array bisection / binary search algorithm) határozza meg. A függvény feltételezi, hogy a nem üres 'shelf' elemei már lejárati idő szerint növekvő sorrendben vannak. """ bisect.insort(shelf, food_to_place, key=lambda f: f.expiration_date) # A key paraméter csak Python 3.10-tól van. def restock_shelf(shelf: list[Food], foods: Iterable[Food], insert_func: Callable[[MutableSequence[Food], Food], None]): """A polc feltöltése új élelmiszertermékekkel, megőrizve a lejárati idő szerinti sorrendet. Mivel a polcon lévő termékek rendezettsége időközben megszűnhet (pl. vásárlók összekeverték), a függvény először sorba rendezi a polcot lejárati idő szerint. Ezt követően az új termékeket egyesével, a megadott beszúró függvénnyel (insert_func) illeszti a megfelelő helyre. """ # Rendrakás a polcon, a termékek lejárati idő szerinti sorba rendezésével. Ha csak kicsit rendezetlen a polc, akkor # az újrarendezés gyorsan végrehajtható. shelf.sort(key=lambda f: f.expiration_date) for food_to_place in foods: insert_func(shelf, food_to_place) |
Észrevehetjük, hogy a bináris keresést alkalmazó megoldáshoz még egy függvényváltozatot definiáltunk insert_bisect() névvel, amely a szabványos könyvtár bisect moduljának insort() függvényét használja. Ezzel azért egészítettük ki a kódot, hogy lássunk e modul gyakorlati alkalmazására is példát. Az insort() elvi szinten ugyanazt teszi, mint amit az insert_custom_bisect(), vagyis a rendezett listába egy új elemet szúr be úgy, hogy a rendezettség fennmaradjon. A beszúrási pozíciót bináris kereséssel határozza meg.
Egy új termék megfelelő helyre történő behelyezésének időigényét mind a keresés, mind a beszúrás időigénye meghatározza.
A lineáris pozíciókeresést alkalmazó eljárás időigénye egy termék felhelyezésekor nagyságrendileg arányos a polcon levő termékek számával, vagyis O(n) komplexitású. Ha n darab terméket egymás után helyezünk el egy kezdetben üres polcon, akkor az összköltség O(n²), vagyis a termékek számával négyzetesen nő.
A bináris pozíciókeresést alkalmazó eljárásnál maga a keresés időigénye jelentősen rövidebb, mert a termékek számának logaritmusával nő, azaz O(log n) komplexitású. A beszúrási művelet azonban a termékek számával arányos, azaz O(n) időköltségű. És ez lesz domináns a logaritmikus keresési időhöz képest. Ezért az összes termék elhelyezésének nagyságrendi időköltsége ebben az esetben is O(n²), vagyis a termékek számával négyzetesen nő.
A keresés optimalizálása tehát elméleti szinten nem javítja a teljes időigény nagyságrendi trendjét. Más szóval, a két eltérő eljárásnál a futási idő egyaránt másodfokú függvénye az elhelyezendő termékek darabszámának.
Ez azonban nem jelenti azt, hogy abszolútértében is azonos futási időt produkál az insert_linear() és az insert_custom_bisect() vagy insert_bisect() függvény. Mérjük is meg ezeket.
Mivel egy élelmiszerüzlet polcán egy adott márkából ritkán van ezres nagyságrendben termék kihelyezve, ezért a polcfeltöltés időigényének mérését 200 termékig végezzük a timeit modul timeit függvényével. Az eredményt a következő ábra bal oldali grafikonja mutatja. Ezen jól látszik a lineáris kereséssel történő beszúrási módszer másodfokú görbéje. Az is egyértelmű, hogy felezéses eljárással sokkal kevesebb idő szükséges, ahogy a termékek száma nő.
Korábban szó volt róla, hogy elvben mindkét módszer O(n²), azaz négyzetes időkomplexitású, de ezen a grafikonon úgy tűnik, mintha a bináris kereséssel működő függvénygörbe nem másodfokú, hanem lineáris lenne. Ez azonban csak látszólag van így, mert ha jelentősen megnöveljük az elhelyezendő termékek darabszámát, akkor már itt is látható az időigény másodfokú jellege. Ezt mutatja a fenti ábra jobb oldali grafikonja.
Annak, hogy azonos O(n²) komplexitás mellett a felezéses eljárással működő függvények futási ideje jóval kisebb, mint a lineáris kereséssel működőé az az oka, hogy a beszúrási művelet mindkét esetben a beépített list típuson történik, ami nagyon gyors lefutású. Ezért a lineáris esetben a keresés dominál, a bináris kereséses megoldásoknál viszont – mivel a keresés nagyon gyors – a beszúrás. De mivel ez sokkal gyorsabb, mint a Python kódban írt lineáris keresés, ezért lesz összességében gyorsabb.
Mindebből a tanulság, hogy az algoritmusok gyakorlati teljesítményét nemcsak az aszimptotikus komplexitás, hanem az implementáció részletei is meghatározzák.
Végül, azért, hogy ne csak elvontan a függvények és algoritmusok szintjén mozogjunk, hanem jobban közelítsük a valóságot, modellezzük a polcot egy Shelf osztállyal, és ebben alkalmazzuk az eddig vizsgált függvényeket.
A Shelf felelőssége a polcon elhelyezett élelmiszertermékek lejárati sorrend szerint rendezett tárolása. Ehhez igénybe vesz egy, az új termékek polcra helyezését megvalósító függvényt. Mint láttuk a bináris keresés alapján működő jelentősen gyorsabb végrehajtást tesz lehetővé, ezért ezt adjuk meg alapértelmezettnek, de lehetőséget biztosítunk más függvény használatára is.
A Shelf képes arra, hogy megadott élelmiszertermékekkel, a lejárati sorrend megtartása mellett, feltöltse önmagát. Mivel a vásárlók két feltöltés között összekeverhetik a termékeket, ezért a feltöltés előtt egy rendrakás, vagyis a polcon már fent levő termékek lejárati sorrend szerinti rendezése is szükséges. Extra funkcióként arra is képes a Shelf, hogy egy megadott dátumhoz képest már lejárt termékek eltávolíthatók legyenek a polcról. A Shelf ezen követelményeknek megfelelő osztálydefinícióját és használatát alább láthatjuk. A teszteredményekből látható a helyes működés.
|
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 |
class Shelf: def __init__(self, insert_func: Callable[[list[Food], Food], None] = insert_bisect): self._items: list[Food] = [] # A polcon elhelyezett élelmiszer termékek konténere. self._insert = insert_func # Az új termékek polcrahelyezését megvalósító függvény. def set_insert_strategy(self, insert_func: Callable[[list[Food], Food], None]) -> None: """Az új termékek polcrahelyezését megvalósító függvény beállítása.""" self._insert = insert_func def tidy(self) -> None: """Rendrakás a polcon: a polcon levő termékek rendezése lejárati idő szerint.""" self._items.sort(key=lambda f: f.expiration_date) def add(self, food: Food) -> None: """Egy élelmiszertermék felhelyezése a polcra.""" self._insert(self._items, food) def restock(self, foods: Sequence[Food]) -> None: """A polc feltöltése a bejövő termékekkel. Mivel nem biztos, hogy a polcon levő termékek lejárati idő szerint vannak rendezve (pl. vásárlók összekeverték), ezért először rendet kell rakni a polcon, és utána lehet az új termékeket a lejárati idejüknek megfelelően a polcon levők közé beilleszteni. """ self.tidy() # Rendrakás a polcon. for food in foods: self.add(food) # Az új termékek felhelyezése a polcra. def remove_expired(self, today: date) -> None: """Lejárt termékek eltávolítása.""" self._items = [food for food in self._items if food.expiration_date >= today] def __repr__(self) -> str: return f"{type(self).__name__}({self._items})" def __iter__(self) -> Iterator[Food]: return iter(self._items) # TESZT # Dobozos tejek létrehozása véletlenszerű lejárati dátumokkal. expiry_dates = [date(2026, randint(1, 12), randint(1, 28)) for _ in range(6)] milks = [Milk('Boci', 400, expiry) for expiry in expiry_dates] milk_shelf = Shelf(insert_func=insert_bisect) # A tejes polc. # Polcfeltöltés. milk_shelf.restock(milks) # Selejtezés. milk_shelf.remove_expired(date.today()) # Ellenőrzés. print(milks) print(*milk_shelf, sep=', ') # A tejek a polcon lejárati idő szerint sorrendben vannak elhelyezve. # Kiírások: # [Milk(Boci, 400, 2026-05-02), Milk(Boci, 400, 2026-05-26), Milk(Boci, 400, 2026-06-26), Milk(Boci, 400, 2026-03-25), # Milk(Boci, 400, 2026-09-09), Milk(Boci, 400, 2026-04-23)] # Milk(Boci, 400, 2026-03-25), Milk(Boci, 400, 2026-04-23), Milk(Boci, 400, 2026-05-02), Milk(Boci, 400, 2026-05-26), # Milk(Boci, 400, 2026-06-26), Milk(Boci, 400, 2026-09-09) |
Ebben a bejegyzésben függvényekkel és osztályokkal történő modellezés mellett algoritmusok futási idő szerinti jellemzése, mérése és összehasonlítása volt a középpontban. Ehhez a Python tudásépítés lépésről lépésre című e-könyv „Egymáshoz rendelve – függvények” fejezet „Költséges függvények” című alfejezetéből lehet az alapokat elsajátítani.