Вводное занятие

В это семестре курс будет проходить в несколько другом формате, сродни тому формату, в котором обычно проводят спецсеминары: я подготовил для вас список тем занятий, каждый из вас должен выбрать себе какую-нибудь тему и сделать по ней доклад. Список тем находится тут. Если у вас есть какие-то темы, которые вы очень хотите освоить, но не было повода, предлагайте их!

Ещё, так как этот семестр сильно короче осеннего, да и достаточные знания питона у вас уже есть, то к следующему занятию вам нужно придумать темы для зачётных заданий и к концу следующего занятия распределиться по группам и темам.

Первые несколько занятий этого курса будут по теме, которая очень нравится в питоне мне, хотя я отнюдь не уверен, что понравится вам. (Ну да это так же, как и во всех курсах всегда). Тема эта – функциональное программирование в питоне. Если сильно упрощать, то основная идея функционального программирования состоит в том, чтобы писать программу в виде большого количества однострочных функций и почти для всего использовать списки. (А вместо циклов всегда использовать рекурсию).

Вспоминаем слайсы

Простая проверка, все ли помнят, что это такое, и что, например, у них обозначает третий аргумент:

   1 >>> list = range(20)
   2 >>> list[1:2:3]
   3 [1]
   4 >>> list[1:8:3]
   5 [1, 4, 7]

И двойственная к слайсам функция range:

   1 >>> range(1, 8, 3)
   2 [1, 4, 7]

Мутирующие и не мутирующие список функции

И когда вы сами пишете функцию, которая что-нибудь делает со списком, и когда вы пользуетесь существующими функциями, всегда полезно знать, меняет эта функция существующий список, или возвращает новый.

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

Разворот списка:

   1 >>> els = range(5) # els -- сокращение от elements
   2 >>> els.reverse()
   3 >>> els
   4 [4, 3, 2, 1, 0]
   5 >>> list(reversed(els)) # reversed возвращает не совсем список,
   6 ... # для наглядности я превращаю его в список явно
   7 [0, 1, 2, 3, 4]
   8 >>> els
   9 [4, 3, 2, 1, 0]

Сортировка:

   1 >>> list = [4, 6, 2, 1]
   2 >>> sorted(list)
   3 [1, 2, 4, 6]
   4 >>> list
   5 [4, 6, 2, 1]
   6 >>> list.sort()
   7 >>> list
   8 [1, 2, 4, 6]

Добавление элемента в конец:

   1 >>> list = [1, 2, 3]
   2 >>> list + [4]
   3 [1, 2, 3, 4]
   4 >>> list
   5 [1, 2, 3]
   6 >>> list.append(4)
   7 >>> list
   8 [1, 2, 3, 4]
   9 >>> list += [5]
  10 >>> list
  11 [1, 2, 3, 4, 5]

И в начало:

   1 >>> list = [4, 5, 6]
   2 >>> [3] + list
   3 [3, 4, 5, 6]
   4 >>> list
   5 [4, 5, 6]
   6 >>> list.insert(0, 3)
   7 >>> list
   8 [3, 4, 5, 6]

Дабы ошибки на этом месте всплывали достаточно скоро, в питоне принято, чтобы функция, меняющая список, всегда возвращала None. Многие из вас уже писали строки вида x = x.append(y), и получали из этого ошибки.

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

Списки туплей

Теперь рассмотрим простую задачку: нам нужно прочитать файл и распечатать его вместе с номерами строк.

Первый подход, как мы это можем сделать:

   1 def enum_lines(file):
   2         i = 1
   3         for line in file:
   4                 print i, line
   5                 i += 1

Для файла из 10 строк это выдаст нам некрасивое:

1  a
2  b
3  c
4  d
5  e
6  f
7  g
8  h
9  i
10  j

Последняя строка съехала потому, что число цифр в номере строки изменилось. Давайте сделаем простенький грязный хак, чтобы это исправить: предположим, что строк у нас вряд ли будет больше 10000, а если и будет, то там уже никто такого сползания не заметит:

   1 def enum_lines(file):
   2         i = 1
   3         for line in file:
   4                 print("%5d %s" % (i, line))
   5                 i += 1

Для тех, кто забыл, как устроено форматирование строка % значения, даю полезную ссылку: docs.python.org -> Library reference -> sequence types -> formatting operations¹

