PHP 再帰効率分析

そして効率は3倍悪くなります。したがって、PHP での再帰は注意して扱う必要があります。
最近、クイックソートアルゴリズムを作成しましたが、PHP の再帰効率は万能ではなく、さまざまなサーバーでは動作が異なる可能性があることがわかりました。

コードをコピー コードは次のとおりです:

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

/**
* 再帰アルゴリズムを使用したクイックソート。
*
* @param array $arr ソートする配列
* @param int $low ソート済みの最も低いサブセクション
* @param int $high ソート済みの最も高いフィールド
*/
function _quick_sort(&$arr, $low, $high)
{
$low_data = $arr[$low];
$prev_low = $low;
$prev_high = $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];
}
}
$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)
while (!empty ($stack)) {
$high = 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];
}
}
$arr[$low] = $low_data ;
if ($prev_low < $low) {
array_push($stack, $prev_low);
if ($low 1) < $ prev_high) {
array_push($stack, $low 1);
}
}


以下は速度をテストするためのコードです:



コードをコピー

コードは次のとおりです:


function qsort_test1()
{
$ arr = range(1, 1000);

$arr2 = $arr;
$t1 (true); $arr2);
$t2 = microtime(true) - $t1;

$t2 のコスト: >$t1 = microtime(true) ; qsort($arr1); $t2 = microtime(true) - $t1; echo "再帰呼び出しのコスト:" 。 ; ｝

IIS サーバー (CGI) モードでのテスト結果は次のとおりです:
非再帰呼び出しのコスト: 0.036401009559631
再帰呼び出しのコスト: 0.053439617156982
私の Apache サーバー上でのテスト結果は次のとおりです:
非再帰呼び出しのコスト: 0.022789001464844
再帰呼び出しのコスト: 0.014809131622314
結果はまったく逆で、PHP のバージョンは同じです。
再帰の効率については詳しく分析する必要がありそうです。