Программирование на Python 3. Руководство издательство СимволПлюс
 Скачать 3.74 Mb.
|
|
409 Локальные и рекурсивные функции Часто бывает удобно иметь внутри функции одну две вспомогатель ные функции. Язык Python позволяет делать это без лишних сложно стей – достаточно просто объявить функцию внутри существующей функции. Такие функции часто называют вложенными или локальны ми . Мы уже видели примеры таких функций в главе 7. Одна из типичных ситуаций использования локальных функций – ко гда необходимо организовать рекурсию. В этих случаях вызывается объемлющая функция, она выполняет все необходимые предваритель ные операции и производит первый вызов рекурсивной функции. Ре курсивными называются функции или методы, которые вызывают се бя сами. Структурно все рекурсивные функции предусматривают два случая: базовый случай и рекурсивный случай. Базовый случай ис пользуется для прекращения рекурсии. Рекурсивные функции могут оказаться весьма затратными в смысле потребления вычислительных ресурсов, потому что для каждого ре курсивного вызова создается новый кадр стека; тем не менее некото рые алгоритмы наиболее естественно реализуются с использованием рекурсии. В большинстве реализаций интерпретатора Python имеется ограничение на глубину возможных рекурсивных вызовов. Значение этого ограничения можно получить, обратившись к функции sys.get recursionlimit() , и изменить его с помощью функции sys.setrecursion limit() , хотя необходимость увеличения этого ограничения часто сви детельствует об использовании неподходящего алгоритма или об ошибке в реализации. Классическим примером рекурсивной функции является функция вы числения факториала. 1 Например, вызов factorial(5) вычислит значе ние 5! и вернет число 120, то есть 1 ×2×3×4×5: def factorial(x): if x <= 1: return 1 return x * factorial(x 1) Это не самое эффективное решение, но оно наглядно демонстрирует две фундаментальные особенности рекурсивных функций. Если в ар гументе x передается число 1 или меньше, функция возвращает 1 и ре курсии не возникает – это базовый случай. Но если значение аргумен та x больше 1, возвращается значение x * factorial(x – 1) , и это уже рекурсивный случай, так как здесь функция вызывает саму себя. Эта функция гарантирует, что рано или поздно завершит свою работу, по тому что в случае, когда значение x меньше или равно 1, выполняется базовый случай, который тут же завершает работу функции, а когда 1 В модуле math имеется более эффективная функция вычисления факториа ла math.factorial(). 410 Глава 8. Усовершенствованные приемы программирования значение x больше 1, каждый рекурсивный вызов будет уменьшать это значение на 1, в результате чего оно рано или поздно достигнет значе ния 1. Чтобы увидеть локальные и рекурсивные функции в осмысленном контексте, мы рассмотрим функцию indented_list_sort(), которая оп ределена в файле модуля IndentedList.py. Эта функция принимает список строк, в котором отступы используются для обозначения ие рархии, и строку, в которой хранится отступ на один уровень, а воз вращает список с теми же строками, но отсортированными в алфавит ном порядке без учета регистра символов, где элементы с отступами рекурсивно отсортированы в пределах своего родительского элемента. Результат работы функции показан на рис. 8.1, в списках before (до сортировки) и after (после сортировки). Пусть дан список before, тогда список after – результат вызова: after = IndentedList.indented_list_sort(before) . По умолчанию в качестве от ступа на один уровень используются четыре пробела, такой же отступ используется в строках списка before, поэтому мы не будем явно ука зывать строку отступа при вызове функции. Сначала мы рассмотрим функцию indented_list_sort() в целом, а за тем перейдем к двум ее локальным функциям. def indented_list_sort(indented_list, indent=" "): KEY, ITEM, CHILDREN = range(3) before = ["Nonmetals", after = ["Alkali Metals", " Hydrogen", " Lithium", " Carbon", " Potassium", " Nitrogen", " Sodium", " Oxygen", "Inner Transitionals", "Inner Transitionals", " Actinides", " Lanthanides", " Curium", " Cerium", " Plutonium", " Europium", " Uranium", " Actinides", " Lanthanides", " Uranium", " Cerium", " Curium", " Europium", " Plutonium", "Nonmetals", "Alkali Metals", " Carbon", " Lithium", " Hydrogen", " Sodium", " Nitrogen", " Potassium"] " Oxygen"] Рис. 8.1. До и после сортировки списка, содержащего строки с отступами Улучшенные приемы процедурного программирования 411 def add_entry(level, key, item, children): def update_indented_list(entry): entries = [] for item in indented_list: level = 0 i = 0 while item.startswith(indent, i): i += len(indent) level += 1 key = item.strip().lower() add_entry(level, key, item, entries) indented_list = [] for entry in sorted(entries): update_indented_list(entry) return indented_list Функция начинается с создания трех констант, которые будут слу жить именами индексов, используемых локальными функциями. За тем определяются две локальные функции, которые будут рассмотре ны чуть позже. Работа алгоритма сортировки делится на две стадии. На первой стадии создается список элементов, каждый из которых представлен трехэлементным кортежем, содержащим «ключ», ис пользуемый при сортировке, оригинальную строку и список дочерних элементов со строками. Ключ – это та же самая строка, в которой все символы приведены к нижнему регистру и удалены начальные и за вершающие пробелы. В переменной level хранится текущий уровень отступа, для элементов верхнего уровня это значение 0, для элемен тов, дочерних по отношению к верхнему уровню это значение 1 и т. д. На второй стадии создается новый список, куда добавляются строки из отсортированного списка элементов верхнего уровня, строки дочер них элементов и т. д. def add_entry(level, key, item, children): if level == 0: children.append((key, item, [])) else: add_entry(level 1, key, item, children[1][CHILDREN]) Эта функция вызывается для каждой строки в списке. Аргумент chil dren – это список, куда должны добавляться новые элементы. При вы зове из внешней функции (indented_list_sort()) ей передается список entries . Эта функция превращает список строк в список элементов, ка ждый из которых содержит строку верхнего уровня (без отступов) и (возможно, пустой) список дочерних элементов. На уровне 0 (на самом верхнем уровне) в список entries добавляется новый кортеж из трех элементов. Он содержит ключ (для сортировки), 412 Глава 8. Усовершенствованные приемы программирования оригинальный элемент (который будет перемещен в список с результа тами) и пустой список дочерних записей. Это базовый случай, так как здесь рекурсия не возникает. На других уровнях элемент item являет ся дочерним по отношению к последнему элементу в списке children. В этом случае функция рекурсивно вызывает саму себя, уменьшая уро вень на 1 и передавая дочерний список последнего элемента в списке children . На уровне 2 и выше выполняется несколько рекурсивных вы зовов, пока наконец не будет достигнут уровень 0 и не будет получен нужный список для добавления элемента. Например, когда дело доходит до строки «Inner Transitionals», внеш няя функция вызывает функцию add_entry() со значением 0 в аргумен те level, с ключом «inner transitionals», с элементом «Inner Transitio nals» и списком entries в качестве списка дочерних записей. Посколь ку текущим является уровень 0, новый элемент просто добавляется в список дочерних элементов (entries) с указанным ключом, элемен том и пустым списком дочер них элементов. Следующая строка – « Lanthanides»; имеется отступ, следовательно, эта строка – дочер няя для строки «Inner Transitionals». Функция add_entry() вызывает ся со значением 1 в аргументе level, с ключом «lanthanides», с элемен том « Lanthanides» и списком entries в качестве списка дочерних за писей. Так как текущим является уровень 1, функция add_entry() ре курсивно вызовет саму себя со значением 0 (1 – 1) в аргументе level, с тем же самым ключом и элементом и со списком дочерних элемен тов, принадлежащим последнему элементу, то есть со списком дочер них элементов для элемента «Inner Transitionals». Ниже показано, как выглядит список entries после добавления всех строк, но перед сортировкой: [('nonmetals', 'Nonmetals', [('hydrogen', ' Hydrogen', []), ('carbon', ' Carbon', []), ('nitrogen', ' Nitrogen', []), ('oxygen', ' Oxygen', [])]), ('inner transitionals', 'Inner Transitionals', [('lanthanides', ' Lanthanides', [('cerium', ' Cerium', []), ('europium', ' Europium', [])]), ('actinides', ' Actinides', [('uranium', ' Uranium', []), ('curium', ' Curium', []), ('plutonium', ' Plutonium', [])])]), ('alkali metals', 'Alkali Metals', [('lithium', ' Lithium', []), Улучшенные приемы процедурного программирования 413 ('sodium', ' Sodium', []), ('potassium', ' Potassium', [])])] Вывод списка был произведен с помощью функции pprint.pprint() из модуля pprint («pretty print» – модуль функций форматированного вывода). Обратите внимание, что список entries содержит всего три элемента (каждый из которых представлен трехэлементным корте жем) и в каждом из них последний элемент кортежа является списком дочерних трехэлементных кортежей (или пустым списком). Функция add_entry() одновременно является и локальной и рекурсив ной функцией. Подобно любой рекурсивной функции в ней предусмат ривается базовый случай действий (в этой функции он выполняется, когда текущим является уровень 0), завершающий рекурсию, и рекур сивный случай Эту функцию можно определить немного иначе: def add_entry(key, item, children): nonlocal level if level == 0: children.append((key, item, [])) else: level = 1 add_entry(key, item, children[1][CHILDREN]) Здесь вместо того чтобы передавать значение level в качестве парамет ра, используется инструкция nonlocal, которая обеспечивает доступ к переменной в объемлющей области видимости. Если бы функция не изменяла переменную level, то инструкция nonlocal была бы не нуж на, так как в этом случае интерпретатор, не обнаружив ее в локальной области видимости (во внутренней функции), продолжил бы поиски в объемлющей области видимости, где и нашел бы эту переменную. Но в этой версии функции add_entry() предусматривается изменение зна чения переменной level. Ранее мы использовали инструкцию global, чтобы сообщить интерпретатору, что подразумевается изменение гло бальной переменной (чтобы предотвратить создание новой локальной переменной вместо изменения существующей глобальной перемен ной); это относится ко всем переменным, которые требуется изменить и которые находятся в одной из внешних областей видимости. Если в большинстве случаев использования инструкции global лучше про сто избегать, то к использованию инструкции nonlocal следует отно ситься по крайней мере с осторожностью. def update_indented_list(entry): indented_list.append(entry[ITEM]) for subentry in sorted(entry[CHILDREN]): update_indented_list(subentry) На первой стадии алгоритма создается список элементов, каждый из которых представлен кортежем из трех элементов (ключ, элемент, 414 Глава 8. Усовершенствованные приемы программирования список дочерних элементов), следующих в том же порядке, в каком они находятся в оригинальном списке. Во второй стадии, с пустым списком результата в начале, выполняются итерации через отсортиро ванный список entries, и для каждого элемента вызывается функция update_indented_list() , которая выстраивает новый список с результа тами. Функция update_indented_list() является рекурсивной. Она до бавляет каждый элемент верхнего уровня в список indented_list, после чего вызывает саму себя, чтобы добавить все элементы из списка до черних элементов. Добавив очередной дочерний элемент в список indented_list , функция вновь вызывает саму себя, чтобы добавить до черние элементы этого дочернего элемента, и т. д. Базовый случай (ко гда прекращается рекурсия) наступает, когда элемент, или дочерний элемент, или дочерний элемент дочернего элемента (и так далее), не имеет дочерних элементов. Интерпретатор пытается отыскать список indented_list в локальной области видимости (во внутренней функции) и не находит его; тогда он пытается отыскать список в объемлющей области видимости и нахо дит его там. Но, обратите внимание, что во внутренней функции про изводится добавление элементов в список indented_list, хотя инструк ция nonlocal при этом не использовалась. Это возможно потому, что инструкция nonlocal (как и инструкция global) применяется к ссыл кам на объекты, а не к самим объектам, на которые они ссылаются. Во второй версии функции add_entry() мы использовали инструкцию non local для переменной level потому, что применяемый оператор += свя зывает ссылку на объект с новым объектом, то есть в действительности выполняется операция level = level + 1, поэтому в переменную level записывается ссылка на новый объект типа int. Но когда вызывается метод list.append() для списка indented_list, изменяется сам список, то есть повторного присваивания ссылки здесь не происходит, и пото му нет необходимости в использовании инструкции nonlocal. (По тем же самым причинам, если у нас имеется словарь, список или другая глобальная коллекция, мы можем добавлять и удалять элементы кол лекции без использования инструкции global.) Декораторы функций и методов Декоратор – это функция, которая принимает функцию или метод в качестве единственного аргумента и возвра щает новую функцию или метод, включающую декори рованную функцию или метод, с дополнительными функциональными возможностями. Нам уже приходи лось использовать некоторые предопределенные декора торы, например, @property и @classmethod. В этом подраз деле мы узнаем, как создавать собственные декораторы функций, а позднее в этой главе узнаем, как создавать декораторы классов. Декораторы классов, стр. 438 Улучшенные приемы процедурного программирования 415 Для первого примера декоратора предположим, что у нас имеется мно жество функций, выполняющих вычисления, и некоторые из них все гда должны возвращать положительный результат. Мы могли бы до бавить в каждую из таких функций инструкцию assert, но использова ние декораторов проще и понятнее. Ниже приводится функция, деко рированная декоратором @positive_result, который будет создан чуть ниже: @positive_result def discriminant(a, b, c): return (b ** 2) (4 * a * c) Благодаря декоратору, если функция вернет отрицательный резуль тат, будет возбуждено исключение AssertionError и программа завер шит работу. И конечно, этот декоратор можно применить к любому числу функций. Ниже приводится реализация декоратора: def positive_result(function): def wrapper(*args, **kwargs): result = function(*args, **kwargs) assert result >= 0, function.__name__ + "() result isn't >= 0" return result wrapper.__name__ = function.__name__ wrapper.__doc__ = function.__doc__ return wrapper Декоратор определяет новую локальную функцию, которая вызывает оригинальную функцию. В данном случае объявляется локальная функция wrapper(). Она вызывает оригинальную функцию и запоми нает результат, который используется в инструкции assert, проверяю щей результат на положительность (или на необходимость завершить программу). Функция wrapper() просто возвращает результат, полу ченный от декорируемой функции. После создания функции wrapper() ее имя и строка документирования приводятся в соответствие с ориги нальной функцией. Этим обеспечивается содействие механизму ин троспекции, то есть в сообщениях об ошибках будет фигурировать имя оригинальной функции, а не функции wrapper(). Наконец декоратор возвращает функцию wrapper() – с этого момента она будет использо ваться взамен оригинальной. def positive_result(function): @functools.wraps(function) def wrapper(*args, **kwargs): result = function(*args, **kwargs) assert result >= 0, function.__name__ + "() result isn't >= 0" return result return wrapper Выше приводится немного более понятная версия декоратора @positi ve_result . На этот раз функция wrapper() сама обертывается декорато ром @functools.wraps из модуля functools, который гарантирует, что 416 Глава 8. Усовершенствованные приемы программирования функция wrapper() будет носить имя оригинальной функции и содер жать ее строку документирования. В некоторых случаях бывает удобно иметь параметризуемый декора тор, но, на первый взгляд, это кажется невозможным, так как декора торы принимают единственный аргумент – функцию или метод. У этой проблемы имеется замечательное решение. Мы можем вызвать функцию с требуемыми параметрами, и она вернет декоратор, кото рый будет использован для декорирования следующей за ним функ ции. Например: @bounded(0, 100) def percent(amount, total): return (amount / total) * 100 Здесь функция bounded() вызывается с двумя аргументами и возвраща ет декоратор, который используется для декорирования функции per cent() . Цель данного декоратора состоит в том, чтобы гарантировать, что возвращаемое значение всегда будет находиться в диапазоне от 0 до 100 включительно. Ниже приводится реализация функции bounded(): def bounded(minimum, maximum): def decorator(function): @functools.wraps(function) def wrapper(*args, **kwargs): result = function(*args, **kwargs) if result < minimum: return minimum elif result > maximum: return maximum return result return wrapper return decorator Эта функция создает функцию декоратор, которая в свою очередь соз дает функцию обертку. Функция обертка выполняет вычисления и воз вращает результат, который гарантированно будет находиться в за данных пределах. Функция decorator() возвращает функцию wrap per() , а функция bounded() возвращает декоратор. Следует отметить, что всякий раз, когда вызывается функция bound ed() , внутри нее создается новый экземпляр функции обертки, кото рая получает минимальное и максимальное значения, переданные при вызове bounded(). Последний декоратор, который будет создан в этом разделе, имеет не много более сложную реализацию. Это функция регистрации, которая записывает имя, аргументы и результат любой декорируемой функ ции. Например: @logged def discounted_price(price, percentage, make_integer=False): |