Можно было бы подсчёт необходимой ширины поля для номера строки сделать и поумнее (для этого сначала прочитать весь файл и посчитать в нём количество переносов строк, посчитать количество символов, нужное для записи этого числа, и отводить под номер каждой строки ровно столько символов) – но это не то, о чём я сейчас хочу рассказать.

Я хочу обратить ваше внимание на то, что мы в этой задаче на самом деле хотим как бы идти параллельно по двум спискам – списку номеров строк и списку значений строк.

Для этой задачи в питоне есть встроенная функция: zip

   1 >>> zip([1, 2, 3], [4, 5, 6, 7])
   2 [(1, 4), (2, 5), (3, 6)]
   3 >>> zip([1, 2], [3, 4], [5, 6])
   4 [(1, 3, 5), (2, 4, 6)]

Функция zip получает на вход несколько списков и возвращает список туплей: [(первый элемент каждого списка), (второй элемент каждого списка) ...] Название функции происходит от слова zipper, застёжка-молния, – и по-моему, это весьма образное название.

В первом примере видно, что если в одном из списков значения кончились раньше, то ровно на этом месте функция zip и остановится. (В первом примере в ответе этой функции не оказалось значения 7 вовсе). Это традиционное поведение такой функции во всех языках, где она есть (по крайней мере, в тех, где я это проверял).

С функцией zip мы можем попытаться сочинить не элегантное и жрущее много памяти, но всё же работоспособное решение нашей задачи:

   1 def enum_lines(file):
   2         for num, line in zip(range(len(list(file))), file):
   3                 print("%5d %s" % (num + 1, line))

Сказать len(file) чтобы посчитать строки файла в питоне нельзя (пока что не буду углубляться в подробности, почему так), поэтому сначала мы превращаем файл в список строк файла: list(file), потом считаем длину этого списка: len(list(file)), потом создаём список чисел от 0 до длины файла - 1: range(len(list(file))), и склеиваем попарно элементы этого списка со строками файла. Так как строки мы начали считать с нуля (чтобы не перегружать и без того загруженную первую строку функции), а выводить номера строк мы хотим по-человечески с единицы, то мы прибавляем 1 к номеру строки, когда его выводим.

Кажется, именно такое применение функции zip – один из самых частых типов потребности в ней. Поэтому именно на этот случай есть специальная функция: enumerate.

Ведёт она себя так²:

   1 >>> list(enumerate(["a", "b", "c"]))
   2 [(0, "a"), (1, "b"), (2, "c")]

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

   1 def enum_lines(file):
   2         for num, line in enumerate(file):
   3                 print("%5s %s" % (num + 1, line))

В конце концов мы получили красивую чистую читаемую функцию в две строки, которая делает то же самое.

dict

Спискам пар есть ещё одно очень полезное применение в питоне: такие списки легко превращаются в словари. Если конструктору типа dict в качестве аргумента дать список пар, то он превратит его в словарь, отображающий первый элемент каждой пары на второй.

Например, если у нас в файле есть две интересующие нас строки – с именами полей и с их значениями, – то превратить такой файл в словарь очень легко:

   1 def read_two_lines(file):
   2         keys = file.readline().split()
   3         values = file.readline().split()
   4         return dict(zip(keys, values))

Подобные случаи – основная область применения функции zip.

Логические функции для работы со списками

Нужны бывают крайне редко, но экономят три строки кода (а следовательно, зачастую делают код более читаемым): функции all и any.

Функция all проверяет, что все элементы списка являются истинными, функция any – что хотя бы один.

   1 >>> all([True, False, True])
   2 False
   3 >>> all([True, True, True])
   4 True
   5 >>> any([True, False, True])
   6 True
   7 >>> any([False, False, False])
   8 False

Что есть истина, что есть ложь

На самом деле, эти функции более широко применимы, потому, что в качестве истинных и ложных значений в питоне можно использовать не только True и False.

По древней традиции в питоне принято всё "пустое" или "нулевое" воспринимать как ложное значение, а всё остальное как истинное.

То есть мы можем написать:

   1 >>> if 1:
   2 ...     print "Yes"
   3 ... else:
   4 ...     print "No"
   5 Yes
   6 >>> if []:
   7 ...     print "Yes"
   8 ... else:
   9 ...     print "No"
  10 No
  11 >>> bool('')
  12 False
  13 >>> bool('hello')
  14 True
  15 >>> bool(-0.0)
  16 False
  17 >>> bool(0.0000001)
  18 True

