Файл: Учебник по информатике. Программирование на Python. Основы 1 Программирование на Python. Основы.pdf

Открытый учебник по информатике. Программирование на Python. Основы
69 алгоритмов строка с добавлением нового элемента всегда будет добавлять первое невычисленное значение, перед тем, как добавить следующее.
Посмотрим, как изменится порядок вычисления. В скобках указан порядок возвращения значений рекурсивной функцией. fib(5) → # выход из рекурсии для 5 (5)
(fib(4) → # выход из рекурсии для 4 (3)
(fib(3) → # выход из рекурсии для 3 (1)
(fib(2) → fib(1)) # уже посчитано (0)
) → fib(2)# уже посчитано (2)
) →
(fib(3) # это уже посчитано (4)
Можно придумать и другие способы хранения результатов работы рекурсивной функции. Однако в языке Python уже есть замечательный декоратор
1
@lru_cache() из библиотеки functools, который может сделать это за нас.
Теперь, если мы перепишем нашу первую реализацию рекурсивной функции в такую, которая не вычисляет значения для одного и того же числа N несколько раз, то получим следующий код. from functools import lru_cache
@lru_cache() def fibonacci(N): if N < 3: return 1 return fibonacci(N-1) + fibonacci(N-2)
Код стал компактным, остался понятным и мы потратили на его оптимизацию крайне мало времени и сил.
При работе с декоратором lru_cache надо помнить, что все значения параметров должны быть строго неизменяемого типа. При попытке вызова функции с, например, списковым значением аргумента, lru_cache вернет ошибку «TypeError: unhashable type: 'list'» или «Ошибка типа: нехешируемый тип 'список'».
Также сохранение полученных результатов – ручное или с помощью
lru_cache – не обходит проблему переполнения стека вызовов. Так как у нас каждому вызову функции fibonacci() будет предшествовать вызов функции
lru_cache(), количество допустимых рекурсивных вызовов fibonacci() будет
1
Декоратор – это функция, являющаяся своего рода «обёрткой» для другой функции. То есть такая функция, которая управляет запуском другой функции. Например, декоратор @lru_cache() перед запуском функции
fibonacci() проверит, был ли уже запуск с таким же параметром и, если значение для такого параметра уже было найдено, сразу вернет результат без повторного запуска функции fibonacci().
Подробнее работу с декораторами рассмотрим в будущих главах.

Открытый учебник по информатике. Программирование на Python. Основы
70 ограничено 500 (при каждом вызове в стек будет попадать сразу два вызова – для lru_cache() и для fibonacci()).
Однако, мы можем найти обходной путь – последовательно вычислить все значения до необходимого нам. from functools import lru_cache
@lru_cache() def fibonacci(N): if N < 3: return 1 return fibonacci(N-1) + fibonacci(N-2) list(map(fibonacci, range(1000))) print(fibonacci(1000))
При таком подходе последовательный вызов функции fibonacci() позволит декоратору lru_cache() запомнить результаты для предыдущих значений (по умолчанию для последних 128) и наш алгоритм не будет совершать более двух рекурсивных вызовов для вычисления любого значения от 1 до 1000!

Открытый учебник по информатике. Программирование на Python. Основы
71
Модуль itertools
Полезные типы данных
Перед тем, как переходить к «ручному» написанию обработки последовательностей добавим в нашу копилку пару полезных типов данных.
Диапазон
Диапазон – генератор целых чисел в заданном диапазоне с указанным шагом.
Синтаксис объявления диапазона: range(start, stop, step)
Генерирует последовательность от start до stop (не включая) с шагом step. В целом работает аналогично нахождению среза (генерирует такие же значения, как значения индексов в срезе).
Тип данных «диапазон» относится к последовательностям. Поэтому к переменным такого типа применимы все операции, допустимые для последовательностей, в том числе срезы и обращение по индексу.
>>> range(1, 100, 2)[10]
21
Однако, две операции над последовательностями – конкатенация (сложение) и повторение (дублирование) – диапазонами не поддерживаются.
Интересный факт.
Срез для диапазона возвращает диапазон, в котором начало, конец и шаг изменены в соответствии с указанными в срезе параметрами.
>>> range(10,100, 4)[10:5:-2] range(50, 30, -8)
В данном примере первичный диапазон вернет числа 10, 14, 18, …, 90, 92, 96.
Срез, соответственно, вернет числа 50, 46, 42, 38, 34 с шагом 2 или ряд
50, 42, 34. Как видим, шаг стал -8, начальное значение 50, первое не перечисляемое значение – 30 (из первичного среза без изменения шага).

Открытый учебник по информатике. Программирование на Python. Основы
72
Множество
Множеством называет набор уникальных значений. Множество является коллекцией, отличается коллекция от последовательности тем, что в ней нет строгого порядка следования элементов, поэтому нельзя обращаться к элементам множества по индексу.
Пустое множество объявляется так: set_a = set()
Если необходимо заполнить множество уже известными значениями set_a = {1, 2, 3, 'value'}
Также в множество можно добавить все уникальные значения итерируемого объекта, например, уникальные символы в строке или неповторяющиеся элементы списка. uniq_str = set('Hello world!') # {'H','e','l','o','w','r','d'} uniq_list = set([1,2,3,2,3,4,1,5,2]) # [1, 2, 3, 4, 5]
Операции над множествами
Операция
Обозначение Пример
Добавить элемент s.add(value) s = set() s.add(5) # {5}
Объединение
(все элементы множеств)
A | B
>>>{1,2,3} | {2,3,4}
{1,2,3,4}
Пересечение
(общие элементы множеств)
A & B
>>>{1,2,3} & {2,3,4}
{2,3}
Вычитание
(элементы А, которых нет в В)
A - B
>>> {1,2,3} - {2,3,4}
{1}
Тождественность
(множества А и В содержат одни и те же элементы)
A == B
>>> {1,2} == {2, 1}
True
>>> {2,3,4} == {2,3}
False
Подмножество
(множество А входит в В)
A <= B
A < B
>>> {1,2,3}<={2,1,3,4}
True
>>> {1,2,3} < {3,1,2}
False
Супермножество
(множество А включает В)
A >= B
A > B
>>> {1,2,3} >= {2,1,3}
True
>>> {1,2,3} > {3,1,2}
False
Количество элементов len(s)
>>> len({1,3,5,1,7})
4
Также множества поддерживают операторы изменения объекта:|=, &=, -=.

Открытый учебник по информатике. Программирование на Python. Основы
73
Модуль itertools
На данный момент мы научились перебирать параллельные элементы в нескольких последовательностях с помощью map. Но что делать, если необходимо перебрать все возможные комбинации элементов последовательности?
На помощь приходит модуль itertools, который в числе прочего содержит функции, которые помогут последовательно перебрать такие комбинации.
Перед изучением следующих функций приведем общие свойства.
1) Итерируемые объекты полностью распаковываются перед обработкой.
То есть, если в качестве параметра передать итератор, сначала он будет распакован в последовательность и только затем обработан. Данное замечание очень важно, потому что результат бесконечных генераторов не может быть обработан таким образом. Также важный нюанс, что результат работы конечных итераторов может быть очень велик, что может вызвать проблемы, связанные с выделением памяти под объект-последовательность.
Например, при передаче файлового объекта в качестве параметра, то сначала весь файл будет прочитан и только потом обработана полученная последовательность.
2) Результаты возвращаются в возрастающем порядке. Порядок возрастания определяется исходя из обрабатываемой последовательности – меньше индекс элемента, меньше значение.
Например, если передать последовательность [3, 1, 11, 10], то возвращаемые комбинации будут получаться по правилу 3 1
<1 2
< 11 3
< 10 4
. Нижние индексы отображают номер элемента в переданной последовательности.
Можно провести аналогию с цифрами в системах счисления – комбинация
1В54 будет точно идти после комбинации 01А2. Для примера из последовательности цепочка 11 3
1 2
11 3 будет больше 3 1
1 2
11 3.
3) Функции не проверяют элементы последовательность на одинаковость.
Если при распаковке итерируемого объекта будут получены одинаковые элементы, то стоящий правее будет бóльшим.
Например, если передать последовательность [3, 3, 3, 3] с соответствующим порядком 3 1
< 3 2
< 3 3
< 3 3
. Функции будут воспринимать последовательности
3 1
3 1
3 2
3 3
и 3 2
3 1
3 2
3 3
как разны. Хотя с точки зрения значений элементов

Открытый учебник по информатике. Программирование на Python. Основы
74 последовательностей разницы нет (так как индекс не возвращается в сгенерированной последовательности).
4) Результат вызова любой рассматриваемой функции – итератор.
Генерируемая последовательность не возвращается сразу вся и, соответственно, не хранится вся в памяти. Поэтому, если необходимо получить последовательность сгенерированных последовательностей, нужно привести итератор к списку или кортежу.
Размещения без повторений
Функция, возвращающая все размещения длиной
r элементов последовательности – itertools.permutations. itertools.permutations(итерируемый_объект, r=длина_размещения)
Предположим, что у нас имеет последовательность s из 3 элементов –
[s1, s2, s3]. Результатом работы функции permutations(s, r=3) будет итератор, который вернет следующие кортежи всегда в таком порядке, независимо от того, есть ли в последовательности повторяющиеся элементы:
(s1,s2,s3),(s1,s3,s2),(s2,s1,s3),(s2,s3,s1),(s3,s1,s2),(s3,s2,s1)
Примеры.
>>> from itertools import permutations
>>> list(permutations('abc', r=3))
[('a',
'b',
'c'),
('a',
'c',
'b'),
('b',
'a',
'c'),
('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a') ]
>>> list(permutations('сссс', r=2))
[('с','с'),('с','с'),('с','с'),('с','с'),('с','с'),('с','с'),
('с','с'),('с','с'),('с','с'),('с','с'),('с','с'),('с','с')]
Что? Почему 12 одинаковых перестановок? Дело в том, что permutations отличает все символы c (в такой постановке у нас 4 разных символа с) и выдает нам перестановки каждого символа с со всеми остальными (4⸱3 штук).

Открытый учебник по информатике. Программирование на Python. Основы
75
Размещения с повторениями
Для работы с размещениями с повторениями есть функция product.
Функция product возвращает размещениями с повторениями для элементов передаваемых итерируемых объектов длиной, указанной в параметре repeat.
Если значение repeat не задано, то для нескольких итерируемых объектов комбинации, где на первом месте будут расположены элементы первого итерируемого объекта, на втором – второго и т.д.. Если же в качестве аргументов был подан только один итерируемый объект, то в качестве результата последовательно вернуться кортежи из одного элемента.
Для последовательности s из 3 элементов – [s1, s2, s3]. Результатом работы функции product(s, repeat=2) будет итератор, который вернет следующие кортежи всегда в таком порядке, независимо от того, есть ли в последовательности повторяющиеся элементы:
(s1,s1),(s1,s2),(s1,s3),(s2,s1),(s2,s2),(s2,s3),(s3,s1),(s3,s2),
(s3,s3)
Примеры.
>>> from itertools import product
>>> list(product('123'))
[('1',), ('2',), ('3',)]
>>> list(product('12', repeat=2))
[('1','1'), ('1','2'), ('2','1'), ('2','2')]
>>> list(product('abc', 'xy'))
[('a','x'), ('a','y'), ('b','x'), ('b','y'), ('c','x'), ('c','y')]
>>> list(product('bb', 'yyz'))
[('b','y'), ('b','y'), ('b','z'), ('b','y'), ('b','y'), ('b','z')]
>>> list(product('01', 'xy', repeat=2))
[('0', 'x', '0', 'x'), ('0', 'x', '0', 'y'), ('0', 'x', '1', 'x'),
('0', 'x', '1', 'y'), ('0', 'y', '0', 'x'), ('0', 'y', '0', 'y'),
('0', 'y', '1', 'x'), ('0', 'y', '1', 'y'), ('1', 'x', '0', 'x'),
('1', 'x', '0', 'y'), ('1', 'x', '1', 'x'), ('1', 'x', '1', 'y'),
('1', 'y', '0', 'x'), ('1', 'y', '0', 'y'), ('1', 'y', '1', 'x'),
('1', 'y', '1', 'y')]

Открытый учебник по информатике. Программирование на Python. Основы
76
Работу последнего примера можно проиллюстрировать с помощью следующего кода
>>> list(product(product('01', 'xy'), repeat=2))
[(('0', 'x'), ('0', 'x')), (('0', 'x'), ('0', 'y')), (('0', 'x'),
('1', 'x')), (('0', 'x'), ('1', 'y')), (('0', 'y'), ('0', 'x')),
(('0', 'y'), ('0', 'y')), (('0', 'y'), ('1', 'x')), (('0', 'y'),
('1', 'y')), (('1', 'x'), ('0', 'x')), (('1', 'x'), ('0', 'y')),
(('1', 'x'), ('1', 'x')), (('1', 'x'), ('1', 'y')), (('1', 'y'),
('0', 'x')), (('1', 'y'), ('0', 'y')), (('1', 'y'), ('1', 'x')),
(('1', 'y'), ('1', 'y'))]
Заметим, что в таком случае имеем дело с парами кортежей из seq. В предыдущем примере этап формирования кортежей пропущен, поэтому имеем дело с четверками, порядок следования элементов в которых соответствует порядку следования в парах кортежей.
Например, вместо
(('0', 'x'), ('1', 'y')) имеем
('0', 'x', '1', 'y')
).
Сочетания
Функция для получения сочетаний без повторений – itertools.combinations.
Количество элементов в сочетании устанавливается через параметр r, который является обязательным параметром.
Для последовательности s из 3 элементов – [s1, s2, s3]. Результатом работы функции combinations(s, r=2) будет итератор, который вернет следующие кортежи всегда в таком порядке, независимо от того, есть ли в последовательности повторяющиеся элементы:
(s1,s2), (s1,s3), (s2,s3)
Примеры.
>>> from itertools import combinations
>>> list(combinations('bbb', r=2))
[('b', 'b'), ('b', 'b'), ('b', 'b')]
>>> from itertools import combinations
>>> list(combinations('abc', r=2))
[('a', 'b'), ('a', 'c'), ('b', 'c')]

Открытый учебник по информатике. Программирование на Python. Основы
77
Про уникальные комбинации
Если же мы хотим обработать только уникальные комбинации или не обрабатывать одинаковые, можно преобразовать возвращаемый итератор в множество и обработать только уникальные значения.
>>>from itertools import combinations
>>>set(combinations('bbc', r=2))
{('b', 'b'), ('b', 'c')}
1>