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

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

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 секунды. Почему существует такая большая разница между временем выполнения двух реализаций?

Ответы

Ответ 1

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

enter image description here После изменения вызова 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

enter image description here

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

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

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

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

Ответ такой же, как и выше. Операция modulo - это не что иное, как комбинация примитивных операций, упомянутых выше:

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

Так как примитивные операции для поплавков более дороги, то есть modulo для floats

Ответ 2

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

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

Ответ 3

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

# 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

Ответ 4

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