И раз уж мы заговорили об истинном лице логических значений, посмотрим и на истинное лицо логических операций:

   1 >>> 1 and 2
   2 2
   3 >>> '' and "hello"
   4 ''
   5 >>> 1 or 2
   6 1
   7 >>> '' or "hello"
   8 'hello'

На самом деле, логические операции возвращают не истину или ложь, а первое значение, которое однозначно определяет их ответ! Более того, если операция определилась с ответом на первом аргументе, она не будет даже пытаться вычислять второй аргумент! Это очень важное свойство называется ленивым вычислением аргументов.

   1 >>> 1/0 and 2
   2 Traceback (most recent call last):
   3 ...
   4 ZeroDivisionError: integer division or modulo by zero
   5 >>> 0 and 1/0
   6 0

Из всего, сказанного в этом разделе, можно сделать два вывода:

Во-первых, можно писать, например, так:

   1 if line != '' and line[0] == 'x':
   2     ...

– такая конструкция будет работать.

Но если поменять проверки местами, она перестанет работать:

   1 if line[0] == 'x' and line != '':
   2     ...

– в случае, если значение line – пустая строка, то программа в этом месте свалится.

Во-вторых,

   1 if is_line_good(line):
   2         print("A")
   3 if is_line_good(line) == True:
   4         print("B")
   5 if bool(is_line_good(line)) == True:
   6         print("C")

– из этих трёх конструкций эквивалентны первая и третья. Вторую конструкцию не стоит писать ни в коем случае, если только вы не имели в виду именно то, что там и написано.

В первой конструкции написано: если строка хорошая – напечатать "A".

Во второй конструкции написано: если проверка хорошести строки вернула значение True и ничто другое – напечатать "B".

В третьей конструкции написано: если истинность зачения, которое вернула проверка хорошести строки, является True – напечатать "C".

Если вы не очень поняли, что здесь происходит, то вот простое правило: никогда не пишите буквосочетаний == True, != True, == False, != False

В заключение добавлю, что в отличие от and и or, any и all всегда возвращают True или False (что лично меня удивляет и несколько огорчает; неприятно в таком месте видеть такую неконсистентность).

List comprehensions

Эта на самом деле небольшая и несложная, но очень выразительная штука в питоне начала зарождаться очень давно. Где-то в начале-середине прошлго века сначала Эрнст Фрэнкель, а потом и Адольф Авраам Халеви Цермело занимались сочинением аксиоматики теории множеств и одна из их аксиом звучала так: если S – множество и p – предикат (т.е. функция, которая возвращает либо истину, либо ложь), то { x | x ∈ S, p(x) } – это тоже множество. Эту аксиому назвали аксиомой выделения, а по-английски the Axiom of Comprehension.

Собственно, возможность писать такие конструкции { x | x ∈ S, p(x) } определяется в значительной степени этой аксиомой, поэтому эту нотацию стали называть (в некоторых узких областях математики) set comprehensions. А по-русски никак её не называют.

Эта нотация множеств вдохновила авторов функциональных языков программирования сотворить подобную ей нотацию в своих языках. В функциональных языках эта нотация использовалась для преобразований списков, поэтому её стали называть list comprehensions. Одно из наиболее ярких последних творений на эту тему было в языке haskell, откуда, по его собственным словам, Гвидо и позаимствовал эту идею для питона³.

Из всей этой печальной истории можно сделать такой вывод: по-русски list comprehensions можно называть разве что выделениями списков ⁴

Хватит трепаться, переходим к делу.

Итак, в питоне можно писать такое: [ выражение for переменная in список ] и значить это будет следующее: для каждого элемента списка, указать на него этой переменной и вычислить в этом контексте выражение, собрать все результаты таких вычислений и положить снова в список.

   1 >>> [ x ** 2 for x in [1, 2, 3]]
   2 [1, 4, 9]

Эта конструкция эквивалентна трём строкам питонского кода:

result = []
for x in [1, 2, 3]:
        result.append(x ** 2)

Знакомая конструкция, не правда ли? Теперь мы знаем, как это писать короче!

Сразу примеров применения.

Мы хотим разобрать csv файл, в котором записаны числа. Подход первый, самый старый:

   1 def parse_numbers(file):
   2         result = []
   3         for line in file:
   4                 numbers = []
   5                 for word in line.split(","):
   6                         numbers.append(int(word))
   7                 result.append(numbers)
   8         return result

Тут мы сразу видим, что внутренний цикл можно представить в виде "выделения списка":

   1 def parse_numbers(file):
   2         result = []
   3         for line in file:
   4                 numbers = [int(word) for word in line.split(",")]
   5                 result.append(numbers)
   6         return result

И снова упираемся в точно такую же конструкцию. Значит, и её можно свернуть:

   1 def parse_numbers(file):
   2         return [[int(word) for word in line.split(",")] for line in file]

Нельзя назвать эту запись самой очевидной, но зато она короче исходной в 4 раза (или вообще в 7 раз, смотря как считать).

Ещё один пример, связанный с разбором форматов. Предположим, мы хотим разобрать строку, в которой записан список присваиваний значений ключ=значение (и мы сразу требуем, чтобы внутри значений не было пробелов, и если значения повторяются, то мы будем использовать последнее). И, разумеется, мы хотим такую строку превратить в словарь.

Что может быть проще!

def parse_keys(line):
        return dict([word.split('=', 1) for word in line.split()])

line.split() – превратили строку в список слов. word.split("=", 1) – разбили слово по первому вхождению "=" (если никакого равенства в слове нет, нам вернётся список из одного элемента, и это вызовет ошибку, что хорошо; если есть больше одного равенства, то мы предполагаем, что второе равенство – это часть текста значения; split(..., 1) возвращает список длины не более 2). Полученный список (списков длины 2) превращаем в словарь и возвращаем.

Второе частое применетие "выделений списков" – для форматирования вывода. Например, ровно обратная операция:

   1 def format_numbers(lines):
   2         ''.join([','.join([str(number) for number in line]) for line in lines]

В начале прошлого семестра была задача: сгенерировать пустое шахматное поле. (Шахматное поле обозначалось как список строк, строка как список клеток, а клетка как значение в ней – строка – или None, если пусто). Саша Гришин прислал мне на эту задачу примерно такое решение:

   1 def field(n_columns, n_rows):
   2         return [[None]*n_columns for _ in range(n_rows)]

Следюущий элемент сложности, который мы можем внести в list comprehensions: мы можем ходить не по одному списку, а по нескольким. Это будет эквивалентно нескольким вложенным циклам. Пример:

   1 >>> [a + str(b) for a in ["a", "b"] for b in range(3)]
   2 ['a0', 'a1', 'a2', 'b0', 'b1', 'b2']

То есть эта конструкция эквивалентна четырём строкам:

   1 result = []
   2 for a in ["a", "b"]:
   3         for b in range(3):
   4                 result.append(a + str(b))

Способ запомнить, в каком порядке случается обход: если в list comprehension воткнуть переносов строк, отступов и двоеточий, и убрать немного лишнего, то получатся вложенные циклы, обходящие списки ровно в том же порядке. Иными словами: первый for внешний (меняется реже всего), внутри него второй for (пробегает все значения для каждой итерации первого), внутри него третий, и так далее.

Наконец, в list comprehensions есть и ещё одна вещь, которую можно вставлять: проверки. Синтаксис столь же простой, как и раньше:

   1 >>> [x for x in range(20) if random.random() > 0.5]
   2 [3, 4, 7, 10, 12, 17]

Эквивалентно:

   1 result = []
   2 for x in range(20):
   3         if random.random() > 0.5:
   4                 result.append(x)

Надеюсь, в этом месте не нужно никаких больше пояснений.

Как и for, if'ы можно добавлять в любом количестве, и их можно чередовать. Эффект будет таким же, как ровно в той же последовательности записанные вложенные for'ы и if'ы. В более вложенных конструкциях можно использовать переменные, определённые в более внешних (т.е. раньше по тексту).

Ещё примеров!

Предположим, у нас есть csv файл, в котором записаны углы. При этом углов может быть записано разное количество (от одного до трёх), и записаны они в градусах (а вся тригонометрия в питоне работает с радианами). Хочется разобрать строку такого файла.⁵. Делается это гораздо проще, чем объясняется:

   1 [math.radians(float(word)) for word in line.split(",") if word]

Последнее условие более-менее эквивалентно проверке if word != "". Надеюсь, сейчас это достаточно очевидно. Читать такие проверки лучше всего так: если слово непусто.

А можно было это же записать длинее:

   1 angles = []
   2 for word in line.split(","):
   3         if word != "":
   4                 angles.append(math.radians(float(word)))

Вам выбирать, что из этих двух вариантов вам больше нравится.

Ещё один пример, оторванный от жизни совсем: составить список простых чисел меньше 200.

Самый наивный подход такой:

Сначала научимся проверять, просто ли данное число n:

   1 all([n % p != 0 for p in range(2,n)])

Дословный перевод на русский: [n простое, если] для каждого числа p от 2 до n, остаток от деления n на p не равен нулю.

А теперь осталось перебрать все n от 2 до 200 и проверить каждое из них:

   1 [n
   2         for n in range(2, 200)
   3         if all([n % p for p in range(2, n)])
   4 ]

Есть ещё один, ещё более медленный, но чрезвычайно забавный подход: сначала сгенерируем список всех составных чисел в нашем интервале, а затем выберем все оставшиеся.

   1 noprimes = [i * j for i in range(2, 200) for j in range(i, 200)]
   2 primes = [n for n in range(2, 200) if n not in noprimes]

О копировании

В завершении случайно свалившаяся плюшка: как копировать списки, словари и пр.

Во-первых, копировать имеет смысл только принципиально изменяемые значения. В питоне числа, строки, тупли, frozenset'ы, логические константы, None менять невозможно (если вам это удалось, напишите Гвидо, но это исправит в следующей версии), возможно только создавать новые из старых. Поэтому копировать эти объекты и смысла нет.

Во-вторых, когда вы берётесь что-нибудь копировать, определитесь с тем, что вы хотите копировать, а что нет. Как правило, если у вас возникла потребность сделать копию, например, списка, это значит, что вы хотите создать новый список той же длины и положить в него ссылки на те же элементы, которые лежат в исходном списке. Это называется "неглубоким" или "мелким" копированием (английский язык тут гораздо более точен: shallow copy). Если вы хотите копировать и сами объекты (и, может быть, их поля? или, если это списки, то, может быть, и их содержимое), то это называется "глубокой" копией (deep copy). Глубокое копирование – достаточно неблагодарное занятие, и почти всегда, если вам захотелось заняться глубоким копированием – это повод задуматься, а правильный ли вы изначально подход избрали, а нельзя ли всё сделать проще?

Ну а собственно способов копирования есть несколько.

Есть модуль copy, в котором есть функции copy (неглубокое копирование) и deep_copy (глубокое копирование). Так как я сам им никогда не пользовался, то и вам про него врать не буду.

Для неглубокого копирования в питоне есть правило: если мы какое-то значение скармливаем конструктору типа, то создаётся новый объект этого типа, а, следовательно, и неглубокая копия:

   1 >>> x = set([1, 2, 3])
   2 >>> y = set(x)
   3 >>> x.add(5)
   4 >>> y
   5 set([1, 2, 3])
   6 >>> x
   7 set([1, 2, 3, 5])
   8 
   9 >>> x = [1, 2, 3]
  10 >>> y = list(x)
  11 >>> x.append(5)
  12 >>> y
  13 [1, 2, 3]
  14 >>> x
  15 [1, 2, 3, 5]
  16 
  17 >>> x = {1: 2, 3: 4}
  18 >>> y = dict(x)
  19 >>> x[6]=4
  20 >>> y
  21 {1: 2, 3: 4}
  22 >>> x
  23 {1: 2, 3: 4, 6: 4}

И есть ещё один способ, почему-то наиболее популярный – использовать хитрые трюки:

   1 >>> x = [1, 2, 3]
   2 >>> y = x[:]
   3 >>> x.append(5)
   4 >>> y
   5 [1, 2, 3]
   6 >>> x
   7 [1, 2, 3, 5]
   8 
   9 >>> x = {1: 2, 3: 4}
  10 >>> y = {}
  11 >>> y.update(x)
  12 >>> x[4] = 3
  13 >>> y
  14 {1: 2, 3: 4}
  15 >>> x
  16 {1: 2, 4: 3, 3: 4}