Файл: Тема Основы языка Python.pdf

65
Рис. 88. Эквивалентная запись
У лямбда-функции нет имени, и, следовательно, вызов её по имени невозможен. Пока единственным применением лямбда-функций для нас может служить их передача в качестве параметра в такие функции, как sort или map. Например, с помощью лямбда-функции мы можем вывести список квадратов всех чисел от 1 до 100 всего в одну строку (рис. 89).
Рис. 89. Пример использования лямбда-функции
В этой программе лямбда-функция принимает в качестве параметра число, а возвращает строковое представление его квадрата.
Вернемся к задаче сортировки точек по удаленности от начала координат. Эта задача также может быть решена с использованием лямбда- функции (рис. 90).
Рис. 90. Пример использования лямбда-функции

66
Лямбда-функция может принимать несколько параметров (тогда после слова lambda нужно записать их имена через запятую), однако при использовании их в sort или map обычно применяется один параметр.
В языке Питон функция также является объектом, и мы можем создать ссылку на объект типа функция. Например, две записи функции возведения в квадрат эквивалентны (рис. 91).
Рис. 91. Пример использования лямбда-функции
Такой подход позволяет переиспользовать лямбда-функции, но в подавляющем большинстве случаев стоит пользоваться стандартным объявлением функции – это упрощает чтение и отладку программы.
Именованные параметры и неопределенное число параметров
Мы уже много раз пользовались функциями, которые могут принимать
(или не принимать) именованные параметры. Например, это необязательные именованные или неименованные параметры sep и end для функции print или параметр key для метода sort и функции sorted.
Сейчас мы научимся создавать функции, которые принимают именованные параметры. Например, напишем функцию, печатающую что угодно итерируемое, состоящее из чего угодно приводимого к строке, с именованным параметром sep, по умолчанию равным пробелу (рис. 92).

67
Рис. 92. Пример использования функций
Именованный параметр в объявлении функции должен идти после основных параметров. В списке параметров записывается его имя, а затем значение по умолчанию (т. е. то значение, которое будет подставляться на место соответствующего параметра, если он не был передан при вызове функции).
Мы пользовались функциями, которые умеют принимать произвольное количество параметров. Например, в функцию print можно передать любое количество параметров. Можно написать собственные функции, которые будут принимать произвольное количество параметров. При этом параметры функции будут упакованы в список. Например, функция подсчета суммы всех переданных параметров может выглядеть так, как представлено на рис.
93.
Рис. 93. Пример использования функций
Функция принимает один параметр, перед которым написана звездочка. Это признак того, что аргументы будут упакованы в список.
Можно писать функции, которые принимают не менее определенного количества параметров. Например, мы можем написать функцию поиска минимума среди неопределенного числа аргументов, но в нее должно быть передано не менее одного аргумента (рис. 94).

68
Рис. 94. Пример использования функций
Параметр со звездочкой всегда должен быть последним, за исключением ситуации, когда в функции также определены именованные параметры.
Чтение до конца ввода
Во многих задачах заранее неизвестно, сколько данных нам предстоит считать. Особенно яркий пример – это обработка текста, когда мы заранее не знаем, сколько строк нам будет введено.
Наиболее удобно работать с такими данными, не пользуясь функцией input, используя методы чтения файла (или ввода с консоли) целиком или построчно.
Рассмотрим простой пример: считать все строки файла input.txt и вывести каждую строку развернутой в файл output.txt (рис. 95).
Рис. 95. Пример работы с файлами

