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

所以，你可以在同樣的速度在Python的PHP的結果。

Answer 1

當然，PHP會陷入無限循環。有沒有辦法可以採取那麼久，如果沒有錯......

我不認爲這些數字的數字與strlen將在PHP中工作。 PHP使用科學記數法處理數字，精度低於Python。

我加了調試echo語句到PHP，打印出$ 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中那樣工作。

Answer 2

這不是速度問題，它是終止條件下的邏輯問題。

它可能不會完成。當您在while測試中將$ fibonacci的當前值轉換爲字符串時，將其轉換爲科學格式並在您將其轉換爲字符串時截斷爲一組有限的小數位（取決於您的精度設置）。這個數字的數量將會遠遠少於1000，所以終止條件永遠不會被滿足。

Answer 3

由於問題似乎與轉換爲字符串，這是一個更快的方式來做到這一點，並不需要它。這與你發佈的算法基本相同（所以我不覺得對你顯示不好），但演示瞭如何使用除法來測試整數的長度，而不是將其轉換爲字符串。

def fibonacci_digits(limit): 
    limit = 10**limit 
    fib = 1 
    old1 = 0 
    old2 = 1 

    i = 1 
    size = 1 
    while size < limit: 
     fib = old1 + old2 
     if not size//fib: # // is pythons integer division operator, not a comment 
      size *= 10 
     old1 = old2 
     old2 = fib 
     i += 1 

    return i 

print fibonacci_digits(1000) 

轉換爲字符串很慢，幾乎從不是正確的做法。以下是時間結果：

$ python -mtimeit -s'import fib' 'fib.fibonacci_digits(1000)' 
10 loops, best of 3: 30.2 msec per loop 

$ python -mtimeit -s'import fib' 'fib.fibonacci_digits2(1000)' 
10 loops, best of 3: 1.41 sec per loop 

Answer 4

許多項目歐拉問題將不得不處理大數字。 PHP將使您的大數字看起來像2.579234678963E+12這是數字的指數表示...顯然很難合作。 因此，對於大多數問題，最好與BCMath Functions一起去。這將保持你的號碼，即使它是一個巨大的數字。

請注意，使用echo bcmul(500,500);將永遠不會像echo 500*500那樣快。並且，BCMath函數返回值始終是字符串。

要解決您的問題，請將所有算術運算替換爲相應的BCMath函數。

Answer 5

問題是，你正在使用大數字。您應該使用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.095s。

Answer 6

我優化了一下Python代碼。使用len（str（））來檢查數字的數量是非常緩慢的。通過math.log10替代運行您的程序要快得多

的第一項在Fibonacci序列中包含1000個數字是：4782 計算在0.008573秒

import time 
from math import log10 


def digits(n): # Return the number of digits for n>=1 
    return int(log10(n))+1 

fibonacci = 1L # Thanks to Python to handle very big numbers 
old1 = 0 
old2 = 1 
limit = 1000 

i = 1 


start = time.time() #Start timer for bench 
while digits(fibonacci) < limit: 
    fibonacci = old1 + old2 
    old1 = old2 
    old2 = fibonacci 
    i += 1 



print "The first term in the Fibonacci sequence to contain %s digits is : %s" % (str(limit), str(i)) 

print "Calculated in %3.6f seconds" % (time.time() - start)