Kód-optimalizálás php-ban
Egy baráti beszélgetés kapcsán jutottam egy érdekes feladat közelébe, amin keresztül a legkülönfélébb optimalizálási technikákat sikerült kipróbálni. Az egyik szépsége, hogy csak php-oldali kód van benne (nincs zavaró html-barkácsolás, illetve futáslassító adatbázis-lekérdezések), így összekeverés nélkül tudtam koncentrálni a programozás algoritmikus szintjére.
A kiírt feladat egyszerű megfogalmazása, valamint a megoldás evolúciója késztetett végül arra, hogy dokumentáljam a folyamatot, ezen keresztül bemutatva a számomra ismert praktikákat.
A feladat
Egy szállodába 25 fős vendégcsoport érkezik. Számoljuk ki, hogy hányféle kombinációban tudunk nekik szállást biztosítani, amennyiben 1, 2, 3 illetve 4 fős szobáink vannak (ezekből korlátlan darabszám áll rendelkezésre), minden szobát teljesen kihasználunk (nincs üres ágy egy kiajánlott szobában sem), valamint nincs kikötés arra sem, hogy ki kivel – vagy kivel nem – szeretne egy szobában lenni.
Korlátaink
A számításnak le kell tudnia futni 1 másodpercen belül egy asztali gépen. A tesztekhez a futtatási korlát 90 másodperc, a memórialimit pedig 128MB.
Én a cikk megírása során tesztgépnek BEORNEGAR-t használtam [Sabertooth X58; Core i7@3.06GHz; 12GB ram; 128GB SSD].
Ízelítő
Az alábbi ábrákon az előtte/utána állapotok szerepelnek. Ezzel szeretnék kedvet csinálni a végigolvasáshoz, mivel egy kicsit hosszadalmas. Viszont a görbék azt mutatják, hogy elég sokat sikerült nyerni a leírt technikák alkalmazásával.
A futási idő a vendégek számának függvényében:
A memóriahasználat ugyanezen aránypárral:
Az első verzió vonala azért olyan rövid, mert a mérések során nagyon hamar elérte a 90 másodperces futási küszöböt, így nem volt lehetőség további adatgyűjtésre. A közbenső verziók memóriahasználatán látható lesz majd a fejlődés ezen a területen is.
Feladatelemzés
A számításhoz fel kell állítani egy modellt. A függvényünknek az alábbi kimenetet kell produkálni:
bemeneti oldalon a vendégek, kimeneti oldalon pedig a variációk száma van
Q(1) = 1 (egy darab egyfős szoba)
Q(2) = 2 (egy darab kétfős, és két egyfős szoba)
Q(3) = 3 (egy darab háromfős, egy két és egy egyfős, illetve három egyfős szoba)
Q(4) = 5 (rövidítve leírva: 1×4, 1×3+1×1, 1×2+2×1, 2×2, 4×1)
Minden további esetre:
Q(n) = unique( Q(n-1) + Q(n-2) + Q(n-3) + Q(n-4) )
Megtéveszthető lehet a unique() függvény egy összeadás eredményére. Ezt azért használtam így, mivel nincs más mód annak jelzésére, hogy a négy különböző függvényfutás által visszaadott variációk közül ki kell ejteni a megegyezőket.
Vegyük sorba a számítási lépéseket, és kiderül miért van erre szükség. Egy és két vendég érkezése esetén nagyon egyszerű fejben is kiszámolni a variációkat, mivel egy vendég esetén egy egyfős, két vendég esetén pedig vagy két egyfős, vagy egy kétfős szobát ajánlunk fel. Három vendég érkezésekor azonban már kezd bonyolódni a helyzet.
Próbáljuk meg három vendégre alkalmazni a Q(n) függvényt (ahol n > 0):
Q(3) = Q(2) + Q(1) + 1
Amennyiben van n-fős szobánk, abban az esetben plusz egy variációt fel kell jegyeznünk, mivel el tudjuk helyezni az összes vendéget egy szobában.
Az egyenlet lépésenkénti megoldása:
Q(3) = 2 + 1 + 1
Q(3) = 4
Ez viszont hibás eredményt ad.
Ha szövegesen követjük a függvények feloldását, akkor meglátjuk miért.
Három vendég érkezése esetén a lehetőségek a következőkből állnak össze:
- egy darab egyfős szoba plusz a két vendégre vonatkozó variációk
- egy darab kétfős szoba plusz az egy vendégre vonatkozó variációk
- egy darab háromfős szoba
Amennyiben végrehajtjuk a rekurzív kibontást:
- egy darab egyfős szoba plusz két darab egyfős szoba
- egy darab egyfős szoba plusz egy darab kétfős szoba
- egy darab kétfős szoba plusz egy darab egyfős szoba
- egy darab háromfős szoba
Itt már jól látszik, hogy az 1×1+1×2 és 1×2+1×1 variációk csak a felírásuk sorrendjében különböznek. Mivel a feladatkiírás szempontjából az, hogy ki kivel alszik egy szobában nem számít, ezért a két kombináció egyenrangú.
Ezekre az ellenőrzésekre vonatkozik a unique() függvény a számítás során, mivel a Q(n) eredményének meghatározásakor figyelmen kívül kell hagynunk a duplikátumokat.
PHP-kód v1
Mostanra felállítottunk egy elméleti számítási módot, és tudjuk, hogy rekurzív függvényt kell írni. Ezek ismeretében el tudjuk készíteni a kód első változatát.
<?php function calc_room_use ($passengers) { // a függvény csak pozitív egész számokon értelmezhető if ($passengers < 1) { return array(); } // ide gyűjtjük majd a lehetséges variációkat $variations = array(); // mind a négyféle szobába megpróbáljuk elosztani a vendégeket for ($rn = 1; $rn <= 4; $rn += 1) { if ($passengers >= $rn) { // kiszámítjuk a Q(n-x) variációkat $uplevel_variations = calc_room_use($passengers - $rn); $actual_variation = $rn; // ez a ciklus felel meg a unique()-nak foreach ($uplevel_variations as $variation) { // minden variációt egy string-ként tárolunk a tömbben $actual_variation = explode(',', $variation); // az előző szint variációihoz hozzáírjuk az aktuális szoba méretét $actual_variation[] = $rn; // sorba rendezzük, hogy a 2,1 és az 1,2 eseteket ki tudjuk szűrni sort($actual_variation); $actual_variation = implode(',', $actual_variation); // és ha nincs ilyen variáció még, akkor felvesszük a lehetségesek közé if (! in_array($actual_variation, $variations)) { $variations[] = $actual_variation; } } // az egy szobában épp elférünk variációját is fel kell vezetni if ($passengers == $rn && ! in_array($rn, $variations)) { $variations[] = $rn; } } } return $variations; } // leszámoljuk és kiírjuk a variációkat echo count(calc_room_use(25)); ?> |
A kód erőforráshasználata diagramon ábrázolva:
Szöveges értelmezésben:
- 1 másodpercen belül kiszámítható: 18 fő
- 30 másodpercen belül kiszámítható: 23 fő
- 25 fő érkező vendég kiszámítása: 86.33 másodperc
- 128 MB memórialimit elérése: nem a közeljövőben valószínű
Értékelés: szánalmas.
Ezek alapján az első kódverzió nem teljesít a követelménykorlátokon belül, ezért átalakításra szorul. És egyben elkezdődik az evolúciója…
MySQL jogosultság-szervezés MAC-alapú kivétel Mikrotik hotspot-ba
Comments are currently closed.