69
Для открытия файла используется функция open, принимающая два параметра: имя файла и режим открытия (''r'' для чтения и ''w'' для записи), а также именованный параметр encoding (значение кодировки ''utf8'' подходит для большинства современных текстовых файлов). Эта функция возвращает ссылку на объект типа файл.
Для чтения всех строк из файла используется метод readlines, который возвращает список всех строк (в смысле lines) файла. Обратите внимание, что строки попадают в список вместе с символом перевода строки, в нашей программе это учитывается при создании среза (этот символ последний в строке). В тестирующей системе все входные файлы имеют перенос строки после последней строки, в реальной жизни это может оказаться не так, и тогда программа будет работать неверно.
Для печати в файл мы пользуемся стандартной функцией print, которой передается именованный параметр file с указанием, в какой файл печатать.
После окончания работы с файлами нужно вызвать для них методы close.
В этой задаче, на самом деле, можно было обойтись без запоминания всего файла в памяти (это особенно актуально для больших файлов).
Решение без запоминания всего файла можно было реализовать так, как представлено на рис. 96.
Рис. 96. Пример работы с файлами
Переменные типа файл являются iterable и умеют возвращать очередную строку из файла, не храня его целиком в памяти.

70
Также существует метод read, который позволяет считать все содержимое файла в одну строковую переменную (при этом содержащую в себе переводы строки \n).
В принципе читать до конца ввода можно и из консоли. Для этого нужно подключить библиотеку sys и использовать определенный в ней файловый дескриптор stdin в качестве файла (например, для перебора строк консоли можно написать for line in sys.stdin). Ввести признак конца файла в консоли можно, нажав Ctrl + Z в Windows или Ctrl + D в Unix-системах.
Еще об одном способе работы с файлами с помощью конструкции with
… as ..., что позволяет автоматически вызывать метод close(), можно почитать здесь: http://book.pythontips.com/en/latest/open_function.html
Сортировка подсчетом
В ряде задач возможные значения в сортируемом списке сильно ограничены. Например, если мы хотим отсортировать оценки от 0 до 10, то может оказаться эффективнее подсчитать, сколько раз встречалась каждая из оценок, и затем вывести её столько раз.
Реализация такого подхода очень проста (рис. 97).
Рис. 97. Сортировка подсчетом
В этой программе мы создали список, состоящий из 11 нулей в одну строку. Этот приём часто пригождается и в других задачах.
Связь задач поиска и сортировки

71
Во многих задачах линейного поиска (поиска минимального элемента, например) возникает соблазн воспользоваться сортировкой.
С этим соблазном следует бороться, т. к. сложность сортировки в языке
Питон составляет
O(NlogN
). Т. е. для сортировки списка из N элементов нужно совершить порядка NlogN действий.
При этом алгоритмы линейного поиска работают за
O(N
), что асимптотически быстрее, чем сортировка. Поэтому в задачах линейного поиска (даже для поиска третьего по величине элемента) следует реализовывать линейный поиск, а не пользоваться сортировкой.
Сортировка в интерпретаторе CPython может оказаться быстрее рукописного линейного поиска (из-за того, что она реализована максимально эффективно и на языке Си
). Но это досадное недоразумение не должно побороть в вас желание писать линейный поиск руками.
2.2. С
труктуры данных – множества и словари
Множества и хеш-функции
В языке Питон множества имеют тот же смысл, что и в математике.
Это набор объектов без определенного порядка. В множество можно добавлять и удалять объекты, проверять принадлежность объекта множества и перебирать все объекты множества.
Над множествами можно совершать групповые операции, например, пересекать и объединять два множества.
Проверка принадлежности элемента множеству, а также операции удаления и добавления элементов осуществляются за O(1) (если бы мы хранили элементы в списке и хотели бы проверить принадлежность элемента списку, то нам потребовалось бы O(N) операций, где N – длина списка).
Такая скорость достигается использованием хеш-таблиц. Хеш-таблица
– это массив достаточно большого размера (назовем этот размер K). Каждому

