Perché in questo caso si sta utilizzando una funzione di generatore due volte più veloce?

Question

Il codice che è comune per entrambe le implementazioni:

from math import sqrt 

def factors(x): 
    num = 2 
    sq = int(sqrt(x)) 
    for i in range(2, sq): 
     if (x % i) == 0: 
      num += 2 
    return num + ((1 if sq == sqrt(x) else 2) if x % sq == 0 else 0) 

1. attuazione che non fa uso di un generatore di funzioni:

i = 1 
while True: 
    if factors(i * (i+1) * 0.5) > 500: 
     print(int(i * (i+1) * 0.5)) 
     break 
    i += 1 

2. Attuazione che fa uso di una funzione generatore :

def triangle(): 
    i = 1 
    while True: 
     yield int(0.5 * i * (i + 1)) 
     i += 1 

t = triangle() 

while True: 
    num = t.__next__() 
    if factors(num) > 500: 
     print(num) 
     break 

la domanda:

La prima implementazione richiede circa 4 secondi mentre la seconda richiede circa 8,2 secondi. Perché c'è una grande differenza tra i tempi di esecuzione delle due implementazioni?

Answer 1

L'unica differenza per quanto ne so è che si esegue il calcolo i * (i+1) * 0.5 due volte nel primo esempio. Non è un calcolo costoso, ma potrebbe fare una grande differenza poiché è una porzione così grande del programma ..

Answer 2

È possibile rimuovere i fattori() del codice, rendere molto più grande.

# implementation 1 
i = 1 
while True: 
    if (i * (i + 1) * 0.5) > n: # n=100000 
     # print int(i * (i + 1) * 0.5), 
     break 
    i += 1 

e % timeit, per confrontare con l'implementazione 2:

def triangle(): 
    i = 1 
    while True: 
     yield i * (i + 1) * 0.5 
     i += 1 

t = triangle() 

while True: 
    num = t.next() 
    if num > n: 
     # print num, 
     break 

Answer 3

Nel caso esplicito non stai prendendo il int dell'espressione prima di chiamare factors e quindi il valore passato sarà un numero in virgola mobile.

Nel caso di generatore si sta invece cedendo int(...), chiamando factors passando un numero intero.

Answer 4

temp1():

def temp1(): 
     i = 1 
     while True: 
      if factors(i * (i+1) * 0.5) > 500: 
       print(int(i * (i+1) * 0.5)) 
       break 
      i += 1 

temp2():

def temp2(): 
    def triangle(): 
     i = 1 
     while True: 
      yield int(0.5 * i * (i + 1)) 
      i += 1 

    t = triangle() 

    while True: 
     num = t.next() 
     if factors(num) > 500: 
      print(num) 
      break 

Cprofile per entrambi:

Dopo aver cambiato il factors chiamata in temp1() a factors(int(...)), Risulta che temp1() prende il tempo simile

Modified temp1 to pass int rather than float:

def temp1(): 
    i = 1 
    while True: 
     if factors(int(i * (i+1) * 0.5)) > 500: 
      print(int(i * (i+1) * 0.5)) 
      break 
     i += 1 

Così si scopre che nella vostra prima implementazione si passa float al factors() e aritmetica in virgola mobile è complessa rispetto aritmetiche

operazioni in virgola interi Perché Floating sono complessi ??

Perché il modo galleggianti sono rappresentati internamente è diverso da int, sono rappresentati in 3 parti come segno mantissa e dell'esponente (IEEE 754) che rappresentazione intero è molto semplice e così sono operazioni come addizioni e sottrazioni interi , anche la moltiplicazione e la divisione vengono eseguite utilizzando una combinazione di operazioni di addizione, sottrazione e spostamento internamente. poiché l'aggiunta e la sottrazione di interi sono semplici, così la loro divisione/moltiplicazione e quindi le operazioni in virgola mobile sono un po 'costose. Perché il modulo a virgola mobile è più costoso di Integer?

La risposta è come sopra, un'operazione di modulo non è altro che combinazione di operazioni primitive di cui sopra come segue:

a mod n = a - (n*int(a/n)) 

Poiché operazioni primitive per galleggianti sono più costosi, quindi è modulo per galleggianti