PHP 中的算法基准毫无意义吗？

Question

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

当我达到80!时，递归函数与迭代方法相比，速度完全不及格，并且逐渐飙升，而迭代则保持稳定的直线，实际上是这样的（x =阶乘， y = 秒):

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

在脚本语言中以这种方式对算法进行基准测试是否毫无用处？

编辑：对于 NullUserException：

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

Answer 1

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

来吧，加入黑暗面吧。

Answer 2

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));

Answer 3

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

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

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

---

正如 Mike Axiak 在评论中指出的那样，您甚至没有在这里测试不同的算法，您正在测试同一算法的两种不同实现：从 n 保持在 i 上运行的产品> 到 1。使用与目标不同的语言来执行此操作几乎总是毫无意义的。

Answer 4

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

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

Answer 5

递归与迭代实现应该对特定算法的渐近行为没有真正的影响。在某些语言（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

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

Answer 6

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

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

Answer 7

您正面临 PHP 不擅长递归的问题。人们通常不会选择 PHP 来做这种事情。始终选择最适合工作的工具。