Python vs velocità PHP

Question

voglio risolvere un problema da Project Euler (BTW, problema 25), e ho trovato una soluzione in 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) 

Ci sono voluti 1,5 secondi per calcolare.

ho implementato lo stesso in PHP, questo è il codice:

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

E ci sono voluti più di 30 minuti, e ancora calcolando ...

So che Python è considerato più veloce di PHP , ma ancora non dovrebbe essere una grande differenza. Come migliorare il mio codice PHP per ottenere risultati più velocemente, se c'è un modo per farlo?

EDIT:

modifico questo post sulla base di commenti qui sotto quindi prima la mia soluzione non avrebbe funzionato. Una soluzione può essere al posto della vecchia, mentre a mettere questo:

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

Ma ancora una volta è una questione grande velocità.

Quindi la soluzione finale sta usando 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); 

Così si può ottenere i risultati alla stessa velocità di Python in PHP.

Answer 1

Definitivamente, il PHP sta entrando in un ciclo infinito. Non c'è modo di impiegarlo così a lungo se non ci fosse qualcosa di sbagliato ...

Non penso che il conteggio delle cifre di questi numeri con strlen funzionerà in PHP. PHP tratta i numeri in notazione scientifica, con una precisione inferiore a quella di Python.

Ho aggiunto il debug di istruzioni echo in PHP, per stampare $ fibonacci e $ i per ogni passaggio.

Una tipica linea di Python assomiglia

fib is 7540113804746346429 
i is 92 

In PHP, che è

fib is 7.54011380475E+18 
i is 92 

Per raggiungere questo obiettivo in PHP, avrete probabilmente bisogno di usare una libreria matematica maggiore precisione.

Check out http://www.php.net/manual/en/book.bc.php - è possibile utilizzare la funzione bcadd per completare l'aggiunta e funzionerà come in Python.

Answer 2

Non si tratta di un problema di velocità, è un problema logico al momento per la terminazione.

Probabilmente non finirà. Quando converti il ​​valore corrente di $ fibonacci in una stringa durante il tuo test, esso verrà convertito in formato scientifico e troncato in un numero limitato di posizioni decimali (in base alle tue impostazioni di precisione) quando lo si trasmette alla stringa. Quel numero di cifre sarà molto inferiore a 1000, quindi le condizioni di terminazione while non saranno mai soddisfatte.

Answer 3

Poiché il problema sembra essere la conversione in stringhe, ecco un modo molto più veloce per farlo che non lo richiede. Questo è essenzialmente lo stesso algoritmo che hai pubblicato (quindi non mi sento male mostrarlo a te) ma dimostra come usare la divisione per testare la lunghezza di un intero invece di convertirlo in una stringa.

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) 

La conversione in una stringa è lenta e non è quasi mai la cosa giusta da fare. Ecco i risultati timeit:

$ 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

Molti dei problemi Project Euler dovrà gestire grandi numeri. PHP renderà i tuoi grandi numeri come 2.579234678963E+12 che è la rappresentazione esponenziale del numero ... È ovviamente difficile lavorare con. Quindi, per la maggior parte dei problemi, è meglio andare con BCMath Functions. Questo manterrà il tuo numero così com'è, anche se è un numero gigante.

Si noti che l'utilizzo di echo bcmul(500,500); non sarà mai veloce come echo 500*500. E, i valori di ritorno della funzione BCMath sono sempre stringhe.

Per risolvere il problema, sostituire tutte le operazioni aritmetiche con la funzione BCMath corrispondente.

Answer 5

Il problema è che si sta lavorando con grandi numeri. È necessario utilizzare le funzioni matematiche BC (php.net/bc). Quindi il tuo codice può essere:

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

Ho provato e ci vogliono circa 0,095 s.

Answer 6

Ho ottimizzato un po 'il codice Python. Usare len (str()) per controllare il numero di cifre è molto lento. Sostituito da math.log10 eseguire il programma molto più veloce

Il primo termine della sequenza di Fibonacci per contenere 1000 digit è: 4782 calcolato in 0,008,573 mila secondo

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)