#!/usr/bin/env python
# coding: utf-8

# # Программирование на языке Python для сбора и анализа данных
# 
# *Текст лекции: Щуров И.В., НИУ ВШЭ*
# 
# Данный notebook является конспектом лекции по курсу «Программирование на языке Python для сбора и анализа данных» (НИУ ВШЭ, 2015-16). Он распространяется на условиях лицензии [Creative Commons Attribution-Share Alike 4.0](http://creativecommons.org/licenses/by-sa/4.0/). При использовании обязательно упоминание автора курса и аффилиации. При наличии технической возможности необходимо также указать активную гиперссылку на [страницу курса](http://math-info.hse.ru/s15/m). Фрагменты кода, включенные в этот notebook, публикуются как [общественное достояние](http://creativecommons.org/publicdomain/zero/1.0/).
# 
# Другие материалы курса, включая конспекты и видеозаписи лекций, а также наборы задач, можно найти на [странице курса](http://math-info.hse.ru/s15/m).

# ## Лекция №5. Словари и списковые включения

# ### Словари

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

# In[1]:


students = ["Вася", "Коля", "Петя", "Аня"]
grades = [5, 4, 2, 3]
# Вася получил 5, Коля 4 и т.д.


# В принципе, мы могли бы теперь, зная имя студента, найти его номер в первом списке и потом обратиться к элементу второго списка с тем же номером. Однако, этот подход довольно неэффективен: если бы у нас была тысяча студентов, нам пришлось бы сначала долго-долго просматривать их список в поисках нужного имени. Время, необходимое на поиск нужной информации, росло бы вместе с ростом длины списка. Это плохо.
# 
# Было бы здорово, если бы у нас была возможность иметь тип данных, в котором элементы нумеруются не натуральными числами, а произвольными объектами. Оказывается, такой тип данных существует: в Python он называется *словарём* (*dictionary*).
# > Более общий термин для такого типа данных: *ассоциированный массив*; в других языках программирования используются также другие термины — например, в Perl похожий объект называется *hash* — сокращение от *hash table*.
# 
# Вот так можно создать словарь в Python:

# In[2]:


gradebook = {"Вася": 5, "Коля": 4, "Петя":2, "Аня": 3}


# Это похоже на создание списка, но есть ряд отличий. Во-первых, мы использовали фигурные скобки вместо квадратных, чтобы показать, что создаём именно словарь. Во-вторых, словарь состоит из *записей*, каждая запись состоит из двух частей: *ключа* (*key*) и *значения* (*value*). Ключ и значение разделяются двоеточием. Например, у нас есть запись `"Аня": 3` с ключом `"Аня"` и значением `3`. Всего наш словарь `gradebook` сейчас содержит четыре записи, ключами которых являются имена студентов, а значениями — их оценки.

# In[3]:


gradebook


# Заметим, что при печати Python переупорядочил записи в словаре. На самом деле, порядок вывода записей в словаре является произвольным: внутри словаря записи не имеют никакого порядка. Поэтому нельзя обратиться, например, к «первой записи», но зато можно обратиться к записи с данным ключом:

# In[4]:


gradebook['Аня']


# In[5]:


gradebook['Вася']


# Можно изменить значение записи, точно так же, как изменить элемент списка.

# In[6]:


gradebook['Аня'] = 5 # Аня переписала контрольную!


# In[7]:


gradebook


# Можно добавить новую запись.

# In[8]:


gradebook['Иннокентий'] = 4 # О, новенький!


# In[9]:


gradebook


# При попытке обратиться к записи, которой нет, мы получим сообщение об ошибке:

# In[10]:


gradebook['Alice']


# Часто нам хочется иметь возможность запросить запись, а в случае, если её нет, получить какое-нибудь «значение по умолчанию», а не ошибку. Для этого нужно использовать метод `get()` вместо квадратных скобок.

# In[11]:


gradebook.get('Alice')


# Здесь вернулось `None`:

# In[12]:


print(gradebook.get('Alice'))


# In[13]:


gradebook.get('Вася')


# Можно было бы передать `get()` второй аргумент, и тогда в случае, если такого ключа в словаре нет, то будет возвращен он.

# In[14]:


gradebook.get('Alice', 'No such student')


# In[15]:


gradebook.get('Вася',  'No such student')


# Можно получить список всех ключей словаря:

# In[16]:


gradebook.keys()


# На самом деле это не совсем список, но эта штука ведёт себя почти как список и из неё можно сделать список. Аналогично со списком всех значений словаря.

