Инструкция map для массовыхопераций над списками

Применяет функцию ко всем элементам списка. Наиболее известная конструкция для массовых операций над списками. Пример – извлечение первых элементов из вложенных списков 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 ₁ = f ₂ =1, f _n= f _n−1+ f _n−2,n∈ℕ. Можем ли мы применить здесь рекурсию? Каждое число Фибоначчи представляет собой сумму двух предыдущих чисел Фибоначчи, которые рассчитываются по той же формуле f_n=f _n−1+f _n−2, условие прекращения рекурсии – достижение начальных значений f ₁ = f ₂ =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 имеет ряд особенностей.

Поскольку программа выполняется в консоли, после её завершения в памяти сохраняются переменные и функции, определённые в программе. При необходимости их можно вызвать через консоль.