2015-06-22 6 views
10

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?Perché in questo caso si sta utilizzando una funzione di generatore due volte più veloce?

+1

È importante che si tratti di una funzione di generatore, oppure si tratta solo di un altro caso in cui [il codice Python è più veloce quando lo si inserisce in una funzione] (http://stackoverflow.com/questions/11241523/why-does-python-code run-veloce-in-a-funzione)? – BrenBarn

+8

* La prima implementazione richiede circa 4 secondi mentre la seconda impiega circa 8,2 secondi *, quindi il titolo del tuo post è corretto o l'ordine dei blocchi di codice è corretto? –

+0

L'implementazione con il generatore è più veloce e richiede circa 4 secondi –

risposta

2

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 ..

+0

Il calcolo si verifica due volte solo in un caso e non fa molta differenza per le prestazioni. –

+0

Vero, non mi ero reso conto che c'era una pausa lì. E non ho dato abbastanza un'occhiata ai fattori. Colpa mia. – Binnut

3

È 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 
+0

Non penso che la funzione del generatore sia ciò che conta davvero – LittleQ

8

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.

+1

Temporizzata, la rimozione del cast dal generatore rende le due implementazioni eseguite in un tempo quasi identico. – samgak

+0

@ 6502 - Sarebbe fantastico se potessi spiegare perché le operazioni su float sono più costose da operazioni su int. – matino

+0

@SaratAdusumilli è molto probabilmente l'operazione modulo che si verifica all'interno del ciclo e non lo sqrt che occupa la maggior parte del tempo supplementare nel caso di float – samgak

10

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:

enter image description here 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 

enter image description here

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

+0

Perché l'operazione modulo è più costosa su float rispetto a int? –

+0

@SaratAdusumilli, Ho aggiornato la risposta affermando perché l'operazione modulo su float è più costosa, dai un'occhiata :) –

+0

Grazie per la tua risposta. –