Модули. Словари. Кортежи.

Разбор домашних задач

Напишите программу, которая выводит на экран песенку про бутылки с использованием format.

Берём любую из прежних реализаций песенки и заменяем запятые в print на соответствующее использование format (хоть прямо из прошлого конспекта):

   1 print "99 bottles of beer on the wall, 99 bottles of beer,"
   2 for bottles_left in reversed(range(100)):
   3   if bottles_left == 0:
   4     bottles = "no more bottles"
   5   elif bottles_left == 1:
   6     bottles = "1 bottle"
   7   else:
   8     bottles = "{} bottles".format(bottles_left)
   9   print "Take one down, pass it around, {} of beer on the wall".format(bottles)
  10   print ""
  11   print "{} of beer on the wall, {} of beer".format(bottles, bottles)
  12 print "Go to the store and buy some more, 99 bottles of beer on the wall".

Напишите функцию token_type(token), которая получает на вход токен, и возвращает слово, описывающее его тип.

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

   1 def token_type(token):
   2   if token.isalpha():
   3     if token.isupper():
   4       return "upper"
   5     if token.islower():
   6       return "lower"
   7     if token.istitle():
   8       return "title"
   9     return "mixed"
  10   else:
  11     if token.isalnum():
  12       return "alnum"
  13     else:
  14       return "other"
  15 
  16 print u"Мой", token_type(u"Мой")
  17 print u"дядя", token_type(u"дядя")
  18 print u"самых1", token_type(u"самых1")

На примере этого решения особенно остро ощущается важная приятность return: он объявляет своё значение результатом функции и сразу выходит из функции.

Можно (и лучше бы!) сразу и попроверять, что она работает. (Хотя это не обязательно присылать как часть решения).

Напишите программу, которая открывает файл words.txt, и выдаёт в файл tokens.csv таблицу из: номера токена, самого токена, его типа.

Задача на умение вызывать функции, которые вы только что описали. В остальном повторяет решение, которое у вас уже давно было:

   1 import codecs
   2 
   3 ... # здесь определяем tokenize из конспекта и token_type
   4 
   5 with codecs.open("words.txt", "r", "utf-8") as infile:
   6     text = infile.read()
   7 
   8 tokens = tokenize(text)
   9 
  10 with codecs.open("tokens.csv", "w", "utf-8") as outfile:
  11     n = 1
  12     for token in tokens:
  13         line = "{num};{token};{type}".format(token=token, num=n, type=token_type(token))
  14         outfile.write(line + "\n")
  15         n = n + 1

Напишите программу, которая открывает файл words.txt, и выдаёт в файл tokens.csv таблицу из: начальной позиции токена, самого токена, его типа. Начальной позицией токена является номером символа, с которого токен начинается1. Символы в файле нумеруются с нуля (учитываться должны _все_ символы в файле, включая невидимые)2. Дополнительное ограничение: в программе не должно быть функции длиннее 10 строк, и вне функций должно быть не больше 10 строк кода.

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

Самое простое решение, как сделать эту функцию, строится из таких размышлений: предположим, мы знаем координату конца предыдущего токена; тогда мы можем воспользоваться str.find для того, чтобы найти текст нашего токена (он заведомо будет первым после этоой позиции, а str.find умеет искать начиная с заданной позиции); и тогда конец нашего токена будет позиция его начала + его длина. (Правда, это рассуждение работает только в предположении, что запись токена ничем не отличается от его записи в тексте – в нашем токенизаторе это работает):

   1 def positions(tokens, text):
   2     positions = []
   3     last_tail = 0 # позиция конца предыдущего токена перед первым токеном -- начало текста
   4     for token in tokens:
   5         position = text.find(token, last_tail) # см. хелпы про str.find
   6         positions.append(position)
   7         last_tail = position + len(token)
   8     return positions

Напишите функцию lengths(words), которая получает на вход список питонских строк, и возвращает список их длин в том же порядке

Последние четыре задачи – на набивание руки на самой полезной на сейчас парадигме, в которой стоит писать функции. Парадигма – писать функции по образу и подобию tokenize:

   1 def lengths(list):
   2     result = []
   3     for word in list:
   4         result.append(len(word))
   5     return result
   6 
   7 print "Works?", lengths(["a", "aaa", "aaa!!!"]) == [1, 3, 6]

Напишите функцию average(numbers), которая получает на вход список чисел, и возвращает среднее арифметическое (без округлений)

Тоже всё просто:

   1 def average(numbers):
   2     sum = 0.0 # эта мелочь спасает меня от необходимости где-либо использовать float
   3     for number in numbers:
   4         sum = sum + number
   5     return sum / len(numbers)
   6 
   7 print "Works?", average([1, 2, 3, 4]) == 2.5

Напишите функцию stringify(list), которая получает на вход списко чего угодно, и возвращает список строк, полученных из каждого элемента в том же порядке

