1

由于 PHP 对我来说更简单，我希望在其中对算法进行基准测试以获得乐趣，因此我选择了阶乘。

与迭代法相比，起床时递归函数速度完全下降80!，并逐渐向上暴涨，而迭代法有一条稳定的线，实际上是这样的（x = 阶乘，y = 秒）：

http://i52.tinypic.com/2a9s7z4.png

但是在 C/Java 中（我刚刚在其中实现了测试）显示相同的结果，彼此之间只有 1-5% 的折扣，几乎相同的速度。

在脚本语言中以这种方式对算法进行基准测试是没有用的吗？

编辑：对于 NullUserException：

function factrec($x) {
    if($x <= 1) {
        return $x;
    } else {
        return $x * factrec($x - 1);
    }
}
4

7 回答 7

4

用脚本语言对算法进行基准测试绝对不是毫无意义的。完成基准测试后，您会在 PHP 中使用哪种阶乘实现？（假设由于某种原因你不能使用内置的。）

用一种语言进行基准测试是毫无意义的，这种语言的特性与你想要实现算法的语言有很大不同。在这里，PHP 中函数调用和语句的相对成本if显着扭曲了结果（或者这是我最好的猜测）。如果您仔细了解为什么会发生这种情况并避免它，那么它仍然可以取得丰硕成果：您注意到差异会更加夸张。归结为是否更容易用目标语言编写或解决差异。

算法复杂度的简单计算应该足以决定使用哪一个，或者至少缩小选择范围。

正如 Mike Axiak 在评论中指出的那样，您甚至没有在这里测试不同的算法，而是在测试同一算法的两种不同实现：让正在运行的产品i从n到1. 用与目标不同的语言来做这件事几乎总是毫无意义的。

于 2010-09-27T23:11:06.057 回答
1

在我看来，如果我要测试算法本身，我会选择 C/C++，以获得它可以在最佳条件下提供的“原始力量”。

另一方面，如果我必须选择哪种算法在某种条件下效果最好，我会尽量复制这种条件。它必须放在 PHP 应用程序中吗？让我们在 PHP 中使用 PHP 提供的结构对其进行测试。它是否需要与 STL 容器一起使用？我将在这种情况下进行测试，而不仅仅是使用数组。恕我直言，在真实条件下进行测试是获得有意义结果的关键。得到这样的结果后，另一件好事是调整这些条件（只要你可以在项目中改变它们），看看你得到了什么效果，找到最好的条件-算法对。

于 2010-09-27T23:09:49.820 回答
1

递归与迭代实现对特定算法的渐近行为应该没有真正的影响。在某些语言（scala、Scheme、Lua、Standard ML、Mozart/Oz、erlang）中，两者实际上可以写成完全相同。即如下方案代码：

(define factorial
  (lambda (n acc)
    (if (= n 0) acc
        (factorial (- n 1) (* n acc)))))
(factorial 5 1)
-> 120

不会使用堆栈，因此执行与迭代方法相同的操作。（这称为尾调用优化，在执行尾递归时会以这种语言调用。）

于 2010-09-27T23:11:23.760 回答
1

基准测试从来都不是毫无意义的。如果您有一些以任何语言编写的代码，这对您的应用程序来说太慢了，那么您就会找出瓶颈。查看这些瓶颈，您会寻找解决方案。一种解决方案可能是使用不同的算法公式，甚至用不同的语言重写。

我对PHP一无所知，所以我不知道在那种环境中递归是否处理得很好，但我的印象是它不是实现重型重复数学的好选择......

于 2010-09-27T23:12:36.553 回答
1

您遇到了 PHP 递归能力差的问题。人们通常不会选择 PHP 来做这种事情。始终为工作选择最佳工具。

于 2010-09-27T23:13:50.920 回答
1

考虑到练习的目的很有趣，它不能没有意义！但是尝试让 PHP 执行递归计算可能表明您已经准备好尝试使用函数式编程语言了。你见过哈斯克尔吗？尾调用优化，有人吗？

来吧，加入黑暗面。

于 2010-09-27T23:21:52.687 回答
1

Java 和 C 比 PHP 快几个数量级。
您需要显着增加输入大小才能看到结果。

此外，正如 Aaron McSmooth 所说，用您计划使用的语言以外的语言对算法进行基准测试是没有意义的。

我不确定，但我怀疑 PHP 是否会进行尾调用优化。无论如何，使用尾递归函数应该会大大提高递归函数的性能：

function factorial($n, $product) {
    if ($n < 1)
        return $product;
    else
        return factorial($n-1, $product*$n);
}

print(factorial(80, 1));
于 2010-09-27T23:25:30.927 回答