# In[17]:


gradebook.values()


# Ключами словарей могут быть не только строчки. Допустим, мы хотим создать словарь, в котором ключами будут числа. Нет ничего проще:

# In[18]:


squares={1:1, 2:4, 3:9}


# In[19]:


squares


# In[20]:


squares[1]


# In[21]:


squares[2]


# В предыдущих двух строчках `squares` ведёт себя примерно как список, но если внимательно приглядеться, то видно, что это не список, а всё-таки словарь.

# In[22]:


squares


# Например, у любого непустого списка есть элемент с индексом 0, а у `squares` такого нет:

# In[23]:


squares[0]


# ### Перебор записей в словаре
# Как обрабатывать информацию в словаре? Для перебора всех элементов списка можно было использовать цикл `for`. А что будет, если ему скормить словарь вместо списка? Попробуем:

# In[24]:


for k in gradebook:
    print(k)


# Понятно! Цикл `for` в этом случае перебирает все *ключи* нашего словаря. А зная ключ, можно получить и значение:

# In[25]:


for k in gradebook:
    print("Студент", k, "имеет оценку", gradebook[k])


# Однако, есть более изящный способ получить сразу ключ и значение очередной записи: использовать `items()`.

# In[26]:


for k, v in gradebook.items():
    print("Студент",k,"имеет оценку", v)


# Как работает этот код? Здесь используется метод `items()`, возвращающий список (точнее, итератор), состоящий из кортежей вида `(ключ, значение)`. 

# In[27]:


list(gradebook.items())


# Оператор `for` в этом случае понимает, что нужно при каждом проходе цикла выбрать очередной кортеж и присвоить его первый элемент (то есть ключ) переменной `k`, а второй элемент (то есть значение) переменной `v` (конечно, эти переменные могли бы называться иначе). С аналогичным поведением мы уже встречались, когда обсуждали конструкцию `enumerate` (см. [лекцию №3](http://nbviewer.ipython.org/github/ischurov/pythonhse/blob/master/Lecture%203.ipynb#%D0%9D%D1%83%D0%BC%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D1%8F-%D1%8D%D0%BB%D0%B5%D0%BC%D0%B5%D0%BD%D1%82%D0%BE%D0%B2-%D1%81%D0%BF%D0%B8%D1%81%D0%BA%D0%B0)).
# 
# Вот так можно найти все записи с заданным значением — например, всех студентов, получивших оценку 4:

# In[28]:


for k, v in gradebook.items():
    if v==4:
        print(k)


# Заметим, что такой «поиск по значению» требует перебора всех записей в словаре и если словарь большой, то он будет занимать много времени — хотя «поиск по ключу» будет по-прежнему выполняться быстро. Кстати, можно быстро проверить, существует ли в словаре запись с данным ключом: 

# In[29]:


"Коля" in gradebook


# In[30]:


"Alice" in gradebook


# Если бы мы хотели искать среди значений, то нужно было бы явно это указать с помощью метода `values()`:

# In[31]:


1 in gradebook.values()


# In[32]:


4 in gradebook.values()


# Вообще оператор `in` не ограничивается только использованием со словарями: он может использоваться, например, со списками:

# In[33]:


5 in [1,2,3,5,8]


# In[34]:


6 in range(1,5)


# ### Создание словарей и функция `zip()`
# Есть разные способы создавать словари. Например, можно создать пустой словарь и постепенно заполнять его элементами:

# In[35]:


my_dict = {}


# In[36]:


my_dict[1] = 1
my_dict['hello'] = 'world'


# In[37]:


my_dict


# Заметим, что в одном и том же словаре прекрасно уживаются элементы разных типов (в данном случае — строки и целые числа).
# 
# Можно создать словарь иначе, передав функции `dict()` список, состоящий из пар ключ-значение (в некоторо смысл, это обратная операция методу `items()`):

# In[38]:


dict([('hello','world'), ('one', 'two')])


# Вернёмся к началу лекции. Допустим, у нас есть два списка, в одном находятся имена студентов, а в другом их оценки. Как можно из этих списков создать словарь, для которого имена были бы ключами, а оценки значениями?
# 
# А вот так:

# In[39]:


students = ["Вася", "Коля", "Петя", "Аня"]
grades = [5, 4, 2, 3]
new_gradebook = list(zip(students,grades))
new_gradebook