Это очень полезная штука, рекомендую её заполучить себе в арсенал. Здорово помогает рядом с join:

   1 def stringify(list):
   2     result = []
   3     for elem in list:
   4         result.append(str(elem))
   5     return result
   6 
   7 print "Works?", stringify(["a", 1, 2]) == ["a", "1", "2"]

Напишите функцию token_types(tokens), которая получает на вход список токенов, и возвращает список их типов в том же порядке. (Разумеется, можно и лучше пользоваться уже готовой функцией token_type):

Снова задача на умение вызывать написанную вами же ранее функцию:

   1 def token_type(token):
   2     ... # копируем из второго задания
   3 
   4 def token_types(tokens):
   5     types = []
   6     for token in tokens:
   7         types.append(token_type(token))
   8     return types
   9 
  10 print "Works?", token_types([u"Пушкин", u"это", u"что-то"]) == ["title", "lower", "other"]

модули

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

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

Чтобы использовать одну и ту же функцию несколько раз из разных программ, в питоне есть понятие модулей. Вы с ними уже сталкивались много раз, и пользуетесь ими постоянно: например, функцией open из модуля codecs.

Мы можем создавать и свои модули, это очень просто. В питоне есть правило: если в той же папке, что и ваша программа, лежит файл xyz.py, то из программы в можете сказать import xyz, и пользоваться теми функциями, которые лежат в xyz.py.

Например, если у нас есть файл tokenizer.py с текстом:

   1 def tokenize(text):
   2     ... # подставьте сюда вашу функцию tokenize для вашей задачи

То мы можем сделать скрипт для выдачи токенов из файла, скажем print_tokens.py:

   1 import codecs
   2 import tokenizer
   3 
   4 with codecs.open("words.txt", "r", "utf-8") as file:
   5     text = file.read()
   6 
   7 tokens = tokenizer.tokenize(text)
   8 
   9 for token in tokens:
  10     print token

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

При импортировании файлов питон создаёт для себя вспомогательные файлы. Например, после импортирования файла xyz.py он создаст рядом файл xyz.pyc. По существу они содержат в себе эквивалент содержимого модуля xyz.py, но в нечелочеческом бинарном формате. Их можно стирать, но питон будет их создавать заново каждый раз при импортировании.

Правила хорошего тона

В питоне принято, чтобы текст программы в общем целом шёл в таком порядке:

• сначала импорты

• затем константы, если они у нас есть (например, если мы работаем с csv, то, вероятно, символ, который мы используем для разделителя – это константа)

• затем определения функций
• и только затем код программы вне функций

   1 def hello(who):
   2     print "Hello", who
   3 
   4 print "Help, I'm being imported!"

   1 import xyz

Help, I'm being imported!

   1 def tokenize(...):
   2     ...
   3 
   4 def token_type(...):
   5     ...
   6 
   7 if __name__ == "__main__":
   8     text = u"""
   9       Особенно широко использовалась дактилоскопия империалистами США
  10       в борьбе против прогрессивных и революционных деятелей. - Б.С.Э.
  11     """
  12     for token in tokenize(text):
  13         print token

dict

Новый тип данных в питоне – словари – предназначен для хранения отношений между парами сущностей. В других языках этот же тип называется: хэш-таблицами, ассоциативными массивами, отображениями и т.п.

Идея похожа на словари в обычном понимании: аналог определяемого в питонском словаре называется ключом, и может быть числом или строкой, а аналог словарной статьи в питонском словаре называется значением, и может быть любым питонским объектом.

Пример:

   1 x = {'apple': 'kind of a fruit', 'peacock': 'kind of a bird', 'jellybaby': 'edible stuff'}
   2 print x

Со словарями мы можем работать как со списками, только в качестве адреса элемента мы должны указывать не номер, а ключ элемента. (Более того, порядок хранения элементов в словаре не определён, наверняка не совпадает с тем, в каком порядке вы их в него положили, и определяется так, чтобы питон мог быстрее доставать по ключу значения):

   1 print x['apple']
   2 x['orange'] = 'an orange-colored fruit'
   3 x[2] = ['number', 'two'] # NB: здесь ключ число
   4 print x

В питонских словарях по одному ключу в каждый конкретный момент времени лежит только одно значение. Мы можем лишь заменить его на другое или удалить:

   1 x['apple'] = 'a green fruit'
   2 print x
   3 x.pop('apple') # см. хелпы, это чуть более полезный метод
   4 print x

С точки зрения цикла и других списковых операций словарь выглядит как список ключей. (Это логично: если бы он вёл себя как список значений, то зачем нужен словарь? Основная информация в словаре – это отношения ключ--значение. В словаре есть средства получить значение по ключу, но нет средств получить ключ по значению).

   1 for word in x:
   2     definition = x[word]
   3     print word, definition

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

Пример: частотный словарь

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

