Recursive min and max functions in PHP and speed test

Recursive min and max functions in PHP and speed test

Created:05 Aug 2017 15:03:39 , in  Maths

This article provides two more examples of PHP functions which employ linear recursion. They are min() and max(). I wrote them partly for fun, but also to carry out a basic speed test on a piece of interpreted PHP code, results of which I hoped, would give me some insight into how stuff written in PHP compares to similar in application but optimized and written in C, hence compiled, solution.

Obviously, PHP is non-starter in comparison to C as far as speed performance is concerned. If you have programmed for a while you know that very well. Still, it is interesting to see how wide the chasm between the two languages can be.

Recursive min and max functions

My min and max are static methods of class LinearRecursion. Like the original functions shipped with PHP, they accept an array of numbers and return smallest and greatest of them respectively.

Here is the code:


/*
  Class: LinearRecursion 
  Description: Provides recursively defined min and max methods
  Author: Sylwester Wojnowski
  WWW: wojnowski.net.pl

  Methods:
    min - find smallest value in a list of numbers
      return Int/Float
    max - find greatest value in a list of numbers
      return Int/Float 
*/
 
class LinearRecursion{
  // recursive max function
  public static function max($sequence,$max = null){ 
    $max = null !== $max ? $max : null;
    // deal with base case of empty sequence
    if(empty($sequence)){return $max;}
  
    $term = array_pop($sequence);
    // first considered terms is always greatest
    if($max === null){ $max = $term;}
    // compare current term to the largest term
    if($term > $max){ $max = $term; }
    return self::max($sequence,$max);  
  }

  // recursive min function
  public static function min($sequence,$min = null){ 
    $min = isset($min) ? $min : null;
    // deal with base case of empty sequence
    if(empty($sequence)){return $min;}

    $term = array_pop($sequence);
    // first considered terms is always smallest
    if($min === null){ $min = $term;}
    // compare current term to the largest term
    if($term < $min){ $min = $term; }
    return self::min($sequence,$min);  
  }
} 

Use examples

Below are two quick use examples:


LinearRecursion::max(array(19,3,1,-9,0));
=> 19

LinearRecursion::min(array(19,3,-1,11,0));
=> -1

Speed benchmark

Here I look at how fast / slow my min() and max() are. I do this using the following piece of code:


class BasicSpeed{
  public static function test($func){
    $s = microtime(true);
    $func();
    return number_format(microtime(true) - $s,8); 
  }
}

BasicSpeed has method "test". Roughly speaking, test() returns formatted number of seconds it takes for a piece of code passed to it as parameter to complete its execution.

To ensure, xdebug PHP extension does not get in the way when executing recursive code for arrays with many items, I also set xdebug maximum nesting level to 1510 and increased PHP memory limit from 128MB to 196MB.


ini_set('xdebug.max_nesting_level', 1510);
ini_set('memory_limit', "196M");

Here is a basic measurement for LinearRecursion::max and PHP max().


// recursive max, sequence of 1500 terms
BasicSpeed::test(function(){
  $sequence = range(0,1499);
  shuffle($sequence);
  LinearRecursion::max($sequence);
});

// PHP max, sequence of 1500 terms
BasicSpeed::test(function(){
  $sequence = range(0,1499);
  shuffle($sequence);
  max($sequence);
});

I have made 800 such measurements. Each entry in the second and third column of the table below is the median of 50 results found with the above method. The first column contains number of items in array passed to LinearRecursion::max and PHP max. The fourth column contains difference in measurements of columns two and three. The fifth and sixth column contain average rates of growth for both functions.


Array length   | LR::max()       | PHP max()  | Difference (ms) | RofGr (LR::max())| RofGr (PHP max)   
-----------------------------------------------------------------------------------------------
10             | 0.00017309     | 0.00003099  | 0.1421          | -              | -
-----------------------------------------------------------------------------------------------
50             | 0.00076699     | 0.00005007  | 0.71692         | 0.000015       | 0.000000477
-----------------------------------------------------------------------------------------------
100            | 0.00200701     | 0.00008798  | 1.91903         | 0.000025       | 0.000000758
-----------------------------------------------------------------------------------------------
200            | 0.00797796     | 0.00016499  | 7.81297         | 0.000060       | 0.00000077
-----------------------------------------------------------------------------------------------
500            | 0.03810000     | 0.00029397  | 37.80603        | 0.000100       | 0.000000490
-----------------------------------------------------------------------------------------------
750            | 0.07975197     | 0.00043988  |79.31209         | 0.000170       | 0.000000584
-----------------------------------------------------------------------------------------------
1000           | 0.14200997     | 0.00050783  |141.50214        | 0.000250       | 0.000000272
-----------------------------------------------------------------------------------------------
1500           | 0.32479286     | 0.00079298  |323.99988        | 0.000370       | 0.000000570

A quick glimpse at the result table gives fairly good idea about the performance of PHP max() anad LinearRecursion::max().

Also, the results sheds light on how fast each of the functions become slower and slower at returning greatest number in the array. For larger number of items in passed list, speed at which PHP max() does is in the region of 0.1% of the speed of LinearRecursion::max().

Conclusion

As stated at the beginning of this experiment, as far as speed performance is concerned, interpreted PHP code is nowhere near compiled C one. The chasm is huge. As the number of items in array grows, the gap becomes wider and wider very quickly.

To restate the above, instead of writing your own PHP code, whenever possible, use what's provided, optimized and compiled for you.

Alternative way of finding max term in an array

PHP max() is not the only game in town for finding the largest number in array. I looked at sorting the list first and next accessing the last item. Theoretically, the method should be very fast. Practically, it is twice as slow compared to max(). Below is a quick result.


// time taken 0.00362110
echo BasicSpeed::test(function(){
  $sequence = range(0,5999);
  shuffle($sequence);
  return max($sequence);
});
// time taken 0.00884295
echo BasicSpeed::test(function(){
  $sequence = range(0,5999);
  shuffle($sequence);
  sort($sequence);
  return $sequence[5999];
});

Final thoughts

That interpreted code turns out to be (too) slow for many even only slightly involved cases is a well-known fact. Nonetheless, no matter what crude tools and methods you use for the purpose, it is instructive to spend a little bit of time to prove the truth to yourself.

This post was updated on 05 Aug 2017 20:26:28

Tags:  php ,  recursion 


Author, Copyright and citation

Author

Sylwester Wojnowski

Author of the above article, Sylwester Wojnowski, is sWWW admin and owner.He enjoys doing Maths and studying algorithms, writing code in scripting and command languages, Thrash Metal music and playing electric guitar.

Copyrights

©Copyright, 2017 Sylwester Wojnowski. This article may not be reproduced or published as a whole or in parts without permission from the author. If you share it, please give author credit and do not remove embedded links.

Computer code, if present in the article, is excluded from the above and licensed under GPLv3.

Citation

Cite this article as:

Wojnowski, Sylwester. "Recursive min and max functions in PHP and speed test." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/recursive-min-and-max-functions-in-php-and-speed-test