3_loops/3_loops.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# PYTHON 3\n",
    "\n",
    "## Словари, множества, collections\n",
    "\n",
    "\n",
    "### Даниил Поляков\n",
    "\n",
    "\n",
    "MIPT 2019"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Напоминание с предыдущего семинара: в Python все является объектом"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Еще коротенькое напоминание про mutable и immutable объекты\n",
    "\n",
    "### Неизменяемые типы\n",
    "- int\n",
    "- float\n",
    "- complex\n",
    "- bool\n",
    "- str\n",
    "- tuple\n",
    "- frozenset\n",
    "\n",
    "При попытке совершить мутирующую операцию с неизменяемым объектом может произойти одна из двух вещей:\n",
    " - Произойдет создание измененной копии объекта (оператор += )\n",
    " - Произойдет ошибка (оператор [])\n",
    " \n",
    "### Изменяемые типы\n",
    "- list\n",
    "- dict\n",
    "- set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Создание и удаление\n",
    "\n",
    "\n",
    "- Note: При создании двух mutable-объектов отдельно - они будут гарантированно разными. Для immutable объектов это верно не всегда.\n",
    "- Об удалении объектов заботиться не нужно, за вас всё сделает интерпретатор"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Словари\n",
    "\n",
    "Универсальное средство для выражения связей между объектами, подсчёта, группировки.\n",
    "Их иногда ещё называют **ассоциативными массивами или хеш-таблицами**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Key1': 'Value1', 'Key2': 'Value2'}"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = {'Key1' : 'Value1', 'Key2' : 'Value2'}\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: 1, 2: 4, 3: 9}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = dict([(1, 1), (2, 4), (3, 9)])\n",
    "b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ключом словаря может быть любой hashable-объект.\n",
    "\n",
    "Определение hashable из документации Python: https://docs.python.org/3/glossary.html#term-hashable \n",
    "\n",
    "Если коротко, то у объекта должен быть правильно определен метод `__hash__()`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Хэш от инта - само знчаение инта"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "343"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hash(343)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1152921504606846982"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hash(6.5) # есть тонкости, связанные с точностью представления чисел с поавающей запятой\n",
    "          # месседж: нужно быть очень аккуратным с хэшированием float и лучше их вообще не хэшировать"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для строк уже по-другому"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-5145302367326745666\n",
      "-1246691722954946658\n"
     ]
    }
   ],
   "source": [
    "print(hash('aaa'))\n",
    "print(hash('aab'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Note: после перезапуска интерпретатора у сложных объектов (например, строк) будет уже другое значение хэш-функции"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "list в Python не является хэшируемым объектом"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[1].__hash__ is None  # метод __hash__ не определен для списка"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно ли использовать словарь в качестве ключа словаря?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "unhashable type: 'dict'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-3-26b72dd798aa>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0md1\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m'b'\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0md2\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0md1\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m'abc'\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: unhashable type: 'dict'"
     ]
    }
   ],
   "source": [
    "d1 = {1: 'b'}\n",
    "d2 = {d1: 'abc'}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{1: 'b'}.__hash__ is None  # dict тоже не является хэшируемым"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "По словарю можно итерироваться, причем как по ключам, так и по значениям"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "b\n",
      "c\n",
      "\n",
      "a\n",
      "b\n",
      "c\n"
     ]
    }
   ],
   "source": [
    "# итерация по словарю\n",
    "dictionary = {'a': 1, 'b': 2, 'c': 3}\n",
    "   \n",
    "for k in dictionary.keys():\n",
    "    print(k)\n",
    "    \n",
    "print()\n",
    "    \n",
    "for k in dictionary:  # такая же итерация по ключам, но Python Zen говорит нам, что явное лучше, чем неявное\n",
    "    print(k)          # поэтому лучше явно прописать .keys(), чтобы улучшить читабельность кода\n",
    "                      # слишком читабельный код еще никогда никому не мешал"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "for v in dictionary.values(): # итерация по значениям\n",
    "    print(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('a', 1)\n",
      "('b', 2)\n",
      "('c', 3)\n"
     ]
    }
   ],
   "source": [
    "for pair in dictionary.items(): # итерируемся сразу по парам (ключ: значение)\n",
    "    print(pair)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Petya': 20, 'Vasya': 21, 'Masha': 22}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# конструкторы:\n",
    "a = dict(a=1, b=2, c=3)\n",
    "\n",
    "keys = [\"Petya\", \"Vasya\", \"Masha\"]\n",
    "values = [20, 21, 22]\n",
    "\n",
    "dictionary = dict(zip(keys, values)) # один из самых удобных способов создания словаря из двух списков\n",
    "                                     # что такое zip поговорим уже в следующий раз \n",
    "dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'b', 'c']\n",
      "[1, 2, 3]\n",
      "[('a', 1), ('b', 2), ('c', 3)]\n"
     ]
    }
   ],
   "source": [
    "print(list(a.keys()))\n",
    "print(list(a.values()))\n",
    "print(list(a.items()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Petya': 20, 'Masha': 22}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "del dictionary['Vasya']\n",
    "dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 1, 'b': 2, 'c': 3, 'Petya': 20, 'Masha': 22}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.update(dictionary)  # объединение двух словарей\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 1,\n",
       " 'b': 2,\n",
       " 'c': 3,\n",
       " 'Petya': 20,\n",
       " 'Masha': 22,\n",
       " ('Composite', 'Key'): [1, 2, 3]}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a[('Composite', 'Key')] = [1, 2, 3]   # only immutable objects could be keys in dicts\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задачка на 5 минут\n",
    "### Используя только что полученные знания об итерировании по словарю, давайте подумаем (и кто-то напишет код на доске), как обратить словарь, т.е. как создать словарь с обратными парами (значение: ключ)? Считаем, что в исходном словаре значения тоже являются хэшируемыми"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Помните генераторы списков (list comprehensions) с прошлого занятия? Существуют и генераторы словарей!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 0, 1: 1, 2: 8, 3: 27, 4: 64}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dct = {i : i ** 3 for i in range(5)}\n",
    "dct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Множества (set)\n",
    "В основе set тоже лежит хэш-таблица"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "({1, 2, 3, 5}, {2, 3, 4, 5, 6})"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = {1, 2, 3}\n",
    "b = set([2, 3, 4])\n",
    "\n",
    "a.add(5)\n",
    "b.update({5, 6}) # объединить множество с другим множеством\n",
    "a, b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1}\n",
      "{4, 6}\n",
      "{1, 2, 3, 4, 5, 6}\n",
      "{2, 3, 5}\n"
     ]
    }
   ],
   "source": [
    "print (a - b)\n",
    "print (b - a)\n",
    "print (a | b) # объединение\n",
    "print (a & b) # пересечение"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Существуют и генераторы множеств"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0, 3, 6, 9}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "st = {i for i in range(10) if not i % 3}\n",
    "st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "unhashable type: 'set'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-17-a9d47011d1ab>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0md\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0mst\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m}\u001b[0m \u001b[0;31m# set тоже не является хэшируемым\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: unhashable type: 'set'"
     ]
    }
   ],
   "source": [
    "d = {st: 1} # set тоже не является хэшируемым"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{frozenset({0, 3, 6, 9}): 6}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = {frozenset(st): 6}  # а вот frozenset уже можно хэшировать, так как он является неизменяемым объектом\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Для чего удобно использовать dict и set?\n",
    "\n",
    "### Установление однозначного соответствия каждому объекту из множества ключей какого-то другого объекта (условно можно удобно реализовать словарь для перевода с одного языка на другой)\n",
    "\n",
    "### Для подсчета уникальных элементов в списке/уникальных слов в тексте\n",
    "\n",
    "### Для быстрой проверки элемента на вхождение: поиск по ключу в dict и set выполняется за O(1) (в среднем): от объекта вычисляется хэш и проверяется, есть ли такой хэш в контейнере"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 in a     # O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Рубрика \"задачи с собеседований\" (опционально по желанию семинариста)\n",
    "\n",
    "Даны два отсортированных списка с числами (не обязательно одной длины). Выведите все числа, которые есть в первом списке, но нет во втором"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "lst1 = [1,2,8]\n",
    "lst2 = [2,6]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### способ 1: с помощью set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 8}"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# способ 1\n",
    "set(lst1) - set(lst2) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "формально за O(n) по времени (на создание set уходит O(n), но с немалой константой), но требует доп память, и не используется отсортированность"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### способ 2: давайте подумаем, как это сделать за O(n) по времени, но без доп.памяти"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### collections\n",
    "Объекты в collections - модифицированные для разных нужд словари и еще несколько удобных структур данных.\n",
    "\n",
    "Хороший краткий обзор модуля collections можно почитать [здесь](https://pythonworld.ru/moduli/modul-collections.html) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0\n",
      "defaultdict(<class 'float'>, {2: 0.0})\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "dct = defaultdict(float)\n",
    "\n",
    "print(dct[2]) # если ключа нет, то устанавливает дефолтное значение\n",
    "print(dct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 deque([0, 1, 2, 3, 4, 5, 6, 7, 8])\n",
      "8 deque([0, 1, 2, 3, 4, 5, 6, 7])\n",
      "7 deque([0, 1, 2, 3, 4, 5, 6])\n",
      "6 deque([0, 1, 2, 3, 4, 5])\n",
      "5 deque([0, 1, 2, 3, 4])\n",
      "\n",
      "0 deque([1, 2, 3, 4])\n",
      "1 deque([2, 3, 4])\n",
      "2 deque([3, 4])\n",
      "3 deque([4])\n",
      "4 deque([])\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "q = deque()\n",
    "\n",
    "for i in range(10):\n",
    "    q.append(i)\n",
    "\n",
    "while len(q) > 5: \n",
    "    print(q.pop(), q) # O(1)\n",
    "\n",
    "print()\n",
    "    \n",
    "while len(q):  # пока дек не пуст\n",
    "    print(q.popleft(), q) # O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 'a', 3: 'c', 2: 'b'}\n",
      "OrderedDict([(1, 'a'), (3, 'c'), (2, 'b')])\n"
     ]
    }
   ],
   "source": [
    "from collections import OrderedDict # помнит порядок, в котором ему были даны ключи\n",
    "\n",
    "data = [(1, 'a'), (3, 'c'), (2, 'b')]\n",
    "\n",
    "print(dict(data))\n",
    "print(OrderedDict(data))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Seminar recap\n",
    "- немного про hashable-объекты в Python\n",
    "- словари, множества и операции с ними\n",
    "- collections"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}