Не пользуясь словарями:

   1 def counts_v1(words):
   2     counts = []
   3     for word in words:
   4         count = words.count(word)
   5         counts.append([word, count])
   6     return counts

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

   1 def counts_v2(words):
   2     counts = []
   3     seen = []
   4     for word in words:
   5         if word not in seen:
   6             count = words.count(word)
   7             counts.append([word, count])
   8             seen.append(word)
   9     return counts

Через словари мы можем воспользоваться другой идеей: идти по словам, и про каждое слово вспомнить, сколько раз мы его видели уже, и прибавить к этому единицу.

   1 def counts_v3(words):
   2     counts = {}
   3     for word in words:
   4         counts[word] = counts[word] + 1
   5     return counts

Одна беда: оно не работает потому, что мы не можем из словаря прочитать по ключу, которого мы ещё не видели. Два варианта, как из этого выходить: либо сначала сделать все нужные ключи в словаре (и положить туда 0), либо проверять про каждое слово, не видели ли мы его ещё.

   1 def counts_v4(words):
   2     counts = {}
   3     for word in words:
   4         if word in counts:
   5             counts[word] = counts[word] + 1
   6         else:
   7             counts[word] = 1
   8     return counts

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

   1 very_many_words = ["a"] * 2000000 # список из 2 миллионов словоупотреблений, правда все они -- слово "a"
   2 print "dict", counts_v4(very_many_words)
   3 print "list", counts_v2(very_many_words)

Дело в том, что words.count(word) по существу проходит циклом по всему списку words, то есть делает 2млн каких-то действий. И вдобавок, мы эту функцию вызываем для каждого слова из words, то есть вызываем эту функцию 2млн раз: получаем 4 триллиона каких-то действий.

Первое правило оптимизации

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

Полезно знать два простых правила оптимизации:

1. The first rule of optimization: DON'T DO IT!!!

2. EXPERTS ONLY!!! The second rule of optimization: see footnote²

Понимать это нужно так:

• ваша первая задача, когда вы что-то пишете – добиться, чтобы программа в принципе достигала поставленной задачи. Если она не достигает цели – цена ей ноль.

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

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

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

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

sorted

Функция sorted получает на вход список (или другой итератор) и возвращает его отсортированным по возрастанию. Она пользуется для этого стандартными операциями сравнения, поэтому умеет сортировать числа по возрастанию, слова и списки в лексикографическом порядке.

   1 print sorted([3, 54, 1, 234, 1])

Отсюда следует и самый простой способ вывести словарь в лексикографическом порядке:

   1 for word in sorted(x):
   2     print word, x[word]

   1 x = []
   2 y = x
   3 print x
   4 y.append(2)
   5 print x

   1 x = []
   2 y = [x, x]
   3 z = {1: x, 2: x}
   4 x.append(1)
   5 print y
   6 print z

   1 x = [1, 2, 3]
   2 y = x
   3 print x is y
   4 print y is x
   5 y = [1, 2, 3]
   6 print x is y
   7 print y is x
   8 y = list(x)
   9 print x is y
  10 print y is x

   1 x = 1, 2, 3
   2 print x
   3 print x[0]
   4 x[0] = 3 # нельзя!

   1 chess = {}
   2 chess['e', 2] = 'pawn'
   3 chess['e', 1] = 'king'
   4 
   5 for x in "abcdefgh":
   6     for y in range(1, 9):
   7        if (x, y) in chess:
   8            print x, y, chess[x, y]

   1 items = [1, 2]
   2 x = items[0]
   3 y = items[1]

   1 x, y = items

   1 def token_type(token):
   2     ... # здесь мы создаём переменные case и content
   3     return case, content
   4 
   5 ...
   6 
   7 case, content = token_type("Что-то")

   1 tokens = ["Hello", "woNderful", "world"]
   2 positions = [1, 12, 42]
   3 types = ["title", "mixed", "lower"]
   4 
   5 data = zip(tokens, positions, types)
   6 for datum in data:
   7     token, position, type = datum
   8     print position, token, type

   1 tokens = ["Hello", "woNderful", "world"]
   2 positions = [1, 12, 42]
   3 types = ["title", "mixed", "lower"]
   4 
   5 for token, position, type in zip(tokens, positions, types):
   6     print position, token, type

   1 import codecs
   2 with codecs.open(...) as file:
   3     lines = list(file)
   4     numbers = range(len(lines))
   5     for n, line in zip(numbers, lines):
   6         print n + 1, line.rstrip()

   1 import codecs
   2 with codecs.open(...) as file:
   3     for n, line in enumerate(file):
   4         print n + 1, line.rstrip()

Литература

• http://docs.python.org/2.7/tutorial/modules.html

• http://docs.python.org/2.7/tutorial/datastructures.html#dictionaries

• http://docs.python.org/2.7/tutorial/datastructures.html#tuples-and-sequences

• http://docs.python.org/2.7/library/functions.html#zip

• http://docs.python.org/2.7/library/functions.html#enumerate