72 неизменяемому объекту можно сопоставить по некоторому правилу число M от 0 до K и поместить этот объект в ячейку списка с индексом M. Например, для целых чисел таким правилом сопоставления может быть просто подсчет остатка от деления целого числа на K. Операция взятия остатка будет нашей хеш-функцией.
Теперь, если нам нужно проверить, принадлежит ли некоторое число множеству, мы просто считаем хеш-функцию от него и проверяем, лежит ли наш объект в ячейке с индексом, равным результату вычисления хеш- функции, или нет. Для других типов данных можно применить такой подход: любой объект так или иначе является последовательностью байт. Будем интерпретировать эту последовательность байт как число и подсчитаем хеш- функцию для этого числа.
Может оказаться, что несколько объектов дают один и тот же хеш
(отображение между огромным множеством различных объектов и скромным размером множества допустимых хешей не может быть биективным).
Такие проблемы можно разрешить, не ухудшая асимптотическую сложность. Подробнее такие методы изучаются в курсе алгоритмов.
Поскольку числа могут быть достаточно длинными, операция подсчета хеш-функции при каждой операции с этим объектом в множестве может быть очень медленной. Поэтому каждый неизменяемый объект в Питоне имеет заранее насчитанный хеш, который подсчитывается один раз при его создании. Кстати, с помощью этих же хешей можно понимать, есть ли уже объект в памяти, и не создавать новых объектов, а просто подвешивать еще одну ссылку на уже существующий объект.
Изменяемые типы, такие как список, не имеют заранее насчитанных хешей. Изменение всего одного элемента в списке привело бы к полному пересчету хеша для всего списка, что катастрофически замедлило бы работу со списками. Поэтому у изменяемых объектов нет хеша, и они не могут быть добавлены в множество.

73
Само множество также является изменяемым объектом и не может быть, например, элементом другого множества.
Существуют также неизменяемые множества, которые создаются с помощью функции frozenset.

74
Рис. 100. Пример работы с множествами
Вывод этой программы такой:
{1, 2, 3}
{4, 5, 6}
{'l', 'o'}
{2, 5, 8, 11, 14, 17, 20}
{1, 2, 3, 4}
{1, 2, 3}
Множество также является итерируемым объектом (еще раз: объекты идут в случайном порядке, не по возрастанию!).
Множество может содержать в себе объекты разных типов (рис. 101).
Рис. 101. Пример работы с множествами
По аналогии со строками, списками и кортежами, количество элементов в множестве можно узнать с помощью функции len.
Из множества можно сделать список или кортеж с помощью функций list и tuple соответственно. Применение функции str к множеству даст нам

75 текстовое представление (элементы в фигурных скобках, разделенные запятыми).
Частой операцией является вывод упорядоченных элементов множества. Это можно сделать, применив функцию sorted сразу к множеству
(ведь оно итерируемо) (рис. 102).
Рис. 102. Пример работы с множествами
Вывод этой программы будет: long string, a, abba a, abba, long string
К множеству можно применять функцию map.
Работа с множествами
Работа с элементами множеств
Чтобы создать пустое множество, нужно воспользоваться кодом, показанным на рисунке 103.
Рис. 103. Пример работы с множествами
Писать пустые фигурные скобки нельзя (во второй части лекции узнаем почему).
Добавление элемента в множество осуществляется с помощью метода add. Если элемент уже был в множестве, то оно не изменится.
Перебрать элементы множества можно с помощью for (for умеет ходить по любым итерируемым объектам) (рис. 104).

76
Рис. 104. Пример работы с множествами
Вывод такой программы будет «1 1 2 2», но упорядоченность является чистой случайностью.
Чтобы проверить, входит ли элемент X в множество A, достаточно написать X in A. Результатом этой операции будет True или False. Чтобы проверить, что элемент не лежит в множестве, можно писать not X in A или, логичнее, X not in A (рис. 105).
Рис. 105. Пример работы с множествами
Вывод этой программы будет:
1 in set x not in set
Чтобы удалить элемент из множества, можно воспользоваться одним из двух методов: discard или remove. Если удаляемого элемента в множестве не было, то discard не изменит состояния множества, а remove выпадет с ошибкой.
Групповые операции над множествами