# Здесь используется удобная функция `zip()`, применение которой не ограничивается созданием словарей. Подобно застёжки-молнии, она «состёгивает» (отсюда и название) несколько списков. Например, `zip()` делает из пары списков список пар (утверждение звучит как скороговорка, но если вы подумаете нам ним как следует, то заметите, что оно в точности описывает то, что делает эта команда):

# In[40]:


list(zip([1,2,3],['a','b','c']))


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

# In[41]:


for student, grade in zip(students, grades):
    print(student, "has grade", grade)


# Функцию `zip()` можно использовать и более чем с двумя списками:

# In[42]:


list(zip([1,2,3,4], [5,6,7,8], ['a','b','c','d']))
# списка три, поэтому на выходе получится список из троек


# Если какой-то из списков окажется короче, то `zip()` «обрежет» остальные списки:

# In[43]:


list(zip([1,2,3], ['a','b']))


# ### Какие объекты могут быть ключами словарей

# До сих пор мы рассматривали словари, ключами которых являются строки и числа. На самом деле, ключами могут быть и более сложно устроенные объекты. Например, представим себе такую реализацию фрагмента таблицы сложения в виде словаря:

# In[44]:


sums = {(2,3): 5, (4, 1): 5, (5, 7): 12}


# In[45]:


sums


# Здесь ключами являются кортежи, состоящие из двух чисел, а значениями — суммы этих чисел.

# In[46]:


sums[(2,3)]


# In[47]:


sums[(4,1)]


# In[48]:


sums[(5,7)]


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

# In[49]:


sums = { [1,2]: 3}


# На этом мы закончим краткое введение в словари и перейдём к следующей теме.
# ### Списковые включения (list comprehensions)

# Мы ранее частенько сталкивались с такой задачей: дан список, в котором записаны числа, но в виде строчек. Создать новый список, в котором числа были бы числами. Мы могли решить эту задачу с помощью цикла:

# In[50]:


str_list = ["1", "5", "12", "7"]

int_list = []
for s in str_list:
    int_list.append(int(s))
    
print(int_list)


# За создание нового списка отвечают три строчки. Писать их каждый раз довольно тоскливо, и создатели Python придумали (точнее, заимствовали из функциональных языков программирования, а те его заимствовали у математиков) гораздо более изящный синтаксис. Он устроен вот так:

# In[51]:


int_list = [int(s) for s in str_list]


# Кадратные скобки вокруг выражения должна подсказать, что мы создаём список (потому что когда нужно создать список, мы обычно заключаем его элементы в квадратные скобки). Выражение внутри скобок нужно читать буквально:
# 
# *список, состоящий из элементов `int(s)` для (`for`) элементов `s` из (`in`) списка `str_list`*
# 
# Представьте себя Гарри Поттером, у которого есть волшебная палочка, превращающая строки в числа. Мы подействовали этой волшебной палочкой на все элементы списка `str_list`.

# In[52]:


int_list


# Видите? Кавычки исчезли — перед нами список, состоящий из чисел. Магия! Исходный список `str_list` при этом не изменился:

# In[53]:


str_list


# Аналогично можно применять любую операцию к элементам списка. Например, возведём все элементы из `int_list` в квадрат (Гарри Поттер взял другую волшебную палочку):

# In[54]:


[x**2 for x in int_list]


# или удвоим все элементы списка:

# In[55]:


double_list = [x*2 for x in int_list]


# In[56]:


double_list


# или прибавим к ним 1:

# In[57]:


[x+1 for x in int_list]


# или превратим их в числа с плавающей точкой:

# In[58]:


[float(x) for x in int_list]


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

# In[59]:


[x for x in int_list if x > 6]


# Когда мы пишем здесь `x for x` мы имеем в виду, что нужно просто подставить в новый список элементы старого, ничего с ними не делая (только выбирая нужные). Но можно и как-то их модифицировать:

# In[60]:


[x**2 for x in int_list if x > 6]


# Решим теперь такую задачу: есть два списка с числами, а мы хотим найти их поэлементную сумму.

# In[61]:


X = [2, 5, 8]
Y = [1, 3, 100]


# Её можно решить таким образом (для перебора элементов двух списков одновременно используем конструкцию `zip()`, обсуждавшуюся выше):

# In[62]:


Z = []
for x, y in zip(X, Y):
    Z.append(x + y)
print(Z)


# Но со списочными включениями тот же код выглядит гораздо симпатичнее:

# In[63]:


[x + y for x, y in zip(X, Y)]


# Кстати, можно использовать синтаксис, похожий на списочное включение, чтобы создавать словари:

# In[64]:


