Perché questa funzione di espressione del generatore è più lenta della versione del loop?

Question

Ho operato secondo la teoria che le espressioni del generatore tendono ad essere più efficienti dei normali cicli. Ma poi mi sono imbattuto nel seguente esempio: scrivere una funzione che ha dato un numero, N, e alcuni fattori, ps, restituisce la somma di tutti i numeri sotto N che sono un multiplo di almeno un fattore.

Ecco una versione ad anello e una più breve versione generatore di espressione:

def loops(N, ps): 
    total_sum = 0 
    for i in xrange(N): 
     for p in ps: 
      if i%p == 0: 
       total_sum += i 
       break 
    return total_sum 

def genexp(N, ps): 
    return sum(i for i in xrange(N) 
       if any(i%p == 0 for p in ps)) 

mi aspetto i due per eseguire o meno uguali, con forse la versione di comprensione un po 'più veloce, ma quello che non si aspettava era questo:

for func in ('loops', 'genexp'): 
    print func, timeit.timeit('%s(100000, [3,5,7])' % func, 
           number=100, 
           setup='from __main__ import %s' % func) 


loops 2.82878184319 
genexp 10.1663100719 

4x più lento non è nemmeno vicino! Perché? Che cosa sto fraintendendo?

Answer 1

Prima di tutto: le espressioni del generatore sono memoria efficienti, non necessariamente efficienti in termini di velocità.

tuo compatta versione genexp() è più lento per due motivi:

• espressioni Generator sono realizzati tramite un nuovo ambito (come una nuova funzione). Stai producendo N nuovi ambiti per ciascun test any(). Creare un nuovo ambito e strapparlo di nuovo è relativamente costoso, certamente quando viene fatto in un ciclo e quindi confrontato con il codice che non lo fa.

• I nomi sum() e any() sono ulteriori elementi globali da cercare. Nel caso di any(), si tratta di ulteriori N ricerche globali per test. I globals devono essere cercati in un dizionario, contro i locali che vengono cercati per indice in un array C (che è molto veloce).

Quest'ultimo è solo un piccolo componente, la maggior parte del costo si trova nella creazione e distruzione di frame (ambiti); se si crea una versione in cui _any e _sum sono i locali alla funzione che si ottiene, ma un piccolo miglioramento in termini di prestazioni:

>>> def genexp_locals(N, ps, _any=any, _sum=sum): 
...  return _sum(i for i in xrange(N) 
...    if _any(i%p == 0 for p in ps)) 
... 
>>> for func in ('loops', 'genexp', 'genexp_locals'): 
...  print func, timeit.timeit('%s(100000, [3,5,7])' % func, 
...        number=100, 
...        setup='from __main__ import %s' % func) 
... 
loops 2.00835800171 
genexp 6.45241594315 
genexp_locals 6.23843789101 

non ho creato un locale xrange per mantenere questo aspetto lo stesso. Dal punto di vista tecnico, il nome _any viene considerato come una chiusura, non un locale, dall'oggetto codice di espressione del generatore, che non è lento come le ricerche globali, ma non altrettanto veloce quanto una ricerca locale.