Code optimizations in PHP

2013-11-01 kms Android, 0

Diet – optimizing memory usage

In the war for optimizing the memory we attack on the whole source. There can be code being able to function with a bit less memory in any corner.

So we switch into a collecting agent, and want to get some of the lent memory back. And not just a little bit…

Attacked points:

• discarding not used data
• manual “garbace collection”
• redesigning the data-structure

Not used data

In the fourth variation we started to compare the array-keys, so the value side data is on ly used in the foreach:

      [...]
        foreach ($variation_cache[$passengers - $rn] as $variation) {
      [...]

There is an extended version of foreach, where we can read the keys from the array into a local variable. With this modification the value side is not needed anymore, because we only use the key side. And we can agree that in spite of storing the whole variation using a boole:true takes up way less space.

After modification:

      [...]
        foreach ($variation_cache[$passengers - $rn] as $variation => $devnull) {
      [...]
            $variation_cache[$passengers][$actual_variation] = true;
      [...]
          $variation_cache[$passengers][$rn] = true;
      [...]

Manual GC

The code only works with variation groups which are not more far away from the actual number than 4:
Q_(n) = unique( Q_(n-1) + Q_(n-2) + Q_(n-3) + Q_(n-4) )

Because of that every variation group can be discarded, we will not need them anymore.

  function calc_room_use ($passengers, &$variation_cache) {
    [...]
    unset($variation_cache[$passengers - 4]);
  }

With this little part we get the garbage collector to free up not used memory space. Automatic collection would not get them, as long as $variation_cache has valid pointers to the not used groups.

Redesigning the data-structure

Many times we get stuck with inherited data-structures and ideas, although we could have better/faster/smaller solution. In these cases it is advised to go the additional step, the gain can be great.
The string holding the actual variation uses commas to give a human readable version since the first version. Implode and explode became also more understandable (there is no impact on functionality whether we use a separator or not).
This is currently the following (for 30 guests):

          $actual_variation = "1,1,1,1,2,2,3,3,4,4,4,4";

We know, that room numbers are all one-digit numbers, we do not need a separator to have the algorithm run. With a small modification it occupies only the half of the memory as before, but functionality remains the same:

          $actual_variation = "111122334444";

Codepart according the new ideas:

      [...]
            $actual_variation = $rn . $variation;
      [...]
            $actual_variation = $variation . $rn;
      [...]
                $actual_variation = substr_replace($variation, $rn, $pos + 1, 0);
      [...]

Resource usage of the sixth version:

Calculation time v6

Memory usage v6

In text:

• Calculated in 1 second: 98 guests
• Calculated in 30 seconds: 222 guests
• 25 arriving guests: 0.006 seconds
• 128MB memorylimit: at calculating 257 guests

Rating: I would give my name to this one

Version sixth was born a few months later than the second version, which was up to the task in the original task. Based on these I think that its evolution is not nearly at the end. If we look on v6 as the “code sapiens” there has to be the possibility of the “code sapiens superior”…

Given the first version is published in its entirety, I think it is best to get v6 also out there (this time without comments, because all of the lines were introduced already before):

<?php
  $variation_cache = array(0 => array());
  function calc_room_use ($passengers, &$variation_cache) {
    if ($passengers < 1) {
      return 0;
    }
    for ($rn = 1; $rn <= 4; $rn += 1) {
      if ($passengers >= $rn) {
        if (! isset($variation_cache[$passengers - $rn])) {
          calc_room_use($passengers - $rn, $variation_cache);
        }
        if (! isset($variation_cache[$passengers])) {
          $variation_cache[$passengers] = array();
        }
        $actual_variation = $rn;
        foreach ($variation_cache[$passengers - $rn] as $variation => $devnull) {
          if ($rn == 1) {
            $actual_variation = $rn . $variation;
          } else if ($rn == 4) {
            $actual_variation = $variation . $rn;
          } else {
            for ($lrn = $rn; $lrn > 0; $lrn -= 1) {
              $pos = strrpos($variation, (string)$lrn);
              if ($pos !== false) {
                $actual_variation = substr_replace($variation, $rn, $pos + 1, 0);
                break;
              }
            }
          }
          if (! isset($variation_cache[$passengers][$actual_variation])) {
            $variation_cache[$passengers][$actual_variation] = true;
          }
        }
        if ($passengers == $rn && ! isset($variation_cache[$passengers][$rn])) {
          $variation_cache[$passengers][$rn] = true;
        }
      }
    }
    unset($variation_cache[$passengers - 4]);
  }
  calc_room_use($passengers, $variation_cache);
  echo count($variation_cache[$passengers]);
?>

And on the upcoming page all the manager-spirited readers can satisfy their needs for graphs and tables.

Pages: 1 2 3 4 5 6 7

development, dynamic programming, optimizations, php

Tracking monthly expenses 3.0 MAC-based exception in a Mikrotik hotspot