Саммерфилд - Программирование на Python 3 (1077331), страница 91
Текст из файла (страница 91)
Простое решение этой проблемы состоит в том, чтобы в составе кортежа, применяемого в качестве ключа, использовать не сам модуль, а значение атрибута паве модуля. Импортировать модули динамически очень просто, и также просто выполнять произвольный программный код на языке РусЬоп с помощью функции ехес( ) . Это может быть очень удобно, например, когда программный код хранится в базе данных.
Однако при этом отсутствует какой-либо контроль над импортируемым или выполняемым программным кодом. Вспомните, что, помимо дополнительных переменных, функций и классов, модули могут также содержать программный код, выполняемый при импортировании. Если такой программный код поступает из непроверенных источников, он может доставить массу неприятностей. Выбор решения зависит от конкретной ситуации — это не может быть поводом для беспокойства в определенных случаях или в личных проектах.
В программе тая«с-питьегз.ру наряду с яоказавной здесь функцией дег гппсыоп() присутствует более сложная ее реализация, которая эффективнее обрабатывает модули, в которых отсутствуют искомые функциональные возможности. 409 Улучшенные приемы процедурного программирования Локальные и рекурсивные функции Часто бывает удобно иметь внутри функции одну-две вспомогательные функции. Язык РуФЬоп позволяет делать это без лишних сложностей — достаточно просто объявить функцию внутри существующей функции. Такие функции часто называют вложенными или локальными. Мы уже видели примеры таких функций в главе 7. Одна из типичных ситуаций использования локальных функций — когда необходимо организовать рекурсию.
В этих случаях вызывается объемлющая функция, она выполняет все необходимые предварительные операции и производит первый вызов рекурсивной функции. Рекурсивными называются функции или методы, которые вызывают себя сами. Структурно все рекурсивные функции предусматривают два случая: базовый случай и рекурсивный случай. Базовый случай используется для прекращения рекурсии. Рекурсивные функции могут оказаться весьма затратными в смысле потребления вычислительных ресурсов, потому что для каждого рекурсивного вызова создается новый кадр стека; тем не менее некоторые алгоритмы наиболее естественно реализуются с использованием рекурсии.
В большинстве реализаций интерпретатора Ру1Ьоп имеется ограничение на глубину возможных рекурсивных вызовов. Значение этого ограничения можно получить, обратившись к функции вув. сеггессгв1сп11з11(), и изменить его с помощью функции вуз. зетгесогв!сп11зм(), хотя необходимость увеличения этого ограничения часто свих детельствует об использовании неподходящего алгоритма или об ошибке в реализации.
Классическим примером рекурсивной функции является функция вычисления факториала.' Например, вызов гвсгсг1а1(5) вычислит значение 5! и вернет число 120, то есть 1х2хЗх4хб: Сеу ГасГсма1!х): 1Г х <= 1: гессгп 1 геспгп х Гастсг1а1(х - 1) Это не самое эффективное решение, но оно наглядно демонстрирует две фундаментальные особенности рекурсивных функций. Если в аргументе х передается число 1 или меньше, функция возвращает 1 и рекурсии не возникает — это базовый случай. Но если значение аргумента х больше 1, возвращается значение х * гасгсг1а1(х - 1), и это уже рекурсивный случай, так как здесь функция вызывает саму себя. Эта функция гарантирует, что рано или поздно завершит свою работу, потому что в случае, когда значение х меньше или равно 1, выполняется базовый случай, который тут же завершает работу функции, а когда В модуле ва1п имеется более эффективная функция вычисления факториа- ла ваСЬ.
Гасссг1а1(). 410 Глава 8, Усовершенствованные приемы программирования значение х больше 1, каждый рекурсивный вызов будет уменьшать это значение на 1, в результате чего оно рано или поздно достигнет значе- ния 1. Чтобы увидеть локальные и рекурсивные функции в осмысленном контексте, мы рассмотрим функцию 1пееп1ее 11вт вог1(), которая определена в файле модуля 1пгйепгегПйвкру. Эта функция принимает список строк, в котором отступы используются для обозначения иерархии, и строку, в которой хранится отступ на один уровень, а возвращает список е теми же строками, но отсортированными в алфавитном порядке без учета регистра символов, где элементы с отступами рекурсивно отсортированы в пределах своего родительского элемента.
Результат работы функции показан на рис. 8.1, в списках Ье[оге (до сортировки) и а !те г (после сортировки). Пусть дан список Ьв[оге, тогда список а[1ег — результат вызова: а[!в г = 1пеепте011вт.[пеептве 11вт всгт(Ье[огв). По умолчанию в качестве отступа на один уровень используются четыре пробела, такой же отступ используется в строках списка Ьетоге, поэтому мы не будем явно указывать строку отступа при вызове функции. Рис. 8 1. До и посла сортировки списка.
содержащего строки с отступали Сначала мы рассмотрим функцию 1пеептее 11вт вогт() в целом, а за- тем перейдем к двум ее локальным функциям. оег 1поептео 11вт вогт([поел!во 1!вт, 1поепт=" "); КЕУ, 1ТЕМ, СН110ЯЕИ = гарса(З) Ьетога = ("Иопаата1в", нувгодап", Сагпоп", И!!годер", Охудеп", "1ппег тгапвптпопа1в", Кап!пап!сев". Сагпоа", Еогорпоа", Ас11ппсав", Огаптоа", Спг1оа", Р1птоппоа", "А1Ка1! Мета1в", 1!1П!оа", Воо!оа", Ротавюоа"] агтаг = [ "А1ка1! мата1в", 1!то!па", Ратавапоа", Вос1оа", "1ппаг тгапвпттопа1в", Асттп[аав", Согтоа", Р1отапппа", Огап!оа", 1аптнаппсав", Сегпоа", Еогортоа", "Иопаеса1в", Сагвоп", Нусгодеп", И]!годер", Охудеп" 1 411 Улучшенные приемы процедурного программирования бе( ааа епггу()ече1, Кеу, !!ев, сл!1бгеп): бег арба!а !паап!еб 1!а!(еп!гу); еп!г!еа = [] Гог !гев !и !пбепгеб 1!а(: 1ече1 = О ! = О веи1е !гев.
а!аггея!гп( !пбепк ! ): ! += 1еп(!паап!) 1ече1 += 1 Кеу = ггев.а!ыр(). 1овег() абб еп!гу( 1ече1, Кеу, !(ев, еп!г!еа) !пбеп!еб 1!а! = [] гог еп!гу дп аоггеб(епгг!еа): арбате !паепгеб 1!а!(епггу) ге!огп апбепгеб 1!а! Функция начинается с создания трех констант, которые будут служить именами индексов, используемых локальными функциями. Затем определяются две локальные функции, которые будут рассмотрены чуть позже. Работа алгоритма сортировки делится на две стадии. На первой стадии создается список элементов, каждый из которых представлен трехэлементным кортежем, содержащим «ключ», используемый при сортировке, оригинальную строку и список дочерних элементов со строками.
Ключ — это та же самая строка, в которой все символы приведены к нижнему регистру и удалены начальные и завершающие пробелы. В переменной 1ече1 хранится текущий уровень отступа, для элементов верхнего уровня это значение О, для элементов, дочерних по отношению к верхнему уровню это значение 1 и т. д.
На второй стадии создается новый список, куда добавляются строки из отсортированного списка элементов верхнего уровня, строки дочерних элементов и т. д, аег ааа епггуПече1, кеу, !гев, сп!!агап): !Г 1ече1 == О: огн1бгеп.аррепб((Кеу, !!ев, [])) е[ае: абб еп!гу(1ече1 — 1, Кеу, !!ев, сл!1бгеп[-1][СН1[ОНЕН]) Эта функция вызывается для каждой строки в списке. Аргумент сл !1- а геп — это список, куда должны добавляться новые элементы.
При вызове из внешней функции (1паеп!еа 1!в! зог!()) ей передается список еп! г!ев. Эта функция превращает список строк в список элементов, каждый из которых содержит строку верхнего уровня (без отступов) и (возможно, пустой) список дочерних элементов. На уровне О (на самом верхнем уровне) в список еп!г!ев добавляется новый кортеж из трех элементов. Он содержит ключ (для сортировки), Глава 8. Усовершенствованные приемы программирования оригинальный элемент (который будет перемещен в список с результатами) и пустой список дочерних записей.
Это базовый случай, так как здесь рекурсия не возникает. На других уровнях элемент [сев является дочерним по отношению к последнему элементу в списке сят1бгеп. В этом случае функция рекурсивно вызывает саму себя, уменьшая уровень на 1 и передавая дочерний список последнего элемента в списке ся11б геп. На уровне 2 и выше выполняется несколько рекурсивных вызовов, пока наконец не будет достигнут уровень О и не будет получен нужный список для добавления элемента. Например, когда дело доходит до строки «1ппег Тгапэ[1[опа]э», внешняя функция вызывает функцию збб ептгу() со значением О в аргументе 1еуе1, с ключом «[ппег СгапвН1опа!э», с элементом «1ппег ТгапэНЫ- па1э» и списком еж г[ез в качестве списка дочерних записей.
Поскольку текущим является уровень О, новый элемент просто добавляется в список дочерних элементов (ептг1ез) с указанным ключом, элементом и пустым списком дочерних элементов. Следующая строка— 1.ап1йапЫез»; имеется отступ, следовательно, эта строка — дочерняя для строки «1ппег Тгапэ[1[опа1э». Функция збб ептгу() вызывается со значением 1 в аргументе 1еуе1, с ключом «1ап1йапЫеэ», с элементом «1 ап1]тапЫеэ» и списком ептг[ез в качестве списка дочерних записей. Так как текущим является уровень 1, функция збб ептгу() рекурсивно вызовет саму себя со значением О (1 — 1) в аргументе 1еуе1, с тем же самым ключом и элементом и со списком дочерних элементов, принадлежащим последнему элементу, то есть со списком дочерних элементов для элемента «1ппег ТгапэН1опа1э».
[('попаета1з', 'Мопаета1з', [('Пубгоцеп', ' Нубгоцеп', []), ('сагооп', ' Сагооп', []), ('пттгоцеп', ' яттгодеп', []), ('охуцеп', ' Охуцеп', [])]), ('тппег тгапэ1(топа1я', '1ппег тгапп(т(опа1э', [('1агтпап1беэ', (оп(пап(без', [('сег1ов', ('еогортоа', ('ао(1п1без', Асттп(без', [('огаптоа', ('сог1ив', ( 91отопша' ('а1ха1т вета1з', 'А1ха1т нета1з', [('1ттл1ив', ' Ытлтов', []), Сег1ов', []). Еогортов', [])]), цгаптоа', []) Сог1иа', []), Р1«топ!оа', [])])]), Ниже показано, как выглядит список ептг[еэ после добавления всех строк, но перед сортировкой: Улучшенные приемы процедурного программирования 413 ('воо1па', ' еоо!оа , []), ('росаввгша', ' Росавв1оа', [])])] Вывод списка был произведен с помощью функции рргспС.
ррг[пС() из модуля ррг1пС (»ргеССу рг[пС» — модуль функций форматированного вывода). Обратите внимание, что список епсгсев содержит всего три элемента (каждый из которых представлен трехзлементным кортежем) и в каждом из них последний элемент кортежа является списком дочерних трехзлементных кортежей (или пустым списком). Функция авс епсгу() одновременно является и локальной и рекурсивной функцией. Подобно любой рекурсивной функции в ней предусматривается базовый случай действий (в этой функции он выполняется, когда текущим является уровень О), завершающий рекурсию, и рекурсивный случай. Эту функцию можно определить немного иначе: сег асс епсгу(неу, 1сеа, спс1огеп): поп1оса! 1ече1 сс 1ече1 == 0: спс1сгеп.аррепо((кеу, ыеа, [])) е[ве. 1ече1 -= 1 асс епсгу(меу, ссеа, см1огеп[- 1](сн![Олен]) Здесь вместо того чтобы передавать значение 1ече1 в качестве параметра, используется инструкция поп1оса1, которая обеспечивает доступ к переменной в объемлющей области видимости.
Если бы функция не изменяла переменную 1ече1, то инструкция поп1оса1 была бы не нужна, так как в этом случае интерпретатор, не обнаружив ее в локальной области видимости (во внутренней функции), продолжил бы поиски в объемлющей области видимости, где и нашел бы эту переменную. Но в этой версии функции асс епСгу() предусматривается изменение значения переменной 1ече1. Ранее мы использовали инструкцию О1ОЬа1, чтобы сообщить интерпретатору, что подразумевается изменение глобальной переменной (чтобы предотвратить создание новой локальной переменной вместо изменения существующей глобальной переменной); это относится ко всем переменным, которые требуется изменить и которые находятся в одной из внешних областей видимости. Если в большинстве случаев использования инструкции О1ОЬа1 лучше просто избегать, то к использованию инструкции поп1оса1 следует относиться по крайней мере с осторожностью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
