MikoAndras.hu

Mikó András személyes oldalai

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.

Számítási idő

Számítási idő

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ámítási idő v2

Számítási idő v2

Memóriahasználat v2

Memóriahasználat v2

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…

Pages: 1 2 3 4 5 6 7

, , ,

Comments are currently closed.