Kód-optimalizálás php-ban
Kód v2 – dinamikus programozás
A dinamikus programozás elve az, hogy egy adott problémát kisebb részekre tördelünk. Azokban az esetekben hatásos igazán, amikor ezek az alproblémák átlapolódnak, egy-egy kisebb részt többször is kiszámítunk mielőtt a teljes megoldáshoz jutnánk.
Az alapötlet igen egyszerű: amikor egy ilyen kisebb részt kiszámítunk, mentsük el – memorizáljuk – az eredményét, és amikor ismét ezt kellene kiszámítani, egyszerűen használjuk fel az előző számítás kimenetét.
Tördelés
Az feladat felírása egyenletekkel az alábbi módon nézett ki négy fő esetére:
Q(4) = unique( Q(3) + Q(2) + Q(1) + 1 )
Tovább bontva:
Q(4) = unique( unique(Q(2) + Q(1) + 1 ) + Q(2) + Q(1) + 1 )
Q(4) = unique( unique( unique(Q(1) + 1 ) + Q(1) + 1) + unique(Q(1) + 1 ) + Q(1) + 1 )
Tehát a Q(4) futása során az alábbi számban hívja meg a kisebb részek számítási függvényeit:
- 3 fő: 1 alkalom
- 2 fő: 2 alkalom
- 1 fő: 4 alkalom
A lista pedig exponenciálisan emelkedik, minél több vendég elszállásolását kell megoldani. Ez az emelkedés látszik az első kód időfüggvényén is.
Több megoldás is van arra, hogyan memorizáljuk kód szinten a már kiszámított variációkat, az én megközelítésem a megosztott változó használata. Ehhez a függvény paraméterlistáját és ennek megfelelően a meghívását is módosítani kell.
<?php // a cache-tömb kezdőértéke 0 vendégre egy üres variációhalmaz $variation_cache = array(0 => array()); // a cache-t cím szerint adjuk át a paraméterben, hogy a beleírt változtatások // a hívó kódban is láthatóak legyenek function calc_room_use ($passengers, &$variation_cache) { if ($passengers < 1) { return 0; } for ($rn = 1; $rn <= 4; $rn += 1) { if ($passengers >= $rn) { // csak akkor számoljunk rész-variációt, ha még nem számoltuk ki if (! isset($variation_cache[$passengers - $rn])) { calc_room_use($passengers - $rn, $variation_cache); } // az aktuális vendég-szám variációtárolója alapesetben üres if (! isset($variation_cache[$passengers])) { $variation_cache[$passengers] = array(); } $actual_variation = $rn; // itt már biztos elérhető a cache-ben a részvariáció-halmaz foreach ($variation_cache[$passengers - $rn] as $variation) { $actual_variation = explode(',', $variation); $actual_variation[] = $rn; sort($actual_variation); $actual_variation = implode(',', $actual_variation); // szintén a cache-ben ellenőrzünk if (! in_array($actual_variation, $variation_cache[$passengers])) { // és oda írunk be is $variation_cache[$passengers][] = $actual_variation; } } if ($passengers == $rn && ! in_array($rn, $variation_cache[$passengers])) { $variation_cache[$passengers][] = $rn; } } } } calc_room_use($passengers, $variation_cache); // a számítási mód annyit változott, hogy a cache-ből kell kiszámolni a variációk számát // nem pedig a függvény értékéből echo count($variation_cache[$passengers]); ?> |
A kód erőforráshasználata az első verzióval összehasonlítva:
Szöveges értelmezésben:
- 1 másodpercen belül kiszámítható: 44 fő
- 30 másodpercen belül kiszámítható: 76 fő
- 25 fő érkező vendég kiszámítása: 0.046 másodperc
- 128MB memórialimit elérése: időlimiten belül kizárt
Értékelés: alakul.
A második verzió már kereteken belül teljesít, viszont még mindig van benne gyorsítási potenciál.
Innentől kezdve a “challenge accepted” mottó vezérel…
MySQL jogosultság-szervezés MAC-alapú kivétel Mikrotik hotspot-ba
Comments are currently closed.