squared = {i: i**2 for i in range(10)} # обратите внимание на фигурные скобки!
squared


# ### Функция `map()`

# У списочных включений есть аналог, который сейчас считается не слишком удобным, но иногда встречается: функция `map()`. Вернёмся к задаче про прервращение строчек в числа.

# In[65]:


str_list


# Вот так она решается с помощью `map()`:

# In[66]:


int_list = list(map(int, str_list))


# In[67]:


list(int_list)


# Функция `map()` принимает два аргумента. Первым аргументом она принимает функцию (да-да, в Python функции можно передавать другим функциям в качестве аргументов!), а вторым — список. После этого она применяет эту функцию к каждому из элементов списка. В общем, записи вида `list(map(int, str_list))` и `[int(x) for x in str_list]` почти эквивалентны.
# 
# Когда действие, которое нужно применить, уже существует в виде функции (как в случае с `int`), то конструкция с `map()` выглядит даже более лаконичной, чем списочное включение. Но если нам нужно сделать что-то менее тривиальное, списочные включения явно проще:

# In[68]:


[int(x)+1 for x in str_list]


# Чтобы реализовать это с помощью `map()`, нужно объявить новую функцию, которая будет возвращать значение выражения `int(x)+1` и передать её `map()`.

# In[69]:


def my_func(x):
    return int(x)+1


# In[70]:


list(map(my_func,str_list))


# Для краткости можно использовать `lambda`-функции (мы про них как-нибудь ещё поговорим), но такой подход гораздо менее прозрачен, чем списочные включения, и сейчас использовать его не рекомендуется.

# ### Два слова об эффективности

# Использовать списочные включения не только приятно, но и полезно: они работают эффективнее, чем код с циклом.

# In[71]:


from random import random
from math import sqrt
N = 10000
mylist = [random() for _ in range(N)]


# In[72]:


get_ipython().run_cell_magic('timeit', '', '\nnewlist = []\nfor x in mylist:\n    newlist.append(sqrt(x))\n')


# In[73]:


get_ipython().run_cell_magic('timeit', '', 'newlist = [sqrt(x) for x in mylist]\n')


# In[74]:


get_ipython().run_cell_magic('timeit', '', 'newlist = list(map(sqrt, mylist))\n')


# Как видно из этих данных (магическое слово `%timeit` позволяет измерить, сколько времени уходит на какую-то операцию), списочные включения почти в два раза быстрее обычного цикла. `map()` работает примерно с такой же скоростью, как и списочные включения (иногда чуть медленнее, иногда чуть быстрее).

# ### Сложные структуры данных

# Списки позволяет сохранить некоторый ряд значений, но зачастую нужно уметь работать с более сложные структурами — например, с таблицами. В некоторых языках программирования есть *двумерные массивы*. Аналогом двумерного массива в Python является «список списков», то есть такой список, элементами которого являются другие списки. С чем-то подобным мы уже встречались.
# 
# Рассмотрим пример: таблица, в которой записаны результаты по нескольким домашним работам у нескольких студентов. (Допустим, мы присвоили студентам некоторые номера и поэтому нам не нужно знать, кого как зовут.) Её можно записать в виде списка списков, например, по строчкам:

# In[75]:


table = [["HW1", "HW2", "HW3", "HW4"], [4, 3, 4, 4], [3, 4, 3, 4], [4, 5, 5, 4]]


# Здесь каждый элемент списка `table` — это строчка нашей таблицы, то есть тоже список. Например, вот так можно узнать, что записано в третьей строке и четвертом столбце нашей таблицы:

# In[76]:


table[2][3]


# Что здесь произошло? Мы сначала вызвали третью строку таблицы с помощью

# In[77]:


table[2]


# А потом из этой третьей строки выбрали четвертый элемент с помощью `[3]`. Можно было бы записать это более подробно:

# In[78]:


row = table[2]
print(row[3])
# row[3] это то же самое, что table[2][3]


# Вот так можно напечатать все элементы таблицы по строчкам:

# In[79]:


for row in table:
    print(*row)


# Допустим теперь, что нам всё же хочется знать, какой студент какую оценку получил. Тогда мы могли бы вместо списка списков использовать словарь, у которого списки были бы значениями:

# In[80]:


gradebook = {'Bill': [4, 3, 2], 'Alice': [3, 4, 5], 'Bob': [5, 5, 4]}


# Вот так можно посмотреть, какую оценку получил Боб по второй домашке:

# In[81]:


gradebook['Bob'][1]


# На сегодня всё! :)