Часто возникает ситуации, когда нужно выполнить некоторое действие с последовательностью объектов той или иной природы. С самой простой из них мы уже давно знакомы: перебор целых чисел в арифметической прогрессии.
for n in range(start, stop, step):
do_something(n)
Рассмотрим более сложный пример, перебор чисел Фибоначчи. Конечно же можно писать так:
def fib(n):
fib1, fib2 = 0, 1
for i in range(n):
fib1, fib2 = fib2, fib1 + fib2
return fib1
for i in range(n):
do_something(fib(n))
Но это не слишком-то эффективно, мы будем считать числа Фибоначчи каждый раз с самого начала,
хотя следующее число может быть элементарно получено из двух предыдущих.
ОК, можно сделать и так:
fib1, fib2 = 0, 1
for i in range(n):
do_something(fib1)
fib1, fib2 = fib2, fib1 + fib2
С числами Фибоначчи получилось даже не так страшно, но если на вычисление очередного объекта требуется десятки строчек кода,
то наше do_something(...) утонет в обвязке.
Ну ладно, тогда есть ещё одно решение: сделать список чисел Фибоначчи:
def fibonacci(n):
fib_list = []
fib1, fib2 = 0, 1
for i in range(n):
fib1, fib2 = fib2, fib1 + fib2
fib_list.append(fib1)
return fib_list
for fib in fibonacci(n):
do_something(fib)
Уже почти божественно.
Но предположим, что число n равно 100000.
Тогда мы зачем-то будем хранить 100000 чисел Фибоначчи, хотя в любой момент времени нам нужно не более двух
(одним пользуемся, второе нужно для вычисление следующего числа).
Кроме того, может оказаться, что на шаге 179 нужно прерваться, и 99821 чисел были вычислены совершенно зря.
fibonacci(n) вычисляла очередное число Фибоначчи только в тот момент, когда оно действительно понадобится, и при этом запоминало своё состояние — два текущих числа Фибоначчи — для быстрого вычисления очередного числа.
Такая стратегия называется ленивыми вычислениями.
Её можно было бы реализовать, используя глобальные переменные.
Однако в языке Python специально для таких задач существуют генераторы (generators) (не путать с генераторами списков, словарей и множеств (list, dictionary, set comprehension)).
Пример генератора чисел Фибоначчи и нескольких способов им воспользоваться:
def fibonacci(n):
fib1, fib2 = 0, 1
for i in range(n):
fib1, fib2 = fib2, fib1 + fib2
yield fib1
for fib in fibonacci(20):
print(fib, end=' ')
print()
print('Сумма первых 100 чисел Фибоначчи равна', sum(fibonacci(100)))
print(list(fibonacci(16)))
print([x*x for x in fibonacci(14)])
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
Сумма первых 100 чисел Фибоначчи равна 927372692193078999175
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
[1, 1, 4, 9, 25, 64, 169, 441, 1156, 3025, 7921, 20736, 54289, 142129]
Итак, для того, чтобы сделать из обычной функции генератор, нужно вместо return использовать yield.
В результате получится не функция, которую можно вызвать и получить результат её работы,
а итерируемый объект, из которого можно последовательно выдёргивать результаты его работы до тех пор,
пока не будет исполнена последняя строчка кода генератора, либо не будет выполнен выход командой return.
При этом после выдачи результата командой yield состояние генератора, все его внутренние переменные сохраняются.
При следующей попытке выдернуть элемент из генератора работа начнётся со строчки, следующей за yield.
Чтобы изучить работу генератора чисел Фибоначчи, попробуйте запустить следующий код:
def fibonacci(n):
print(' Стартуем генератор')
fib1, fib2 = 0, 1
print(' Всё готово, нам дали n =', n)
for i in range(n):
if i == 0:
print(' Итак, это - первая итерация')
fib1, fib2 = fib2, fib1 + fib2
print(' Сейчас про-yield-им число', fib1, 'при i =', i)
yield fib1
print(' Мы снова в генераторе! По-прежнему i =', i, ' fib1 =', fib1, 'fib2 =', fib2)
print(" Всё, последняя строчка генератора...")
print('Мы снаружи. Сейчас будем итерировать по генератору')
for f in fibonacci(3):
print('Снаружи получили значение f =', f)
print('Снаружи закончили итерацию')
"""
Мы снаружи. Сейчас будем итерировать по генератору
Стартуем генератор
Всё готово, нам дали n = 3
Итак, это - первая итерация
Сейчас про-yield-им число 1 при i = 0
Снаружи получили значение f = 1
Мы снова в генераторе! По-прежнему i = 0 fib1 = 1 fib2 = 1
Сейчас про-yield-им число 1 при i = 1
Снаружи получили значение f = 1
Мы снова в генераторе! По-прежнему i = 1 fib1 = 1 fib2 = 2
Сейчас про-yield-им число 2 при i = 2
Снаружи получили значение f = 2
Мы снова в генераторе! По-прежнему i = 2 fib1 = 2 fib2 = 3
Всё, последняя строчка генератора...
Снаружи закончили итерацию
"""
Итак, достаточно внутри функции хоть раз воспользоваться командой yield, чтобы сделать из неё генератор.
После этого её нельзя вызвать так, как обычно (попробуйте print(fibonacci(5))),
но можно использовать в for, list, sorted, map, zip, enumerate и так далее.
* — распаковка.
Его можно применять только применительно к параметрам вызываемой функции.
При этом происходит следующее: из объекта, к которому применяется распаковка, извлекаются отдельные элементы и передаются в качестве отдельных параметров:
Рассмотрим пример:
def func1():
return 2, 5, 7
def func2(x, y, z):
print(x + y + z)
func2(*func1())
Здесь функция func1() возвращает кортеж из трёх чисел,
а функция func2() принимает на вход три элемента.
Результат работы первой функции можно передать сразу во вторую, если распаковать результат её работы.
Другой пример использования распаковки --- это передача одного и того же набора параметров в разные функции:
def func1(x, y):
print(x + y)
def func2(x, y):
print((x ** 2 + y ** 2) ** 0.5)
pars = (3, 7)
func1(*pars)
func2(*pars)
Очень удобно использовать распаковку — внутри функции print:
def fibonacci(n):
fib1, fib2 = 0, 1
for i in range(n):
fib1, fib2 = fib2, fib1 + fib2
yield fib1
print(*fibonacci(10))
Таким образом, можно быстро выводить содержимое списков, результаты работы генераторов или функций, возвращающих кортежи или списки.
Также при помощи распаковки можно передавать числовые параметры из стандартного ввода в функцию в одну строчку:
def max(a, b, c):
return max(max(a, b), c)
print(max(*map(int, input().split())))
Напишите генератор square_fibonacci(n), генерирующий последовательность квадратов чисел Фибоначчи.
Выведите результат при помощи функции print и распаковки.
Напишите генератор factorials(n), генерирующий последовательность факториалов натуральных чисел.
Напишите генератор triangular_numbers(n), генерирующий последовательность треугольных чисел.
Напишите генератор mod_powers(a, n), генерирующий последовательность степеней числа по модулю
до тех пор, пока очередная степень не будет равна 1.
Гарантируется, что числа и взаимно просты.
Напишите генератор binomial_coefficients(n), генерирующий последовательность биномиальных коэффициентов
.
Запрещается использовать факториалы.
Еще 4000 лет назад вавилонские ученые составляли наряду с таблицами умножения и таблицами обратных величин таблицы квадратов чисел и квадратных корней из чисел. При этом они умели находить приблизительное значение квадратного корня из любого целого числа. Для извлечения корня из числа они использовали последовательность , , предел которой как раз равен .
Напишите генератор babylonian_sequence(a), генерирующий данную последовательность до тех пор,
пока отличие от не станет меньше .
n из букв a, b:
def abc_gen(n):
if n == 0:
yield ''
else:
for shorter in abc_gen(n - 1):
yield 'a' + shorter
yield 'b' + shorter
print(*abc_gen(4))
>>>
aaaa baaa abaa bbaa aaba baba abba bbba aaab baab abab bbab aabb babb abbb bbbb
Здесь точно также нужно следить за тем, чтобы рекурсия не стала бесконечно глубокой.
По данному натуральному n⩽10 выведите все двоичные последовательности длины n в лексикографическом порядке.
По данным натуральным n и k (2⩽k⩽10) выведите все последовательности длины n, составленные из символов 0..k-1. в лексикографическом порядке.