PHP recursive efficiency analysis

  • 2020-03-31 19:24:01
  • OfStack

And it's three times less efficient. Therefore, recursion in PHP must be treated with care.
Recently, I wrote a quicksort algorithm and found that the recursive efficiency in PHP is not one-size-fits-all and may behave differently in different servers.

function qsort(&$arr) 
{ 
_quick_sort($arr, 0, count($arr) - 1); 
} 

 
function _quick_sort(&$arr, $low, $high) 
{ 
$low_data = $arr[$low]; 
$prev_low = $low; 
$prev_high = $high; 
while ($low < $high) 
{ 
while ($arr[$high] >= $low_data && $low < $high) { 
$high--; 
} 
if ($low < $high) { 
$arr[$low] = $arr[$high]; 
$low++; 
} 
while ($arr[$low] <= $low_data && $low < $high) { 
$low++; 
} 
if ($low < $high) { 
$arr[$high] = $arr[$low]; 
$high--; 
} 
} 
$arr[$low] = $low_data; 
if ($prev_low < $low) { 
_quick_sort($arr, $prev_low, $low); 
} 
if ($low + 1 < $prev_high) { 
_quick_sort($arr, $low + 1, $prev_high); 
} 
} 

function quick_sort(&$arr) 
{ 
$stack = array(); 
array_push($stack, 0); 
array_push($stack, count($arr) -1); 
while (!empty($stack)) { 
$high = array_pop($stack); 
$low = array_pop($stack); 
$low_data = $arr[$low]; 
$prev_low = $low; 
$prev_high = $high; 
while ($low < $high) 
{ 
while ($arr[$high] >= $low_data && $low < $high) { 
$high--; 
} 
if ($low < $high) { 
$arr[$low] = $arr[$high]; 
$low++; 
} 
while ($arr[$low] <= $low_data && $low < $high) { 
$low++; 
} 
if ($low < $high) { 
$arr[$high] = $arr[$low]; 
$high--; 
} 
} 
$arr[$low] = $low_data; 
if ($prev_low < $low) { 
array_push($stack, $prev_low); 
array_push($stack, $low); 
} 
if ($low + 1 < $prev_high) { 
array_push($stack, $low + 1); 
array_push($stack, $prev_high); 
} 
} 
}

Here is the code to test the speed:
 
function qsort_test1() 
{ 
$arr = range(1, 1000); 
shuffle($arr); 
$arr2 = $arr; 
$t1 = microtime(true); 
quick_sort($arr2); 
$t2 = microtime(true) - $t1; 
echo " Cost of non-recursive calls: " . $t2 . "n"; 
$arr1 = $arr; 
$t1 = microtime(true); 
qsort($arr1); 
$t2 = microtime(true) - $t1; 
echo " Cost of recursive call: " . $t2 . "n"; 
 }  

In my IIS server (CGI) mode, my test results are:
Cost of non-recursive calls: 0.036401009559631
Cost of recursive call: 0.053439617156982
On my Apache server, my test results are:
Cost of non-recursive calls: 0.022789001464844
Cost of recursive call: 0.014809131622314
The result is the exact opposite, and the PHP version is the same.
It seems that the efficiency of recursion to a specific problem specific analysis.

Related articles: