Курс лекций по Python. Курс лекций по Python (ru). 1. Лекция Введение в программирование на языке Python
![]()
|
3. Лекция: Элементы функциональногоdct = {'a': 'abc', 'b': 'sdf'} print swiss_knife(1, *lst, **dct) Пример определения функции с помощью lambda–выражения дан ниже: Листинг func = lambda x, y: x + y В результате lambda–выражения получается безымянный объект–функция, которая затем используется, например, для того, чтобы связать с ней некоторое имя. Однако, как правило, определяемые lambda–выражением функции, применяются в качестве параметров функций. В языке Python функция может возвратить только одно значение, которое может быть кортежем. В следующем примере видно, как стандартная функция divmod() возвращает частное и остаток от деления двух чисел: Листинг def bin(n): «"«Цифры двоичного представления натурального числа """ digits = [] while n > 0: n, d = divmod(n, 2) digits = [d] + digits return digits print bin(69) Примечание: Важно понять, что за именем функции стоит объект. Этот объект можно связать с другим именем: def add(x, y): return x + y addition = add # теперь addition и add — разные имена одного и того же объекта Пример, в котором в качестве значения по умолчанию аргумента функции используется изменчивый объект (список). Этот объект — один и тот же для всех вызовов функций, что может привести к казусам: Листинг def mylist(val, lst=[]): lst.append(val) return lst print mylist(1), print mylist(2) Вместо ожидаемого [1] [2] получается [1] [1, 2], так как добавляются элементы к «значению по умолчанию». Правильный вариант решения будет, например, таким: Листинг def mylist(val, lst=None): lst = lst or [] return lst Конечно, приведенная выше форма может использоваться для хранения в функции некоторого состояния между ее вызовами, однако, практически всегда вместо функции с таким побочным эффектом лучше написать класс и использовать его экземпляр. Рекурсия В некоторых случаях описание функции элегантнее всего выглядит с применением вызова этой же функции. Такой прием, когда функция вызывает саму себя, называется рекурсией. В функциональных языках рекурсия обычно используется много чаще, чем итерация (циклы). В следующем примере переписывается функция bin() в рекурсивном варианте: Листинг def bin(n): «"«Цифры двоичного представления натурального числа """ if n == 0: return [] n, d = divmod(n, 2) return bin(n) + [d] print bin(69) Здесь видно, что цикл while больше не используется, а вместо него появилось условие окончания рекурсии: условие, при выполнении которого функция не вызывает себя. Конечно, в погоне за красивым рекурсивным решением не следует упускать из виду эффективность реализации. В частности, пример реализации функции для вычисления n–го числа Фибоначчи это демонстрирует: Листинг def Fib(n): if n < 2: return n else: return Fib(n–1) + Fib(n–2) В данном случае количество рекурсивных вызовов растет экспоненциально от числа n, что совсем не соответствует временной сложности решаемой задачи. В качестве упражнения предлагается написать итеративный и рекурсивный варианты этой функции, которые бы требовали линейного времени для вычисления результата. Предупреждение: При работе с рекурсивными функциями можно легко превысить глубину допустимой в Python рекурсии. Для настройки глубины рекурсии следует использовать функцию setrecursionlimit(N) из модуля sys, установив требуемое значение N. Функции как параметры и результат Как уже не раз говорилось, функции являются такими же объектами Python как числа, строки или списки. Это означает, что их можно передавать в качестве параметров функций или возвращать из функций. Функции, принимающие в качестве аргументов или возвращающие другие функции в Например, алгоритм поиска может вызывать переданную ему функцию для каждого найденного объекта. Функция apply() Функция apply() применяет функцию, переданную в качестве первого аргумента, к параметрам, которые переданы вторым и третьим аргументом. Эта функция в Python устарела, так как вызвать функцию можно с помощью обычного синтаксиса вызова функции. Позиционные и именованные параметры можно передать с использованием звездочек: Листинг >>> lst = [1, 2, 3] >>> dct = {'a': 4, 'b': 5} >>> apply(max, lst) 3 >>> max(*lst) 3 >>> apply(dict, [], dct) {'a': 4, 'b': 5} >>> dict(**dct) {'a': 4, 'b': 5} Обработка последовательностей Многие алгоритмы сводятся к обработке массивов данных и получению новых массивов данных в результате. Среди встроенных функций Python есть несколько для работы с последовательностями. Под последовательностью в Python понимается любой тип данных, который поддерживает интерфейс последовательности (это несколько специальных методов, реализующих операции над последовательностями, которые в данном курсе обсуждаться не будут). Следует заметить, что тип, основной задачей которого является хранение, манипулирование и обеспечение доступа к самостоятельным данным называется контейнерным типом или просто контейнером. Примеры контейнеров в Python — списки, кортежи, словари. Функции range() и xrange() Функция range() уже упоминалась при рассмотрении цикла for. Эта функция принимает от одного до трех аргументов. Если аргумент всего один, она генерирует список чисел от 0 (включительно) до заданного числа (исключительно). Если аргументов два, то список начинается с числа, указанного первым аргументом. Если аргументов три — третий аргумент задает шаг Листинг >>> print range(10) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> print range(1, 10) [1, 2, 3, 4, 5, 6, 7, 8, 9] print reduce(f, lst, (0, [])) В итоге получается: Листинг (45, [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]) Функция zip() Эта функция возвращает список кортежей, в котором i–й кортеж содержит i–е элементы аргументов–последовательностей. Длина результирующей последовательности равна длине самой короткой из последовательностей–аргументов: Листинг >>> print zip(range(5), «abcde») [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e')] Итераторы Применять для обработки данных явные последовательности не всегда эффективно, так как на хранение временных данных может тратиться много оперативной памяти. Более эффективным решением представляется использование итераторов — специальных объектов, обеспечивающих последовательный доступ к данным контейнера. Если в выражении есть операции с итераторами вместо контейнеров, промежуточные данные не будут требовать много места для хранения — ведь они запрашиваются по мере необходимости для вычислений. При обработке данных с использованием итераторов память будет требоваться только для исходных данных и результата, да и то необязательно вся сразу — ведь данные могут читаться и записываться в файл на диске. Итераторы можно применять вместо последовательности в операторе for. Более того, внутренне оператор for запрашивает от последовательности ее итератор. Объект файлового типа тоже (построчный) итератор, что позволяет обрабатывать большие файлы, не считывая их целиком в память. Там, где требуется итератор, можно использовать последовательность. Работа с итераторами рассматривается в разделе, посвященном функциональному программированию, так как итераторами удобно манипулировать именно в функциональном стиле. Использовать итератор можно и «вручную». Любой объект, поддерживающий интерфейс итератора, имеет метод next(), который при каждом вызове выдает очередное значение итератора. Если больше значений нет, возбуждается исключение StopIteration. Для получения итератора по некоторому объекту необходимо прежде применить к этому объекту функцию iter() (цикл for делает это автоматически). В Python имеется модуль itertools, который содержит набор функций, комбинируя которые, можно составлять достаточно сложные схемы обработки данных с помощью итераторов. Далее рассматриваются некоторые функции этого модуля. Функция iter() Эта функция имеет два варианта использования. В первом она принимает всего один аргумент, который должен «уметь» предоставлять свой итератор. Во втором один из аргументов — функция без аргументов, другой — стоповое значение. Итератор вызывает указанную функцию до тех пор, пока та не возвратит стоповое значение. Второй вариант встречается много реже первого и обычно внутри метода класса, так как сложно порождать значения «на пустом месте»: print i, 1 1 1 1 Функция itertools.count() Бесконечный итератор, дающий целые числа, начиная с заданного: Листинг for i in itertools.count(1): print i, if i > 100: break 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 Функция itertools.cycle() Можно бесконечно повторять и некоторую последовательность (или значения другого итератора) с помощью функции cycle(): Листинг tango = [1, 2, 3] for i in itertools.cycle(tango): print i, 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 … Функции itertools.imap(), itertools.starmap() и itertools.ifilter() Аналогами map() и filter() в модуле itertools являются imap() и ifilter(). Отличие imap() от map() в том, что вместо значения от преждевременно завершившихся итераторов объект None не подставляется. Пример: Листинг for i in map(lambda x, y: (x,y), [1,2], [1,2,3]): print i, (1, 1) (2, 2) (None, 3) from itertools import imap for i in imap(lambda x, y: (x,y), [1,2], [1,2,3]): print i, (1, 1) (2, 2) Здесь следует заметить, что обычная функция map() нормально воспринимает Листинг for i in map(lambda x, y: (x,y), iter([1,2]), [1,2,3]): print i, (1, 1) (2, 2) (None, 3) Функция itertools.starmap() подобна itertools.imap(), но имеет всего два аргумента. Второй аргумент — последовательность кортежей, каждый кортеж которой задает набор параметров для функции (первого аргумента): Листинг >>> from itertools import starmap >>> for i in starmap(lambda x, y: str(x) + y, [(1,'a'), (2,'b')]): … print i, … 1a 2b Функция ifilter() работает как filter(). Кроме того, в модуле itertools есть функция ifilterfalse(), которая как бы добавляет отрицание к значению функции: Листинг for i in ifilterfalse(lambda x: x > 0, [1, — 2, 3, — 3]): print i, — 2–3 Функции itertools.takewhile() и itertools.dropwhile() Некоторую новизну вносит другой вид фильтра: takewhile() и его «отрицательный» аналог dropwhile(). Следующий пример поясняет их принцип действия: Листинг for i in takewhile(lambda x: x > 0, [1, — 2, 3, — 3]): print i, print for i in dropwhile(lambda x: x > 0, [1, — 2, 3, — 3]): print i, 1 — 2 3–3 Таким образом, takewhile() дает значения, пока условие истинно, а остальные значения даже не берет из итератора (именно не берет, а не высасывает все до конца!). И, наоборот, dropwhile() ничего не выдает, пока выполняется условие, зато потом выдает все без остатка. Функция itertools.izip() Функция izip() аналогична встроенной zip(), но не тратит много памяти на построение списка кортежей, так как итератор выдает их строго по требованию. Функция itertools.groupby() Эта функция дебютировала в Python 2.4. Функция принимает два аргумента: итератор (обязательный) и необязательный аргумент — функцию, дающую значение ключа: groupby(iterable[, func]). Результатом является итератор, который возвращает двухэлементный кортеж: ключ и итератор по идущим подряд элементам с этим ключом. Если второй Листинг import itertools, math lst = map(lambda x: math.sin(x*.4), range(30)) for k, i in itertools.groupby(lst, lambda x: x > 0): print k, list(i) Функция itertools.tee() Эта функция тоже появилась в Python 2.4. Она позволяет клонировать итераторы. Первый аргумент — итератор, подлежащий клонированию. Второй (N) — количество необходимых копий. Функция возвращает кортеж из N итераторов. По умолчанию N=2. Функция имеет смысл, только если итераторы задействованы более или менее параллельно. В противном случае выгоднее превратить исходный итератор в список. Собственный итератор Для полноты описания здесь представлен пример итератора, определенного пользователем. Если пример не очень понятен, можно вернуться к нему после изучения объектно–ориентированного программирования: Листинг class Fibonacci: «"«Итератор последовательности Фибоначчи до N»"" def __init__(self, N): self.n, self.a, self.b, self.max = 0, 0, 1, N def __iter__(self): # сами себе итератор: в классе есть метод next() return self def next(self): if self.n < self.max: a, self.n, self.a, self.b = self.a, self.n+1, self.b, self.a+self.b return a else: raise StopIteration # Использование: for i in Fibonacci(100): print i, Простые генераторы Разработчики языка не остановились на итераторах. Как оказалось, в интерпретаторе Python достаточно просто реализовать простые генераторы. Под этим термином фактически понимается специальный объект, вычисления в котором продолжаются до выработки очередного значения, а затем приостанавливаются до возникновения необходимости в выдаче следующего значения. Простой генератор формируется функцией–генератором, которая синтаксически похожа на обычную функцию, но использует специальный оператор yield для выдачи следующего значения. При вызове такая функция ничего не вычисляет, а который будет функционально эквивалентной «ленивой» реализацией. Ленивыми называются вычисления, которые откладываются до самого последнего момента, когда получаемое в результате значение сразу используется в другом вычислении. Для примера с последовательностью Фибоначчи можно построить такой вот генератор: Листинг def Fib(N): a, b = 0, 1 for i in xrange(N): yield a a, b = b, a + b Использовать его не сложнее, чем любой другой итератор: Листинг for i in Fib(100): print i, Однако следует заметить, что программа в значительной степени упростилась. Генераторное выражение В Python 2.4 по аналогии со списковым включением появилось генераторное выражение. По синтаксису оно аналогично списковому, но вместо квадратных скобок используются круглые. Списковое включение порождает список, а, значит, можно ненароком занять очень много памяти. Генератор же, получающийся в результате применения генераторного выражения, списка не создает, он вычисляет каждое следующее значение строго по требованию (при вызове метода next()). В следующем примере можно прочесть из файла строки, в которых производятся некоторые замены: Листинг for line in (l.replace(" — ", " — ") for l in open(«input.dat»)): print line Ничто не мешает использовать итераторы и для записи в файл: Листинг open(«output.dat», «w»).writelines( l.replace(" — ", " — ") for l in open(«input.dat»)) Здесь для генераторного выражения не потребовалось дополнительных скобок, так как оно расположено внутри скобок вызова функции. Карринг Библиотека Xoltar toolkit (автор Bryn Keller) включает модуль functional, который позволяет упростить использование возможностей функционального программирования. Модуль functional применяет «чистый» Python. Библиотеку можно найти по адресу: http://sourceforge.net/projects/xoltar–toolkit. При карринге (частичном применении) функции создается новая функция, задавая некоторые аргументы исходной. Следующий пример иллюстрирует частичное применение вычитания: Листинг from functional import curry return x — y print subtract(3, 2) subtract_from_3 = curry(subtract, 3) print subtract_from_3(2) print curry(subtract, 3)(2) Во всех трех случаях будет выведено 1. В следующем примере получается новая функция, подставляя второй аргумент. Вместо другого аргумента вставляется специальное значение Blank: Листинг from functional import curry, Blank def subtract(x, y): return x + y print subtract(3, 2) subtract_2 = curry(subtract, Blank, 2) print subtract_2(3) print curry(subtract, Blank, 2)(3) Заключение В этой лекции рассматривался принцип построения функциональных программ. Кроме того, было показано, что в Python и его стандартных модулях имеются достаточно мощные выразительные средства для создания функциональных программ. В случае, когда требуются дополнительные возможности, например, карринг, их можно легко реализовать или взять готовую реализацию. Следует отметить, что итераторы — это практичное продолжение функционального начала в языке Python. Итераторы по сути позволяют организовать так называемые ленивые вычисления (lazy computations), при которых значения вычисляются только когда они непосредственно требуются. Ссылки по теме Статья Д. Мертца http://www–106.ibm.com/developerworks/library/l–prog.html Часто задаваемые вопросы в comp.lang.functional http://www.cs.nott.ac.uk/gmh/faq.html |