Генератор последовательности фибоначчи

      Комментарии к записи Генератор последовательности фибоначчи отключены

def fib(max):
a, b = 0, 1 ?
while amax:
yield a ?
a, b = b, a + b ?

  1. Последовательность Фибоначчи — это последовательность чисел, в которой каждое число является суммой двух предыдущих. Она начинается с 0 и 1, сначала постепенно возрастает, потом растет все быстрее и быстрее. Чтобы начать последовательность, вам необходимо две переменные: а начинает с 0, а b — с 1.
  2. a является начальный значением последовательности, поэтому её следует вернуть.
  3. b является следующим числом последовательности, так что присвойте ее a, но так же посчитайте следующее значение (a + b) и присвойте его b для последующего использования. Заметьте, что это происходит одновременно. Если a равно 3, а b равно 5, то a, b = b, a + b установит a в 5 (предыдущее значение b) а b в 8 (сумма предыдущих значений a и b).

Так что теперь у вас есть функция выдает последовательные числа Фибоначчи. Конечно, вы могли бы сделать это с помощью рекурсии, но данная реализация проще читается. Помимо этого, она лучше работает с циклами for.

-yield приостанавливает функцию, next() снова запускает ее в том же состоянии

from fibonacci import fib
for n in fib(1000): ?
… print(n, end=’ ‘) ?
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
list(fib(1000)) ?
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]

  1. Вы можете использовать генератор типа fib() непосредственно в for цикле. Цикл for автоматически вызоывает функцию next() чтобы получить значения из генератора fib() и присвоить их переменной for цикла n.
  2. Каждый раз проходя for цикл, n принимает новое значение от yield в функции fib(), и все что вам нужно сделать — напечатать его. Как только fib() выходит за пределы чисел (a становится больше, чем max, которое в данном случае равно 1000), так сразу цикл for заканчивает работу.
  3. Это полезная техника: отдайте генератор функции list(), и она пройдет в цикле весь генератор (точно так же, как и цикл for в предыдущем примере) и вернет список всех значений.

A Plural Rule Generator

Давайте вернемся к plural5.py и посмотрим как работает эта версия функции plural().

def rules(rules_filename):
with open(rules_filename, encoding=’utf-8′) as pattern_file:
for line in pattern_file:
pattern, search, replace = line.split(None, 3) ?
yield build_match_and_apply_functions(pattern, search, replace) ?

def plural(noun, rules_filename=’plural5-rules.txt’):
for matches_rule, apply_rule in rules(rules_filename): ?
if matches_rule(noun):
return apply_rule(noun)
raise ValueError(‘no matching rule for {0}’.format(noun))

  1. Никакой магии. Помните, что строки файла правил содержат по три значения, разделенных пустым пространством, так что вы используете line.split(None, 3) чтобы получить три «колонки» и присвоить их трем локальным переменным.
  2. А затем вы вызываете yield. Что вы возвращаете? Две функции, созданные динамически вашим старым помощником, build_match_and_apply_functions(), который такой же как и в предыдущих примерах. Другими словами, rules() — это генератор, который отдаёт правила совпадения и изменения по требованию.
  3. Поскольку rules() — это генератор, вы можете использовать его напрямую в for цикле. При первом прохождении for цикла, вы вызовете функцию rules(), которая откроет файл шаблонов, прочитает первую строку, динамически построит функцию условия и модификации из шаблона в этой строке, и вернет динамически созданные функции. При прохождении через loop цикл второй раз, вы продолжите ровно с того места, в котором покинули rules() (это было внутри for line in pattern_file цикла). Первое, что он сделает — прочитает следующую строку файла (который до сих пор открыт), динамически создаст другие функции условия и модификации на основании шаблонов этой строки файла, и отдаст эти две функции.

Что вы приобрели по сравнению с вариантом 4? Меньшее время запуска. В варианте 4 когда вы импортировали модуль plural4, он читал весь файл шаблонов и строил список всех возможных правил ещё до того, как вы вообще подумали о вызове функции plural(). С генераторами вы можете выполнять все действия лениво: вы читаете первое правило и создаете функции и пробуете их, и если это срабатывает вы никогда не читаете остальной файл и не создаете другие функции.

В чем вы теряете? В производительности! Каждый раз когда вы вызываете функцию plural(), генератор rules() начинает всё с начала — что означает открытие заново файла шаблонов и чтение с самого начала построчно.

Что если бы вы могли взять лучшее из двух миров: минимальные расходы на запуск (не исполнять никакого кода во время import) и максимальная производительность (не создавать одни и те же функции снова и снова). И да, вы по-прежнему хотите хранить правила в отдельном файле (потому что код — это код, а данные — это данные), настолько долго, пока вам вдруг не потребуется читать одну и ту же строку дважды.

Чтобы сделать это, вам необходимо будет построить свой собственный итератор. Но перед тем как вы сделаете это, вам необходимо изучить классы в Python.

Статьи к прочтению:

Генератор псевдослучайных чисел


Похожие статьи: