Maintaining State в генераторах Python

Введение

В этой статье продолжается обзор генераторов в Python 3 начатый здесь

Создайте файл generators_demo.py и копируйте туда код из примеров.

Запустить файл можно командой

python3 generators_demo.py

Пример

Рассмотрим код, который будет возвращать из списка определённое количество неповторяющихся элементов

def take(count, iterable): counter = 0 for item in iterable: if counter == count: return counter += 1 yield item def distinct(iterable): seen = set() for item in iterable: if item in seen: continue yield item seen.add(item) # continue - finish current loop iteration and begin the next iteration immediately def run_pipeline(): items = [3, 6, 6, 2, 1, 1] for item in take(3, distinct(items)): print(item) run_pipeline()

distinct() - это генератор, который выдаёт по одному элементу, если этого элемента нет во множестве (в set) seen

take() - это тоже генератор - он просто берет определённое количество элементов

python generators_demo.py

Каждый вызов функции-генератора создаёт новый генератор-объект (generator object)

Чтобы разобраться в работе этого примера можно использовать debugger, например PyCharm

В качестве дополнительной иллюстрации, которая особенно пригодится чуть позже используем обычный print().

Добавим ещё пару элементов в items

def take(count, iterable): counter = 0 for item in iterable: print("take item", item) if counter == count: print("No need to take it, return now") return counter += 1 yield item def distinct(iterable): seen = set() for item in iterable: print("distinct item candidate", item) if item in seen: continue else: print("distinct item", item) yield item seen.add(item) # continue - finish current loop iteration and begin the next iteration immediately def run_pipeline(): items = [3, 6, 6, 2, 1, 1, 5, 5] for item in take(3, distinct(items)): print("run_pipeline item", item) print(item) run_pipeline()

distinct item candidate 3 distinct item 3 take item 3 run_pipeline item 3 3 distinct item candidate 6 distinct item 6 take item 6 run_pipeline item 6 6 distinct item candidate 6 distinct item candidate 2 distinct item 2 take item 2 run_pipeline item 2 2 distinct item candidate 1 distinct item 1 take item 1 No need to take it, return now Process finished with exit code 0

Как видите, сперва работает take(), затем distinct(), затем run_pipeline()

take() когда берёт 1 понимает, что она уже лишняя (нужно всего 3 элемента) и до 5 дело вообще не доходит.

Произведено ровно столько работы, сколько необходимо, это так называемое ленивое вычисление (lazy computing)

Если становится слишком сложно, можно уйти от этой схемы, заставив distinct() выполнить все вычисления прежде чем они попадут в take().

Для этого вызовем disctinct() из list()

def run_pipeline(): items = [3, 6, 6, 2, 1, 1] for item in take(3, list(distinct(items))): print("run_pipeline item", item)

distinct item candidate 3 distinct item 3 distinct item candidate 6 distinct item 6 distinct item candidate 6 distinct item candidate 2 distinct item 2 distinct item candidate 1 distinct item 1 distinct item candidate 1 distinct item candidate 5 distinct item 5 distinct item candidate 5 take item 3 run_pipeline item 3 take item 6 run_pipeline item 6 take item 2 run_pipeline item 2 take item 1 No need to take it, return now Process finished with exit code 0

В этом случае проделана лишняя работы - distinct() прошёлся по всем элементам и в результате получился список [3, 6, 2, 1, 5] из которого take() взял нужные три элемента.

В данном примере разница невелика, но если бы в items было не 8 а миллион элементов, мы бы её почувстовали

Производительность

Сравним скорость выполнения этих скриптов. Сделаем это с помощью декоратора prof_timer , который нужно поместить выше вызова run_pipeline()

def prof_timer(orig_func): import time def wrapper(*args, **kwargs): t1 = time.time() result = orig_func(*args, **kwargs) t2 = time.time() - t1 print(f'{orig_func.__name__} ran in: {t2} sec') return result return wrapper

@prof_timer def run_pipeline(): items = [3, 6, 6, 2, 1, 1, 5, 5]

Lazy:

run_pipeline ran in: 6.0249837585029e-05 sec

С list():

run_pipeline ran in: 6.4849853515625e-05 sec

Разница незаметна. Добавим элементов в items

@prof_timer def run_pipeline(): items = [ 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5, 3, 6, 6, 2, 1, 1, 5, 5,]

Lazy:

run_pipeline ran in: 0.00011014938354492188 sec

С list():

run_pipeline ran in: 0.0005578994750976562 sec

Lazy быстрее в 5 раз

Генератор чисел Фибоначчи

Генератор, который выдаёт числа Фибоначчи.

Для примера запустим вариант, который покажет первые 20 чисел Фибоначчи.

Чтобы запустить бесконечную генерацию - раскомментируйте нижний блок кода

def fib_gen(): yield 0 a = 1 b = 1 while True: yield b a, b = b, a+b g = fib_gen() for i in range(20): print(next(g)) # Uncomment to generate infinit number # of Fibonacci numbers # import time # time.sleep(3) # for f in fib_gen(): # print("\nf: ",f)

python fibon.py

0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

Generator Expressions

Синтаксис

(expr(item) for item in iterable)

Чтобы передать генератор в функцию как аргумент дополнительные скобки не обязательны

func(expr(item) for item in iterable)

Рассмотрим пример

million_squares = (x*x for x in range(1, 1000001)) print(million_squares) print(list(million_squares)[-10:]) print(list(million_squares)[-10:]) # [] # To recreate a generator from a # generator expression, you must # execute the expression again

python gen_expr.py

<generator object <genexpr> at 0x7fdc7ada4580> [999982000081, 999984000064, 999986000049, 999988000036, 999990000025, 999992000016, 999994000009, 999996000004, 999998000001, 1000000000000] []

Второй вызов list() ничего не дал, так как генератор уже отработал до конца.

Вычислим сумму чисел передав генератор в sum()

print(sum(x*x for x in range(1, 1000001)))

333333833333500000

Вычислим сумму всех простых чисел меньших 1000

def is_prime(x): from math import sqrt if x < 2: return False for i in range(2, int(sqrt(x)) + 1): if x % i == 0: return False return True print(sum(x for x in range(1001) if is_prime(x)))

76127