Применяет функцию ко всем элементам списка. Наиболее известная конструкция для массовых операций над списками. Пример – извлечение первых элементов из вложенных списков A:
L=list(map(lambda x:x[0],A))
Lambda-функция
lambda x:x[0]
извлекает первый элемент из списка. Она применяется ко всем элементам списка A (которые тоже являются списками). Особенностью операции map в Pythonявляется то, что результат её не является списком, а, в соответствии с принципом "ленивых" вычислений, является некой условной конструкцией "map(…)". Чтобы заставить интерпретатор выполнить операцию до конца и выдать результат в виде списка, используем операцию приведения типов list(…).
Поскольку первым аргументом инструкции map является функция, для него удобно использовать lambda -функции вместо стандартной инструкции def, которую нужно объявлять заранее.
Возможно применение mapбез lambda -функции:
print (list(map(float,'2222!3333!0.1'.split('!'))))
Здесь мы разбиваем строку таблицы на цифры и преобразуем строковые переменные в вещественные числа с помощью стандартной функции приведения типов float.
Пример примененияmapпри построении графика зависимости, заданной двумерным массивом. В соответствии с требованиями библиотеки matplotlib операции plot необходимо предоставить два списка с координатами точек Xи Y. С помощью операции, описанной выше, извлекаем сначала первый столбец, потом – второй:
plt.plot(list(map(lambda x:x[0],A)),list(map(lambda x:x[1],A)))
Нужно отметить, что данная операция более красиво записывается с помощью расширенных возможностей срезов массивов библиотеки numpy (подробнее см. далее):
a=np.array(A)
plt.plot(a[:,0],a[:,1])
Альтернативой инструкции mapявляются обычные конструкции на основе циклов, генераторы списков и массовые операции над массивами библиотеки numpy. Нужно отметить, что последние записываются наиболее лаконично и естественно.
Рекурсия
Рекурсия — это такой способ организации подпрограммы, при котором эта подпрограмма в ходе выполнения вызывает сама себя.
Правильнее сказать, что подпрограмма вызывает свою копию, сохраняя свои данные в стеке. Поскольку глубина стека ограничена, многократная рекурсия может вызвать ошибку переполнения стека. Вообще рекурсия увеличивает количество действий для достижения результата, увеличивает объём используемой памяти и особенно резко ограничивает возможности решения задачи по глубине рекурсии. Тем не менее, рекурсивные алгоритмы бывают настолько удобными, простыми и гибкими, что рекурсия довольно часто находит применение в программировании.
Подход к организации подпрограммы с использованием рекурсии напоминает метод математической индукции.
Имеем объект, действие над которым можно представить как последовательность элементарных действий. Мы должны записать элементарное действие над объектом и возвратить результат в виде изменённого объекта, который передаётся на следующий шаг рекурсии. Кроме того, мы должны прописать условие, по которому функция просто возвращает результат – условие окончания рекурсии. Если это условие не выполняется, функция вызывает свою копию над изменённым объектом. Более того, можно вызвать несколько копий.
Например, нам нужно просмотреть дерево каталогов и найти файлы по какому-то признаку. Элементарная функция получает ссылку на каталог и перечень уже найденных файлов и возвращает перечень найденных файлов, включая те, что найдены в каталоге. Если она при просмотре каталога находит вложенные каталоги, то она применяет к каждому из них свою копию, включая найденные этими функциями файлы в свой результат. Если вложенных каталогов нет, то она просто возвращает как результат найденные файлы, не вызывая свои копии, и рекурсия далее не продолжается.
Как показано в примере выше, рекурсия – эффективный способ работы с древовидными структурами данных.
Хрестоматийный пример рекурсии– построение ряда чисел Фибоначчи. (Описание позаимствовано из [2])
Леонардо Фибоначчи (Леонардо Пизанский) – крупный средневековый итальянский математик (1170-1240), автор «Книги об абаке» (1202), которая несколько веков оставалась основным сборником сведений об арифметике и алгебре. Сегодня имя Фибоначчи чаще всего упоминается в связи с числовой последовательностью, которую он обнаружил, изучая закономерности живой природы. Ряд этих чисел образуется следующими значениями 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 и так далее – каждое последующее число ряда получается сложением двух предыдущих.
Особенностью ряда чисел Фибоначчи является то, что по мере роста номера числа в последовательности, отношение предшествующего члена к последующему приближается к значению – 0.618 (древние греки называли это число «золотым сечением»), а последующего к предыдущему – к 1.618. «Золотым» это соотношение называют из-за того, что на нем же основан принцип музыкальной, цветовой и геометрической гармонии.
Давайте напишем функцию, рассчитывающую n-й элемент ряда Фибоначчи. Итак, мы имеем обобщенную формулу: f 1 = f 2 =1, f n= f n−1+ f n−2,n∈ℕ. Можем ли мы применить здесь рекурсию? Каждое число Фибоначчи представляет собой сумму двух предыдущих чисел Фибоначчи, которые рассчитываются по той же формуле fn=f n−1+f n−2, условие прекращения рекурсии – достижение начальных значений f 1 = f 2 =1, так что применить рекурсию в данном случае вполне можно:
def fibonacci(n):
if n == 1 or n == 2:
return 1
return fibonacci(n-1) + fibonacci(n-2)
Результат выражения
print (fibonacci(7))
равен 13, что соответствует ряду чисел Фибоначчи.
Ниже рассмотрим реализацию сортировки по методу пузырька с помощью рекурсии.
import random
L=[random.randrange(100) for i in range(1,20)]# Генерируем случайный список
print (L)
def mysort(L):
for i in range(0,len(L)-1):# Перебираем пары элементов
if L[i]>L[i+1]: # если в паре элементов порядок нарушен,
L=L[:i]+[L[i+1],L[i]]+L[i+2:] # то меняем местами
return mysort(L) # и вызываем функцию mysort(L), чтобы
# выполнить следующий поиск и перестановку
return L #если пары менять не пришлось, возвращаем список неизменным, функцию mysort(L) не вызываем - рекурсия закончена
print (mysort(L)) # используем функцию сортировки mysort(L)
Пример отличает очень простой и короткий код. Недостаток – предельное количество сортируемых элементов – не более 80… Сказывается ограничение по глубине рекурсии.
Ещё пример из области фрактальной геометрии, где рекурсивный по сути алгоритм реализован без применения рекурсивного вызова функций (чтобы не ограничиваться из-за объёма памяти):
"""
Дракон Хартера — Хейтуэя
(см. http://elementy.ru/posters/fractals/dragon)
Опубликовано на условиях свободной лицензии GNU General Public License
(с) Андрей Столяров, 2015 г.
"""
import matplotlib.pyplot as plt # Подключаем библиотеку matplotlib.pyplot и даём ей псевдоним pll
import numpy as np
A=[[0,0],[1,1],[2,0]] # Исходныйэлемент
for k in range(0,18): # Цикл по этапам измельчения
for i in range(0,len(A)-1): # Цикл по элементам, в котором каждый элемент
# разбиваетсянаподэлементы
A.insert(i*2+1,[0.5*A[i*2][0]+0.5*A[i*2+1][0]-(i%2-0.5)*(A[i*2][1]-A[i*2+1][1]),
0.5*A[i*2][1]+0.5*A[i*2+1][1]+(i%2-0.5)*(A[i*2][0]-A[i*2+1][0])])
plt.plot(list(map(lambda x:x[0],A)),list(map(lambda x:x[1],A)))# Отрисовываем
plt.show()
Дано: исходный элемент
Каждую нечётную линию заменяем двумя линиями, которые являются катетами прямоугольного равностороннего треугольника с вершиной слева, а чётную – с вершиной справа.
1-й шаг:
2-й шаг:
18-й шаг:
Отладка программ
Отладка программ в Python имеет ряд особенностей.
Поскольку программа выполняется в консоли, после её завершения в памяти сохраняются переменные и функции, определённые в программе. При необходимости их можно вызвать через консоль.
