Quello che sto capendo è che non hai davvero bisogno di rendere il codice più veloce, vuoi solo sapere perché è più lento. Per rispondere, diamo un'occhiata allo smontaggio. Ai fini di questa discussione, ho intenzione di avvolgere ogni metodo in una chiamata di funzione, il caricamento di u
e v
e il comando di ritorno può essere ignorato in ogni disassemblaggio.
def test1(u, v):
return (u[0]-v[0])**2 + (u[1]-v[1])**2 + (u[3]-v[3])**2
dis.dis(test1)
0 LOAD_FAST 0 (u)
3 LOAD_CONST 1 (0)
6 BINARY_SUBSCR
7 LOAD_FAST 1 (v)
10 LOAD_CONST 1 (0)
13 BINARY_SUBSCR
14 BINARY_SUBTRACT
15 LOAD_CONST 2 (2)
18 BINARY_POWER
19 LOAD_FAST 0 (u)
22 LOAD_CONST 3 (1)
25 BINARY_SUBSCR
26 LOAD_FAST 1 (v)
29 LOAD_CONST 3 (1)
32 BINARY_SUBSCR
33 BINARY_SUBTRACT
34 LOAD_CONST 2 (2)
37 BINARY_POWER
38 BINARY_ADD
39 LOAD_FAST 0 (u)
42 LOAD_CONST 4 (3)
45 BINARY_SUBSCR
46 LOAD_FAST 1 (v)
49 LOAD_CONST 4 (3)
52 BINARY_SUBSCR
53 BINARY_SUBTRACT
54 LOAD_CONST 2 (2)
57 BINARY_POWER
58 BINARY_ADD
59 RETURN_VALUE
Ho tagliato il primo esempio a una lunghezza di 3 perché avrebbe ripetuto lo stesso schema più e più volte. È possibile vedere rapidamente che non vi è alcuna funzione chiamata overhead e praticamente l'interprete sta facendo il minimo lavoro possibile su questi operandi per raggiungere il risultato.
def test2(u, v):
sum((a-b)**2 for a, b in izip(u, v))
dis.dis(test2)
0 LOAD_GLOBAL 0 (sum)
3 LOAD_CONST 1 (<code object <genexpr> at 02C6F458, file "<pyshell#10>", line 2>)
6 MAKE_FUNCTION 0
9 LOAD_GLOBAL 1 (izip)
12 LOAD_FAST 0 (u)
15 LOAD_FAST 1 (v)
18 CALL_FUNCTION 2
21 GET_ITER
22 CALL_FUNCTION 1
25 CALL_FUNCTION 1
28 RETURN_VALUE
Quello che vediamo qui è che creiamo una funzione di fuori del generatore di espressione, di carico 2 globali (somma e izip, le ricerche globali sono più lento di ricerche locali, non possiamo evitare di farli una volta, ma se Saranno chiamati in un ciclo chiuso, molte persone li assegnano a un locale, come ad esempio _izip
o _sum
, e quindi subiscono 4 costose operazioni bytecode di fila, chiamando izip, ottenendo l'iteratore dal generatore, chiamando la funzione creato dal generatore e quindi chiamando la funzione somma (che consumerà l'iteratore e aggiungerà ogni elemento prima di tornare).
def test3(u, v):
sum = 0
for i in xrange(len(u)):
sum += (u[i]-v[i])**2
dis.dis(test3)
0 LOAD_CONST 1 (0)
3 STORE_FAST 2 (sum)
6 SETUP_LOOP 52 (to 61)
9 LOAD_GLOBAL 0 (xrange)
12 LOAD_GLOBAL 1 (len)
15 LOAD_FAST 0 (u)
18 CALL_FUNCTION 1
21 CALL_FUNCTION 1
24 GET_ITER
25 FOR_ITER 32 (to 60)
28 STORE_FAST 3 (i)
31 LOAD_FAST 2 (sum)
34 LOAD_FAST 0 (u)
37 LOAD_FAST 3 (i)
40 BINARY_SUBSCR
41 LOAD_FAST 1 (v)
44 LOAD_FAST 3 (i)
47 BINARY_SUBSCR
48 BINARY_SUBTRACT
49 LOAD_CONST 2 (2)
52 BINARY_POWER
53 INPLACE_ADD
54 STORE_FAST 2 (sum)
57 JUMP_ABSOLUTE 25
60 POP_BLOCK
61 LOAD_CONST 0 (None)
64 RETURN_VALUE
Ciò che vediamo qui è una versione più semplice di quello che sta accadendo in test2
. Nessuna espressione del generatore o chiamata alla somma, ma abbiamo sostituito quella funzione di overhead con una chiamata di funzione non necessaria eseguendo xrange(len(u))
invece della soluzione più veloce suggerita da @Lucas Malor.
def test4(u, v):
mysum = 0
for a, b in izip(u, v) :
mysum += (a-b)**2
return mysum
dis.dis(test4)
0 LOAD_CONST 1 (0)
3 STORE_FAST 2 (mysum)
6 SETUP_LOOP 47 (to 56)
9 LOAD_GLOBAL 0 (izip)
12 LOAD_FAST 0 (u)
15 LOAD_FAST 1 (v)
18 CALL_FUNCTION 2
21 GET_ITER
22 FOR_ITER 30 (to 55)
25 UNPACK_SEQUENCE 2
28 STORE_FAST 3 (a)
31 STORE_FAST 4 (b)
34 LOAD_FAST 2 (mysum)
37 LOAD_FAST 3 (a)
40 LOAD_FAST 4 (b)
43 BINARY_SUBTRACT
44 LOAD_CONST 2 (2)
47 BINARY_POWER
48 INPLACE_ADD
49 STORE_FAST 2 (mysum)
52 JUMP_ABSOLUTE 22
55 POP_BLOCK
56 LOAD_FAST 2 (mysum)
59 RETURN_VALUE
Quanto sopra rappresenta il contributo di @Lucas Malor ed è più veloce in alcuni modi. Sostituisce le operazioni in pedice con la decompressione, riducendo al tempo stesso il numero di chiamate a 1. Questo è, in molti casi, il più velocemente possibile con i vincoli che ci hai fornito.
Si noti che vale solo eval
utilizzando una stringa generata in fase di esecuzione simile alla funzione in test1 se si desidera chiamare la funzione abbastanza volte per meritare il sovraccarico. Si noti inoltre che quando la lunghezza di uev diventa sempre più grande (che è in genere la valutazione degli algoritmi di questo tipo) la funzione chiamata overhead delle altre soluzioni diventa sempre più piccola e quindi, nella maggior parte dei casi, la soluzione più leggibile è enormemente superiore . Allo stesso tempo, anche se è più lento nei casi di piccole dimensioni, se la lunghezza delle sequenze, uev, può essere molto lunga, raccomando un'espressione di generatore anziché una comprensione di lista. I risparmi di memoria causeranno un'esecuzione molto più veloce nella maggior parte dei casi (e più veloce gc). Complessivamente, la mia raccomandazione è che la piccola accelerazione in caso di sequenze brevi non vale l'aumento delle dimensioni del codice e del comportamento incoerente con altre implementazioni di Python che si stanno osservando eseguendo micro-ottimizzazioni. La soluzione "migliore" è quasi certamente test2
.
Sei appena arrivato a [timeit] (http://docs.python.org/2/library/timeit.html). Nella soluzione n. 2 stai creando un elenco che non ti serve. Prova 'sum ((a-b) ** 2 per a, b in izip (u, v))'. Nella soluzione n. 3 stai indicizzando troppo spesso. Prova 'per a, b in izip (u, v): sum + = (a-b) ** 2' –
Ha commentato che è più veloce di un elenco di un generatore. Sembra che lui sappia cosa sta facendo. – FogleBird
@Rob In realtà ho fatto molto tempo e non sono riuscito a trovare una soluzione che si avvicini alla variante hardcoded. Ecco perché ho postato la mia domanda qui. Come ho già notato, il # 2 è più veloce con la lista che senza (dato che i generatori danno un po 'di overhead, e gli stessi vettori non sono enormi). –