sem05_dict/sem05_204.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Семинар 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[42, 0, -9, 5, -15]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [42, 0, -9, 5, -15]\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-15, -9, 0, 5, 42]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.sort()\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'tuple' object does not support item assignment",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-7-2f7db5666e11>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m42\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m9\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m15\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[0mx\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m\u001b[0;36m42\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: 'tuple' object does not support item assignment"
     ]
    }
   ],
   "source": [
    "x = (42, 0, -9, 5, -15)\n",
    "x[2] =42"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('Маша', 12), ('Мирослав', 1), ('Добрыня', 4)]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = ['Маша', 'Мирослав', 'Добрыня']\n",
    "b = [12, 1, 4]\n",
    "\n",
    "list(zip(a,b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "book = [('яйца', 60), ('чай', 16), ('кофе', 35), ('лён', 20), \n",
    "        ('петрушка', 15), ('торт', 10), ('арбуз', 60), ('йогурт', 35), \n",
    "        ('соя', 20), ('ролтон', 42), ('бобы', 10), ('глаз дракона', 2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('яйца', 60)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'яйца'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "60"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book[0][1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задача:__ Покупатель пришел и говорит \"Хочу бобы, сколько стоят?\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "z = 'бобы'\n",
    "for item in book:\n",
    "    if item[0] == z:\n",
    "        print(item[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Это __линейный поиск.__ То есть мы перебираем по очереди все элементы и смотрим подходят ли они нам. __Вопрос:__ сколько в худшем случае он работает по времени? Исходная книга длины $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Линейный поиск: O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мы хотим искать быстрее $\\Rightarrow$ __бинарный поиск.__ Мы изначально договариваемся, что хотим хоранить данные в отсортированном виде. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "book = [('яйца', 60), ('чай', 16), ('кофе', 35), ('лён', 20), \n",
    "        ('петрушка', 15), ('торт', 10), ('арбуз', 60), ('йогурт', 35), \n",
    "        ('соя', 20), ('ролтон', 42), ('бобы', 10), ('глаз дракона', 2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('арбуз', 60),\n",
       " ('бобы', 10),\n",
       " ('глаз дракона', 2),\n",
       " ('йогурт', 35),\n",
       " ('кофе', 35),\n",
       " ('лён', 20),\n",
       " ('петрушка', 15),\n",
       " ('ролтон', 42),\n",
       " ('соя', 20),\n",
       " ('торт', 10),\n",
       " ('чай', 16),\n",
       " ('яйца', 60)]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(book)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('глаз дракона', 2),\n",
       " ('торт', 10),\n",
       " ('бобы', 10),\n",
       " ('петрушка', 15),\n",
       " ('чай', 16),\n",
       " ('лён', 20),\n",
       " ('соя', 20),\n",
       " ('кофе', 35),\n",
       " ('йогурт', 35),\n",
       " ('ролтон', 42),\n",
       " ('яйца', 60),\n",
       " ('арбуз', 60)]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f(item):\n",
    "    return item[1]\n",
    "\n",
    "sorted(book, key=f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('глаз дракона', 2),\n",
       " ('торт', 10),\n",
       " ('бобы', 10),\n",
       " ('петрушка', 15),\n",
       " ('чай', 16),\n",
       " ('лён', 20),\n",
       " ('соя', 20),\n",
       " ('кофе', 35),\n",
       " ('йогурт', 35),\n",
       " ('ролтон', 42),\n",
       " ('яйца', 60),\n",
       " ('арбуз', 60)]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(book, key=lambda item: item[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('глаз дракона', 2),\n",
       " ('петрушка', 15),\n",
       " ('йогурт', 35),\n",
       " ('ролтон', 42),\n",
       " ('арбуз', 60),\n",
       " ('яйца', 60),\n",
       " ('кофе', 35),\n",
       " ('торт', 10),\n",
       " ('бобы', 10),\n",
       " ('чай', 16),\n",
       " ('лён', 20),\n",
       " ('соя', 20)]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(book, key=lambda item: len(item[0]), reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'а' < 'б'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'аа' < 'аб'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'ааб' < 'бaб'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"ё\" < \"я\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1072"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ord('а')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1103"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ord('я')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1105"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ord('ё')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('арбуз', 60),\n",
       " ('бобы', 10),\n",
       " ('глаз дракона', 2),\n",
       " ('йогурт', 35),\n",
       " ('кофе', 35),\n",
       " ('лён', 20),\n",
       " ('петрушка', 15),\n",
       " ('ролтон', 42),\n",
       " ('соя', 20),\n",
       " ('торт', 10),\n",
       " ('чай', 16),\n",
       " ('яйца', 60)]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book = sorted(book)\n",
    "book"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def binary_search(book, goal):\n",
    "    lower = 0\n",
    "    upper = len(book) - 1\n",
    "    \n",
    "    while lower <= upper:\n",
    "        mid = (lower + upper) // 2\n",
    "\n",
    "        if book[mid][0] == goal:\n",
    "            return mid\n",
    "        elif book[mid][0] > goal:\n",
    "            upper = mid - 1\n",
    "        else:\n",
    "            lower = mid + 1\n",
    "    return None\n",
    "    \n",
    "binary_search(book, 'бобы')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('кофе', 35)"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "idx = binary_search(book, 'кофе')\n",
    "book[idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "idx = binary_search(book, 'johaghoaeкофе')\n",
    "print(idx)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Замаскированные циклы: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = ['Маша', 'Мирослав', 'Добрыня']\n",
    "'Маша' in a # линейный поиск O(n), если a - list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.index('Маша') # линейный поиск O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Хэш-таблица"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "book = [('яйца', 60), ('чай', 16), ('кофе', 35), ('лён', 20), \n",
    "        ('петрушка', 15), ('торт', 10), ('арбуз', 60), ('йогурт', 35), \n",
    "        ('соя', 20), ('ролтон', 42), ('бобы', 10), ('глаз дракона', 2)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Хэш-таблица = массив + хэш-функкция"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(33, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0])"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [0]*33 # заведём пустой массив\n",
    "len(x), x[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ f: String  -> \\{0,1,2,3,\\ldots, m\\} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def simple_hash(x):\n",
    "    alph = 'абвгдеёжзийклмнопрстуфхцчшщъыьэюя'\n",
    "    return alph.index(x[0])\n",
    "\n",
    "simple_hash('яйца')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "simple_hash('торт')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "for item in book:\n",
    "    idx = simple_hash(item[0])\n",
    "    x[idx] = item[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[60,\n",
       " 10,\n",
       " 0,\n",
       " 2,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 35,\n",
       " 35,\n",
       " 20,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 15,\n",
       " 42,\n",
       " 20,\n",
       " 10,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 16,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 0,\n",
       " 60]"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "60"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "idx = simple_hash('арбуз')\n",
    "x[idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "60"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "idx = simple_hash('арбалет')\n",
    "x[idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# O(1) тратим на поиск цены!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Хэш таблицы в питоне реализованы в виде множеств и словарей!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Словари"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Маша': 12, 'Мирослав': 1, 'Добрыня': 4}"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dct = {'Маша': 12, 'Мирослав': 1, 'Добрыня':4}\n",
    "dct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'Паша' in dct # O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dct['Маша']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Маша': 15, 'Мирослав': 1, 'Добрыня': 4}"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dct['Маша'] += 3\n",
    "dct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Маша': 15, 'Мирослав': 1, 'Добрыня': 4, 'Паша': 10}"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dct['Паша'] = 10\n",
    "dct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'Паша' in dct # O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Маша': 12, 'Мирослав': 1, 'Добрыня': 4}"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = ['Маша', 'Мирослав', 'Добрыня']\n",
    "b = [12, 1, 4]\n",
    "\n",
    "dct1 = dict(zip(a,b))\n",
    "dct1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Маша': 26, 'Мирослав': 1, 'Добрыня': 4, 'Паша': 0}"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dct2 = {'Паша':0, 'Маша': 26}\n",
    "\n",
    "# Уникальный ключ в словаре может встерится только 1 раз! \n",
    "dct1.update(dct2)\n",
    "dct1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_keys(['Маша', 'Мирослав', 'Добрыня', 'Паша'])"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dct1.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_values([26, 1, 4, 0])"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dct1.values()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_items([('Маша', 26), ('Мирослав', 1), ('Добрыня', 4), ('Паша', 0)])"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dct1.items()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Маша 26\n",
      "Мирослав 1\n",
      "Добрыня 4\n",
      "Паша 0\n"
     ]
    }
   ],
   "source": [
    "for k,v in dct1.items():\n",
    "    print(k, v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В качестве ключей могут выступать только неизменяемые штуки. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = {'Маша':[1,2,3,4], 'Даша':{42: 13, '26': False}}\n",
    "y['Даша'][42]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "unhashable type: 'list'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-100-0954fcf73f26>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0my\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m'Маша'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'Даша'\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m{\u001b[0m\u001b[0;36m42\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m13\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'26'\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m}\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: 'list'"
     ]
    }
   ],
   "source": [
    "y = {[1,2,3,4]: 'Маша', 'Даша':{42: 13, '26': False}}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Маша'"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = {(1,2,3,4): 'Маша', 'Даша':{42: 13, '26': False}}\n",
    "y[(1,2,3,4)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Множества \n",
    "\n",
    "множество - словарь без значений"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "set"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = {'Маша', 'Мирослав', 'Добрыня'}\n",
    "type(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "list"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = ['Маша','Паша','Паша','Паша']\n",
    "type(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "set"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = set(b)\n",
    "type(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Маша', 'Паша'}"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Задача:__ посчитать все уникальные имена."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = ['Маша', 'Мирослав', 'Добрыня','Маша','Паша','Паша','Паша']\n",
    "len(set(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Добрыня', 'Маша', 'Мирослав', 'Паша'}"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = {'Маша', 'Мирослав', 'Добрыня'}\n",
    "b = {'Маша','Паша'}\n",
    "\n",
    "a | b # объединение"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Маша'}"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a & b # пересечение"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Добрыня', 'Мирослав'}"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a - b # разность множеств"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Добрыня', 'Мирослав', 'Паша'}"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a ^ b # симметрическая разность"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Джон', 'Добрыня', 'Маша', 'Мирослав'}"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.add('Джон')\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Решаем задачи\n",
    "\n",
    "Дан текст. Выведите слово, которое в этом тексте встречается чаще всего. Если таких слов несколько, выведите то, которое меньше в лексикографическом порядке."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'oh': 1,\n",
       " 'you': 1,\n",
       " 'touch': 1,\n",
       " 'my': 2,\n",
       " 'tralala': 1,\n",
       " 'mmm': 1,\n",
       " 'ding': 2,\n",
       " 'dong': 1}"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text = \"oh you touch my tralala mmm my ding ding dong\"\n",
    "\n",
    "dct = {}\n",
    "for word in text.split(' '):\n",
    "#     dct[word] += 1 # KeyError: 'oh'\n",
    "    if word in dct:\n",
    "        dct[word] += 1\n",
    "    else:\n",
    "        dct[word] = 1\n",
    "\n",
    "dct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(<function __main__.<lambda>()>,\n",
       "            {'oh': 1,\n",
       "             'you': 1,\n",
       "             'touch': 1,\n",
       "             'my': 2,\n",
       "             'tralala': 1,\n",
       "             'mmm': 1,\n",
       "             'ding': 2,\n",
       "             'dong': 1})"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "text = \"oh you touch my tralala mmm my ding ding dong\"\n",
    "\n",
    "dct = defaultdict(lambda:0)\n",
    "for word in text.split(' '):\n",
    "    dct[word] += 1\n",
    "dct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(list,\n",
       "            {'oh': ['oh'],\n",
       "             'you': ['you'],\n",
       "             'touch': ['touch'],\n",
       "             'my': ['my', 'my'],\n",
       "             'tralala': ['tralala'],\n",
       "             'mmm': ['mmm'],\n",
       "             'ding': ['ding', 'ding'],\n",
       "             'dong': ['dong']})"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dct = defaultdict(list)\n",
    "for word in text.split(' '):\n",
    "    dct[word].append(word)\n",
    "dct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'oh': 1,\n",
       "         'you': 1,\n",
       "         'touch': 1,\n",
       "         'my': 2,\n",
       "         'tralala': 1,\n",
       "         'mmm': 1,\n",
       "         'ding': 2,\n",
       "         'dong': 1})"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import Counter\n",
    "\n",
    "text = \"oh you touch my tralala mmm my ding ding dong\"\n",
    "cnt = Counter(text.split(' '))\n",
    "cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('my', 2),\n",
       " ('ding', 2),\n",
       " ('oh', 1),\n",
       " ('you', 1),\n",
       " ('touch', 1),\n",
       " ('tralala', 1),\n",
       " ('mmm', 1),\n",
       " ('dong', 1)]"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = cnt.most_common()\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 145,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x_max = max(x, key=lambda w: w[1])[1]\n",
    "x_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ding'"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z = filter(lambda w: w[1] == x_max, x)\n",
    "ans = sorted(z, key=lambda w: w[0])[0][0]\n",
    "ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Очередь"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([1, 2, 3])"
      ]
     },
     "execution_count": 153,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "a = [1,2,3]\n",
    "deq = deque(a)\n",
    "deq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([1, 2, 3, 42])"
      ]
     },
     "execution_count": 154,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deq.append(42)\n",
    "deq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([54, 1, 2, 3, 42])"
      ]
     },
     "execution_count": 156,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deq.appendleft(54)\n",
    "deq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 158,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = deq.pop()\n",
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([54, 1, 2, 3])"
      ]
     },
     "execution_count": 159,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "54"
      ]
     },
     "execution_count": 160,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = deq.popleft()\n",
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([1, 2, 3])"
      ]
     },
     "execution_count": 161,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос:__ как рекурссивно обойти словарь? \n",
    "\n",
    "__Ответ:__ а вот так! Давай ещё при этом закинем все значения, которые мы получаем при обходе в очередь ради фана!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque(['Маша', 13, 4, 22])"
      ]
     },
     "execution_count": 177,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = {(1,2,3,4): 'Маша', 'Даша':{42: 13, '26': {5:4, 'fff':22}}}\n",
    "\n",
    "def iter_dict(dct, deq):\n",
    "    for k,v in dct.items():\n",
    "        if isinstance(v, dict):\n",
    "            return iter_dict(v, deq)\n",
    "        else:\n",
    "            deq.append(v)\n",
    "    return deq\n",
    "\n",
    "deq = deque()\n",
    "iter_dict(y, deq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " "
   ]
  }
 ],
 "metadata": {
  "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.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}