Perché la sottrazione è più veloce dell'aggiunta in Python?

Question

stavo ottimizzando po 'di codice Python, e ho provato il seguente esperimento:

import time 

start = time.clock() 
x = 0 
for i in range(10000000): 
    x += 1 
end = time.clock() 

print '+=',end-start 

start = time.clock() 
x = 0 
for i in range(10000000): 
    x -= -1 
end = time.clock() 

print '-=',end-start 

Il secondo ciclo è affidabile veloce, ovunque da un soffio al 10%, a seconda del sistema corro su. Ho provato a variare l'ordine dei loop, il numero di esecuzioni, ecc. E sembra funzionare ancora.

Straniero,

for i in range(10000000, 0, -1): 

(cioè eseguito il loop all'indietro) è più veloce di

for i in range(10000000): 

anche quando il contenuto di loop sono identici.

Cosa dà e c'è una lezione di programmazione più generale qui?

Answer 1

$ python -m timeit -s "x=0" "x+=1" 
10000000 loops, best of 3: 0.151 usec per loop 
$ python -m timeit -s "x=0" "x-=-1" 
10000000 loops, best of 3: 0.154 usec per loop 

Sembra che tu abbia un po 'di measurement bias

Answer 2

Il ciclo in esecuzione indietro è più veloce perché il computer ha un tempo più facile il confronto se un numero è uguale a 0.

Answer 3

Penso che la "programmazione generale lezione "è che è davvero difficile da prevedere, solo guardando il codice sorgente, quale sequenza di dichiarazioni sarà la più veloce. I programmatori di tutti i livelli vengono spesso catturati da questa sorta di ottimizzazione "intuitiva". Ciò che pensi di sapere potrebbe non essere necessariamente vero.

Semplicemente non esiste un sostituto per lo che misura la prestazione del programma. Complimenti per averlo fatto; rispondere a perché il richiede indubbiamente di approfondire l'implementazione di Python, in questo caso.

Con linguaggi compilati da byte come Java, Python e .NET, non è nemmeno sufficiente misurare le prestazioni su una sola macchina. Le differenze tra versioni di VM, implementazioni di traduzione di codice nativo, ottimizzazioni specifiche della CPU e così via renderanno questo tipo di domanda sempre più difficile da rispondere.

Answer 4

Con Python 2.5 il problema più grande qui è l'utilizzo dell'intervallo, che assegnerà una lista così grande da iterare su di esso. Quando si usa xrange, qualunque sia il secondo è leggermente più veloce per me. (Non sono sicuro che l'intervallo sia diventato un generatore in Python 3.)

Answer 5

È sempre una buona idea porre una domanda per dire quale piattaforma e quale versione di Python si sta utilizzando. A volte non importa. Questo non è uno di quei momenti:

1. time.clock() è appropriato solo su Windows. Getta via il tuo codice di misurazione e usa -m timeit come dimostrato nella risposta di pixelbeat.

2. Python 2.X's range() crea un elenco. Se si utilizza Python 2.x, sostituire range con xrange e vedere cosa succede.

3. Python 3.X's è Python2.X long.

Answer 6

Posso riprodurlo sul mio Q6600 (Python 2.6.2); aumentando l'intervallo di 100000000:

('+=', 11.370000000000001) 
('-=', 10.769999999999998) 

Prima, alcune osservazioni:

• Questo è 5% per un'operazione banale. Questo è significativo.
• La velocità degli opcode di addizione e sottrazione nativi è irrilevante. È nel rumore, completamente sminuito dalla valutazione bytecode. Si tratta di una o due istruzioni native circa migliaia.
• Il bytecode genera esattamente lo stesso numero di istruzioni; l'unica differenza è INPLACE_ADD rispetto a INPLACE_SUBTRACT e +1 vs -1.

Guardando la sorgente Python, posso fare un'ipotesi. Questo viene gestito in ceval.c, in PyEval_EvalFrameEx. INPLACE_ADD ha un ulteriore blocco di codice significativo, per gestire la concatenazione di stringhe. Quel blocco non esiste in INPLACE_SUBTRACT, poiché non è possibile sottrarre le stringhe. Ciò significa che INPLACE_ADD contiene più codice nativo. A seconda (molto!) Del modo in cui il codice viene generato dal compilatore, questo codice aggiuntivo potrebbe essere in linea con il resto del codice INPLACE_ADD, il che significa che le aggiunte possono colpire la cache delle istruzioni più di sottrazione. Questo potrebbe causare causando ulteriori riscontri di cache L2, che potrebbero causare una significativa differenza di prestazioni.

Questo dipende in gran parte dal sistema in uso (diversi processori hanno diverse quantità di cache e architetture di cache), il compilatore in uso, inclusa la particolare versione e le opzioni di compilazione (diversi compilatori decideranno in modo diverso quali bit di codice sono sul percorso critico, che determina in che modo il codice assembly viene raggruppato insieme) e così via.

Inoltre, la differenza è invertita in Python 3.0.1 (+: 15.66, -: 16.71); senza dubbio questa funzione critica è cambiata molto.

Answer 7

L'esperimento è difettoso. Il modo in cui questo esperimento dovrebbe essere progettato è quello di scrivere 2 programmi diversi: 1 per aggiunta, 1 per sottrazione. Dovrebbero essere esattamente uguali e funzionare nelle stesse condizioni con i dati da mettere in archivio. Quindi è necessario calcolare la media delle esecuzioni (almeno diverse migliaia), ma è necessario un esperto di statistica per comunicare un numero appropriato.

Se si desidera analizzare diversi metodi di aggiunta, sottrazione e loop, di nuovo ognuno di questi dovrebbe essere un programma separato.

errore sperimentale potrebbe derivare dal calore del processore e altre attività in corso sulla CPU, quindi mi piacerebbe eseguire i funzionamenti in una varietà di modelli ...

Answer 8

"Il secondo ciclo è affidabile veloce .. . "

Questa è la tua spiegazione proprio lì. Re-ordine lo script in modo che il test di sottrazione è a tempo prima, poi l'aggiunta, e improvvisamente aggiunta diventa di nuovo l'operazione più veloce:

-= 3.05 
+= 2.84 

Ovviamente succede qualcosa alla seconda metà dello script che rende più veloce.La mia ipotesi è che la prima chiamata a range() è più lento a causa di pitone ha bisogno di allocare memoria sufficiente per una lunga lista tale, ma è in grado di riutilizzare quella memoria per la seconda chiamata a range():

import time 
start = time.clock() 
x = range(10000000) 
end = time.clock() 
del x 
print 'first range()',end-start 
start = time.clock() 
x = range(10000000) 
end = time.clock() 
print 'second range()',end-start 

un paio di basi di questo script mostrano che il tempo in più necessario per i primi range() conti per quasi tutta la differenza di tempo tra '+ =' e '- =' visto sopra:

first range() 0.4 
second range() 0.23 

Answer 9

che sarebbe notevole, così Ho accuratamente valutato il tuo codice e ho anche impostato l'espirimento come volevo d lo trovi più corretto (tutte le dichiarazioni e le chiamate di funzione all'esterno del ciclo). Entrambe le versioni ho eseguito cinque volte.

• esecuzione il codice validato i vostri reclami: - = prende costantemente meno tempo; 3,6% in media
• L'esecuzione del mio codice, tuttavia, contraddice il risultato dell'esperimento: + = richiede in media (non sempre) lo 0,5% di tempo in meno.

per mostrare tutti i risultati che ho messo trame on-line:

• tua valutazione: http://bayimg.com/kadAeaAcN
• La mia valutazione: http://bayimg.com/KadaAaAcN

Quindi, concludo che l'esperimento ha una distorsione, ed è significativo.

Infine Ecco il mio codice:

import time 

addtimes = [0.] * 100 
subtracttimes = [0.] * 100 

range100 = range(100) 
range10000000 = range(10000000) 

j = 0 
i = 0 
x = 0 
start = 0. 


for j in range100: 
start = time.clock() 
x = 0 
for i in range10000000: 
    x += 1 
addtimes[j] = time.clock() - start 

for j in range100: 
start = time.clock() 
x = 0 
for i in range10000000: 
    x -= -1 
subtracttimes[j] = time.clock() - start 

print '+=', sum(addtimes) 
print '-=', sum(subtracttimes) 

Answer 10

C'è una lezione di programmazione più generale qui?

La lezione di programmazione più generale qui è che l'intuizione è una guida scadente quando si predice prestazioni di esecuzione del codice del computer.

Si può ragionare sulla complessità algoritmica, ipotizzando ottimizzazioni del compilatore, prestazioni della cache di stima e così via. Tuttavia, dal momento che queste cose possono interagire in modi non banali, l'unico modo per essere sicuri della velocità di un particolare pezzo di codice è di confrontarlo nell'ambiente di destinazione (come avete fatto correttamente).