Почему функция генератора работает в два раза быстрее?

Question

код, который является общим для обеих реализаций:

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. Реализация, которая не использовать функцию генератора:

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

2. Реализация, что делает использование функции генератора :

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 

Вопрос:

Первая реализация занимает около 4 секунд, а вторая занимает примерно 8,2 секунды. Почему существует такая большая разница между временем выполнения двух реализаций?

Answer 1

Единственное отличие, насколько я знаю, это то, что вы делаете расчет i * (i+1) * 0.5 дважды в первом примере. Это не дорогое вычисление, но это может иметь большое значение, поскольку это такая большая часть программы.

Answer 2

Вы можете удалить множители() кода, сделать намного больше.

# 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 

и % timeit, для сравнения с реализацией 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

В явном случае, если вы не принимают int выражения перед вызовом factors и поэтому передаваемое значение будет число с плавающей запятой.

В случае генератора вместо этого вы получаете int(...), вызывая factors, передавая целое число.

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 для обоих:

После изменения factors вызова в temp1() к factors(int(...)), Оказывается, temp1() принимает аналогичное время

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 

Так получается, что в первой реализации вы передаете float к factors() и арифметику с плавающей точкой является сложным, чем целочисленные арифметические

Почему операций с плавающей точкой сложны?

Поскольку способ отображения float внутренне отличается от ints, они представлены в 3 частях как знак, мантисса и экспонента (IEEE 754), тогда как представление целого числа очень простое, и поэтому такие операции, как сложение и вычитание по целым числам , даже умножение и деление выполняются с использованием комбинации операций сложения, вычитания и сдвига внутри. так как их сложение и вычитание просты, поэтому их деление/умножение и, следовательно, операции с плавающей запятой некоторые из них являются чем-то дорогостоящим

Почему модуль с плавающей запятой стоит дорого целого?

Ответ такой же, как указано выше, операция по модулю не что иное, как сочетание примитивных операций, указанных выше, следующим образом:

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

Так как примитивные операции для поплавков являются более дорогими, так что по модулю для поплавков