Array Array - Язык программирования Python

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 []

lst.append(val)

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 как числа, строки или списки. Это означает, что их можно передавать в качестве параметров функций или возвращать из функций.

Функции, принимающие в качестве аргументов или возвращающие другие функции в результате, называют функциями высшего порядка. В Python функции высшего порядка применяются программистами достаточно часто. В большинстве случаев таким образом строится механизм обратных вызовов (callbacks), но встречаются и другие варианты. Например, алгоритм поиска может вызывать переданную ему функцию для каждого найденного объекта.

Функция 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 range(1, 10, 3)

[1, 4, 7]

Функция xrange() - аналог range(), более предпочтительный для использования при последовательном доступе, например, в цикле for или с итераторами. Она возвращает специальный xrange–объект, который ведет себя почти как список, порождаемый range(), но не хранит в памяти все выдаваемые элементы.

Функция map()

Для применения некоторой функции ко всем элементам последовательности применяется функция map(f, *args). Первый параметр этой функции — функция, которая будет применяться ко всем элементам последовательности. Каждый следующий n+1–й параметр должен быть последовательностью, так как каждый его элемент будет использован в качестве n–го параметра при вызове функции f(). Результатом будет список, составленный из результатов выполнения этой функции.

В следующем примере складываются значения из двух списков:

Листинг

>>> l1 = [2, 7, 5, 3]

>>> l2 = [-2, 1, 0, 4]

>>> print map(lambda x, y: x+y, l1, l2)

[0, 8, 5, 7]

В этом примере применена безымянная функция для получения суммы двух операндов ко всем элементам l1 и l2. В случае если одна из последовательностей короче другой, вместо соответствующего операнда будет None, что, конечно, собьет операцию сложения. В зависимости от решаемой задачи, можно либо видоизменить функцию, либо считать разные по длине последовательности ошибкой, которую нужно обрабатывать как отдельную ветвь алгоритма.

Частный случай применения map() - использование None в качестве первого аргумента. В этом случае просто формируется список кортежей из элементов исходных последовательностей:

Листинг

>>> l1 = [2, 7, 5, 3]

>>> l2 = [-2, 1, 0, 4]

>>> print map(None, l1, l2)

[(2, — 2), (7, 1), (5, 0), (3, 4)]

Функция filter()

Другой часто встречающейся операцией является фильтрование исходной последовательности в соответствии с некоторым предикатом (условием). Функция filter(f, seq) принимает два аргумента: функцию с условием и последовательность, из которой берутся значения. В результирующую последовательность попадут только те значения из исходной, для которой f() возвратит истину. Если в качестве f задано значение None, результирующая последовательность будет состоять из тех значений исходной, которые имеют истинностное значение True.