3

ベンチマーク用に PHP で階乗関数の 2 つのバージョンを作成しました。1 つは通常の再帰を使用し、もう 1 つは末尾再帰を使用します。後者の方が速いはずですが、結果はそうではありません。ここで何か不足していますか？

ベンチマーク テストを含む私のコードは次のとおりです。

<?php
benchmark();

function benchmark()
{
    $n = 10;
    $multiplier = 10000;
    $functions = array('factorial_recursive', 'factorial_tailRecursive');

    foreach ($functions as $function) {
        $start = microtime(true);
        echo $function . '<br>';
        echo $function($n) . '<br>';
        echo ($multiplier * (microtime(true) - $start)) . '<br><br>';
    }
}

function factorial_recursive($n)
{
    if ($n == 1) {
        return $n;
    }

    return $n * factorial_recursive($n - 1);
}

function factorial_tailRecursive($n, $result = 1)
{
    if ($n == 1) {
        return $result;
    }

    return factorial_tailRecursive($n - 1, $result * $n);
}

印刷出力:

factorial_recursive
3628800
2.4199485778809

factorial_tailRecursive
3628800
2.5296211242676

洞察をいただければ幸いです - ありがとう！

4

1 に答える 1

2

私はあなたのコードを取り、コマンドラインで実行するために少し変更しました（brを改行に変換し、出力形式を微調整しました）。また、ベンチマークが1回ではなく25回実行されるように変更しました。

<?php
foreach (range(1, 25) as $iteration) {
    benchmark($iteration);
}

function benchmark($iteration)
{
    $n = 10;
    $multiplier = 10000;
    $functions = array('factorial_recursive', 'factorial_tailRecursive');

    echo "\nIteration {$iteration}:\n";
    foreach ($functions as $function) {
        $start = microtime(true);
        echo $function . "\n";
        echo $function($n) . "\n";
        echo ($multiplier * (microtime(true) - $start)) . "\n\n";
    }
}

function factorial_recursive($n)
{
    if ($n == 1) {
        return $n;
    }

    return $n * factorial_recursive($n - 1);
}

function factorial_tailRecursive($n, $result = 1)
{
    if ($n == 1) {
        return $result;
    }

    return factorial_tailRecursive($n - 1, $result * $n);
}

これが私のphpcliバージョンです：

$ php --version
PHP 5.3.10-1ubuntu3.4 with Suhosin-Patch (cli) (built: Sep 12 2012 19:00:43) 
Copyright (c) 1997-2012 The PHP Group
Zend Engine v2.3.0, Copyright (c) 1998-2012 Zend Technologies
    with Xdebug v2.1.0, Copyright (c) 2002-2010, by Derick Rethans

これが私の25回の反復の結果です。

$ php ./benchmark.php 

Iteration 1:
factorial_recursive
3628800
0.46014785766602

factorial_tailRecursive
3628800
0.33855438232422


Iteration 2:
factorial_recursive
3628800
0.26941299438477

factorial_tailRecursive
3628800
0.26941299438477


Iteration 3:
factorial_recursive
3628800
0.27179718017578

factorial_tailRecursive
3628800
0.2598762512207


Iteration 4:
factorial_recursive
3628800
0.26941299438477

factorial_tailRecursive
3628800
0.2598762512207


Iteration 5:
factorial_recursive
3628800
0.28848648071289

factorial_tailRecursive
3628800
0.28848648071289


Iteration 6:
factorial_recursive
3628800
0.27894973754883

factorial_tailRecursive
3628800
0.27894973754883


Iteration 7:
factorial_recursive
3628800
0.29087066650391

factorial_tailRecursive
3628800
0.2598762512207


Iteration 8:
factorial_recursive
3628800
0.25033950805664

factorial_tailRecursive
3628800
0.25033950805664


Iteration 9:
factorial_recursive
3628800
0.25033950805664

factorial_tailRecursive
3628800
0.2598762512207


Iteration 10:
factorial_recursive
3628800
0.25033950805664

factorial_tailRecursive
3628800
0.24795532226562


Iteration 11:
factorial_recursive
3628800
0.25033950805664

factorial_tailRecursive
3628800
0.27894973754883


Iteration 12:
factorial_recursive
3628800
0.27894973754883

factorial_tailRecursive
3628800
0.27894973754883


Iteration 13:
factorial_recursive
3628800
0.2598762512207

factorial_tailRecursive
3628800
0.25033950805664


Iteration 14:
factorial_recursive
3628800
0.25033950805664

factorial_tailRecursive
3628800
0.27179718017578


Iteration 15:
factorial_recursive
3628800
0.25033950805664

factorial_tailRecursive
3628800
0.24795532226562


Iteration 16:
factorial_recursive
3628800
0.24080276489258

factorial_tailRecursive
3628800
0.25033950805664


Iteration 17:
factorial_recursive
3628800
0.27179718017578

factorial_tailRecursive
3628800
0.25033950805664


Iteration 18:
factorial_recursive
3628800
0.24080276489258

factorial_tailRecursive
3628800
0.25033950805664


Iteration 19:
factorial_recursive
3628800
0.25033950805664

factorial_tailRecursive
3628800
0.25033950805664


Iteration 20:
factorial_recursive
3628800
0.25033950805664

factorial_tailRecursive
3628800
0.2598762512207


Iteration 21:
factorial_recursive
3628800
0.24795532226562

factorial_tailRecursive
3628800
0.23841857910156


Iteration 22:
factorial_recursive
3628800
0.30040740966797

factorial_tailRecursive
3628800
0.29087066650391


Iteration 23:
factorial_recursive
3628800
0.30994415283203

factorial_tailRecursive
3628800
0.26226043701172


Iteration 24:
factorial_recursive
3628800
0.29087066650391

factorial_tailRecursive
3628800
0.32186508178711


Iteration 25:
factorial_recursive
3628800
0.27894973754883

factorial_tailRecursive
3628800
0.30040740966797

これらの結果を見ると、違いはごくわずかであり、呼び出すには近すぎると言わざるを得ません。少なくともBig-Oに関しては、実行時に実質的に同一です。

于 2012-11-30T04:00:11.463 に答える