MikoAndras.hu/en

Personal pages for Andras MIKO

Code optimizations in PHP

I got in the reach of a really interesting problem as I was talking with a friend. This got me to try various optimization techniques in practice. One of the beauties is that it only contains php-code (there are no mind-numbing html hacks, or sql/io bottlenecks), so I could concentrate on the level of the algorithmic challenges only.

The simple wording of the problem, and its evolution got me to document the process, and to show techniques known to me through it.

The objective

A group of 25 arrives at a hotel. Calculate the ways we could offer them accommodation, if we have 1, 2, 3 and 4 people bedrooms (and we have unlimited amount of them), we use all offered rooms to the fullest (there are no empty beds in the assigned rooms), and there are no rules for who wants – or does not want – to be with whom in the same room.

Limitations

The calculation has to come to a successful end in 1 second on a desktop machine. Test have a time limit of 90 seconds, and memory limit 128MB.
During my research I have chosen BEORNEGAR [Sabertooth X58; Core i7@3.06GHz; 12GB ram; 128GB SSD].

Teaser

In the graphs below are the before/after states. I want to create interest for reading the full post, as it got a bit long. In spite of that the curves show that the techniques used in this article can help to big gains when properly used.

The run-time depending on the number of guests (X-axis is number of guests, Y-axis is elapsed time in seconds):

Run-time before/after

Run-time before/after

Memory-usage with the same X-axis:

Memory-usage befora/after

Memory-usage befora/after


The curve for the first version is short, because it got up to 90 seconds runtime too quickly, so I could not gather any more data. The speed development can be seen also on the mid-versions’ memory-usage as well.

Analyse

For the calculations we need a model. Our function has to produce the following output:

parameter is the number of guests, output is the number of variations

Q(1) = 1 (one piece of one-people bedroom)
Q(2) = 2 (one pcs two-people, two pcs one-people)
Q(3) = 3 (one pcs three-people, one pcs two-people and one pcs one-people, or three pcs one-people bedroom)
Q(4) = 5 (in short: 1×4, 1×3+1×1, 1×2+2×1, 2×2, 4×1)

All other cases:
Q(n) = unique( Q(n-1) + Q(n-2) + Q(n-3) + Q(n-4) )

Using uniqe() on a result of an addition can be deceivable. I have written it, because there is no other way to say, that we have to eliminate duplicate variations created by the four different function-runs.

Let’s go through the calculation steps, and we can conclude why this is neccessary. With one and two guests it is really easy to get the numbers, with one guest we offer a one-bedroom and with two guests either one two-bedroom or two one-bedrooms. The equation starts to be difficult already with three guests.
Try to use the equation Q(n) on three guests (where n > 0):

Q(3) = Q(2) + Q(1) + 1

In case we have an n-bedroom we have to note one more variation, because we can put all the guests in the same room.

The step-by-step calculation is like:
Q(3) = 2 + 1 + 1
Q(3) = 4

But this gives a wrong solution.

We could go over the steps in text, to get a better picture.

With three arriving guests the variations are as follows:

  • one one-bedroom and the variations for two guests
  • one two-bedroom and the variations for one guest
  • one three-bedroom

After unfolding the recursive functions:

  • one one-bedroom and two one-bedrooms
  • one one-bedroom and one two-bedroom
  • one two-bedroom and one one-bedroom
  • one three-bedroom

Here it can be more easily observed, that the variations 1×1+1×2 and 1×2+1×1 only differ in the order. In the spirit of the task the problem who-is-roomed-with-whom is irrelevant, so the two combinations should be treated as one.

Exactly for these checks was the function unique() built, because we have to dump duplicates while calculating resolutions on Q(n).

PHP-code v1

We have the theoretics of the calculation, and we know it has to be realised in a recursive function. So the first version can be created.

<?php
  function calc_room_use ($passengers) {
    // the function is only meaningful on positive integers
    if ($passengers < 1) {
      return array();
    }
    // to hold the variations
    $variations = array();
    // try to divide the guests into the available rooms
    for ($rn = 1; $rn <= 4; $rn += 1) {
      if ($passengers >= $rn) {
        // calculate the Q(n-x) variations
        $uplevel_variations = calc_room_use($passengers - $rn);
        $actual_variation = $rn;
        // this cycle fits unique()
        foreach ($uplevel_variations as $variation) {
          // every variation will be stored as a string
          $actual_variation = explode(',', $variation);
          // we write the actual room to the previous level's variations
          $actual_variation[] = $rn;
          // sort them, to eliminate 2,1 and 1,2 cases
          sort($actual_variation);
          $actual_variation = implode(',', $actual_variation);
          // if we do not have such variation, we write it to the possibilities
          if (! in_array($actual_variation, $variations)) {
            $variations[] = $actual_variation;
          }
        }
        // the we-can-fit-in-a-single-room must be added as well
        if ($passengers == $rn && ! in_array($rn, $variations)) {
          $variations[] = $rn;
        }
      }
    }
    return $variations;
  }
  // count and print variations
  echo count(calc_room_use(25));
?>

Resource-use on a graph:

Calculation time

Calculation time

Memory use

Memory use

In text:

  • Calculated in 1 second: 18 person
  • Calculated in 30 seconds: 23 person
  • 25 arriving guests: 86.33 seconds
  • 128 MB memorylimit: not in foreseeable future

Rating: pitiable.

According to this the first version does not complete, so it must be worked on. And so its evolution starts…

Pages: 1 2 3 4 5 6 7

, , ,

Leave a Reply

Your email address will not be published. Required fields are marked *

*

*

You may use these HTML tags and attributes: <a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>