Python与PHP速度对比

Question

我想解决一个来自Project Euler的问题（顺便说一下，是第25题），我在Python中找到了一个解决方案：

fibonacci = 1
old1 = 0
old2 = 1
limit = 1000

i = 1

while len(str(fibonacci)) < limit:
    fibonacci = old1 + old2
    old1 = old2
    old2 = fibonacci
    i = i + 1

print(i)

这个计算用了1.5秒。

我在PHP中实现了同样的代码，代码如下：

$fibonacci = 1;
$old1 = 0;
$old2 = 1;
$limit = 1000;

$i = 1;

while (strlen((string)$fibonacci) < $limit){
    $fibonacci = $old1 + $old2;
    $old1 = $old2;
    $old2 = $fibonacci;
    $i = $i + 1;
}
print($i);

结果却花了超过30分钟，还在计算中……

我知道Python通常比PHP快，但这差距也太大了吧。有没有办法优化我的PHP代码，让结果计算得更快呢？

编辑：

根据下面的评论，我修改了这个帖子，最开始我的解决方案是行不通的。一个解决方案是把旧的while循环换成这个：

while (strlen(number_format($fibonacci, 0, '', '')) < $limit){ ... }

但速度问题依然很严重。

所以最终的解决方案是使用BCMath：

$fibonacci = '1';
$old1 = '0';
$old2 = '1';
$limit = 1000;

$i = 1;

while (strlen($fibonacci) < $limit){

    $fibonacci = bcadd($old1, $old2);
    $old1 = $old2;
    $old2 = $fibonacci;
    $i = $i + 1;
}
echo $fibonacci . "<br />";
print($i);

这样你就可以在PHP中以和Python一样的速度得到结果。

Answer 1

问题在于，你正在处理很大的数字。你应该使用BC数学函数（php.net/bc）。这样你的代码可以是：

$fibonacci = "1";
$old1 = "0";
$old2 = "1";
$limit = 1000;

$i = 1;

while (strlen($fibonacci) < $limit){
    $fibonacci = bcadd($old1, $old2);
    $old1 = $old2;
    $old2 = $fibonacci;
    $i = $i + 1;
}
print($i);

我试过了，这样大约需要0.095秒。

Answer 2

这不是速度的问题，而是你在判断循环结束条件时的逻辑问题。

这个循环可能永远不会结束。当你在循环条件中把当前的$fibonacci值转换成字符串时，它会变成科学计数法，并且小数位数会被限制（这取决于你的精度设置）。这个数字的位数会远远少于1000，所以循环的结束条件永远达不到。

Answer 3

没错，PHP 代码陷入了无限循环。如果没有什么问题的话，肯定不会花这么长时间...

我觉得用 strlen 来计算这些数字的位数在 PHP 中可能行不通。因为 PHP 处理这些数字时使用的是科学计数法，而且精度比 Python 低。

我在 PHP 代码中加了调试用的 echo 语句，这样可以在每一步打印出 $fibonacci 和 $i 的值。

在 Python 中，一行代码看起来是这样的：

fib is 7540113804746346429
i is 92

在 PHP 中，这样写：

fib is 7.54011380475E+18
i is 92

要在 PHP 中实现这个功能，你可能需要使用一个更高精度的数学库。

可以看看这个链接 http://www.php.net/manual/en/book.bc.php - 你可以使用 bcadd 函数来进行加法运算，它的效果和 Python 中一样。