sem05_dict/sem05_201.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Семинар 5: бинарный поиск, хэш-таблицы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Линейный и бинарный поиск\n",
    "\n",
    "Вы - продавец в магазине. Когда покупатель что-то у вас покупает, вы проверяете стоимость товара по книге. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "book = [('яйца', 60), ('чай', 16), ('кофе', 35), ('лён', 20), \n",
    "        ('петрушка', 15), ('торт', 10), ('арбуз', 60), ('йогурт', 35), \n",
    "        ('соя', 20), ('ролтон', 42), ('бобы', 10), ('глаз дракона', 2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'йогурт'"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book[7][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "35"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book[7][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "tuple index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-53-7d36466eb99e>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mbook\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m7\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m: tuple index out of range"
     ]
    }
   ],
   "source": [
    "book[7][2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как найти сколько стоят бобы? Листать книгу, читать в ней каждую строчку до тех пор пока мы не найдём ответ. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "бобы стоят 10\n"
     ]
    }
   ],
   "source": [
    "z = 'бобы'\n",
    "\n",
    "for item in book:\n",
    "    if item[0] == z:\n",
    "        print(f'{z} стоят', item[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос:__ Если у нас всего $n$ продуктов, сколько действий нам надо будет сделать в худшем случае? \n",
    "\n",
    "__Ответ:__ Линейный поиск - $O(n)$ - в худшем случае, нужный продукт последний"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как-то долговато. Давайте попробуем ускориться. Одной из идей ускорения может быть сортировка. Если отсортировать все продукты по их названию, искать будет легче."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('чай', 16),\n",
       " ('лён', 20),\n",
       " ('соя', 20),\n",
       " ('яйца', 60),\n",
       " ('кофе', 35),\n",
       " ('торт', 10),\n",
       " ('бобы', 10),\n",
       " ('арбуз', 60),\n",
       " ('йогурт', 35),\n",
       " ('ролтон', 42),\n",
       " ('петрушка', 15),\n",
       " ('глаз дракона', 2)]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(book, key=lambda w: len(w[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = lambda x: x**2\n",
    "f(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "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": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(book)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('чай', 16),\n",
       " ('лён', 20),\n",
       " ('соя', 20),\n",
       " ('яйца', 60),\n",
       " ('кофе', 35),\n",
       " ('торт', 10),\n",
       " ('бобы', 10),\n",
       " ('арбуз', 60),\n",
       " ('йогурт', 35),\n",
       " ('ролтон', 42),\n",
       " ('петрушка', 15),\n",
       " ('глаз дракона', 2)]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(book, key=lambda x: len(x[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('яйца', 60),\n",
       " ('арбуз', 60),\n",
       " ('ролтон', 42),\n",
       " ('кофе', 35),\n",
       " ('йогурт', 35),\n",
       " ('лён', 20),\n",
       " ('соя', 20),\n",
       " ('чай', 16),\n",
       " ('петрушка', 15),\n",
       " ('торт', 10),\n",
       " ('бобы', 10),\n",
       " ('глаз дракона', 2)]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(book, key=lambda x: x[1], reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('яйца', 60),\n",
       " ('арбуз', 60),\n",
       " ('ролтон', 42),\n",
       " ('кофе', 35),\n",
       " ('йогурт', 35),\n",
       " ('лён', 20),\n",
       " ('соя', 20),\n",
       " ('чай', 16),\n",
       " ('петрушка', 15),\n",
       " ('торт', 10),\n",
       " ('бобы', 10),\n",
       " ('глаз дракона', 2)]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f(x):\n",
    "    return x[1]\n",
    "\n",
    "sorted(book, key=f, reverse=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Можно договориться, что мы всегда будем хранить книгу отсортированной, тогда товар будет легко найти бинарным поиском"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Будем открывать книгу в середине. Там буква \"п\". Нам нужна буква \"б\", она левее буквы \"п\". Откроем серидну левой части книги, там буква \"й\", нам нужно еще левее, снова откроем середину. Будем так делать до тех пор, пока не найдём бобы. Такая процедура будет работать быстрее, она называется __бинарный поиск.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "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": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book = sorted(book, key=lambda w: w[0])\n",
    "book"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "def binary_search(lst, z):\n",
    "    low = 0\n",
    "    high = len(lst) - 1\n",
    "    \n",
    "    while low <= high:\n",
    "        mid =(low + high) // 2\n",
    "        guess = lst[mid]\n",
    "        \n",
    "        if guess[0] == z:\n",
    "            return mid\n",
    "        if guess[0] > z:\n",
    "            high = mid - 1\n",
    "        else:\n",
    "            low = mid + 1\n",
    "    return None \n",
    "\n",
    "idx = binary_search(book, 'бобы')\n",
    "print(idx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('бобы', 10)"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book[idx]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос:__ Если у нас всего $n$ продуктов, сколько действий нам надо будет сделать в худшем случае? \n",
    "\n",
    "__Ответ:__ В худшем случае нужный продукт мы найдём самы последним, и он останется в нашем массиве один. Каждый раз мы урезаем массив в два раза. Получается уравнение:\n",
    "\n",
    "$$\n",
    "\\frac{n}{2^{k}} = 1,\n",
    "$$\n",
    "\n",
    "где $k$ - число действий, которое мы сделали (разбиение массива на 2 части, константой пренебрегаем).\n",
    "\n",
    "Решаем уравнение относительно $k$, получаем\n",
    "\n",
    "$$\n",
    "k = \\log_2{n}.\n",
    "$$\n",
    "\n",
    "Обычно основанием пренебрегают, так как мы умножением логарифма на констунту легко можем поменять его:\n",
    "\n",
    "$$\n",
    "\\log_a b = \\frac{\\log_c b}{\\log_c a}.\n",
    "$$\n",
    "\n",
    "Поэтому обычно пишут, что \n",
    "\n",
    "$$\n",
    "T(n) = k = O(\\log n)\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Линейный поиск - O(n) - в худшем случае \n",
    "# Бинарный поиск - O(log(n)) в худшем случае"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Что такое хэш-таблица? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Всё ещё долго. А можно ещё быстрее? Конечно можно. Давайте наймём помощницу по имени Алиса и заставим её выучить всю книгу с продуктами и ценами наизусть. Тогда мы сможем задавать ей вопрос и моментально будем получать ответ на него. Просто чудо, а не помощница! Где бы взять такую... \n",
    "\n",
    "Попробуем создать её из тех структур данных, которые мы уже знаем. А именно: из массивов. Для этого будем использовать __хеш-функцию.__ Хеш-функция - это такая функция, которая на вход получает строку и возвращает число. Они и поможет нам создать свою Алису."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "book = [('яйца', 60), ('чай', 16), ('кофе', 35), ('лён', 20), \n",
    "        ('петрушка', 15), ('торт', 10), ('арбуз', 60), ('йогурт', 35), \n",
    "        ('соя', 20), ('ролтон', 42), ('бобы', 10), ('глаз дракона', 2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "book.index(('соя', 20)) # линейный поиск "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Хэш-таблица__ - это комбинация из массива и хэш-функции. __Хэш-функция__ - это любое правило, по которомму можно легко и быстро превратить входные данные в целое положительное число.\n",
    "\n",
    "Пусть наша хэш-функция возвращает номер первой буквы слова в алфавите. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 40,
     "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": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "simple_hash('глаз дракона')"
   ]
  },
  {
   "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": [
    "Положим в массив $x$ на $32$ позицию цену на яйца. По аналогии сделаем со всеми продуктами и их ценами. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "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": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for food, price in book:\n",
    "    x[simple_hash(food)] = price\n",
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Хэш-функция в нашем примере связывает каждое название с одним индексом. На месте этого индекса в векторе $x$ и лежит нужная цена. __Поздравляю, мы создали свою Алису!__\n",
    "\n",
    "А теперь к нам приходит клиент и спрашивает: \"А сколько стоит торт?\" Мы легко можем ответить на его вопрос: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ind = simple_hash('торт')\n",
    "ind"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x[ind]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И мы делаем это моментально, без перебора как в первых двух случаях. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "А если клиент спросит \"А сколько стоит тигр?\". Упс..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ind = simple_hash('тигр')\n",
    "x[ind]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Поиск в хэш-таблице работает за O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопросы:__\n",
    "\n",
    "- Понятное дело, что на практике хеш-функции устроены сложнее, у той функции, которую мы тут использовали есть куча проблем: какие это проблемы? \n",
    "- Как можно попытаться решить эти проблемы? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Немного подробнее можно почитать про это в [грокаем алгоритмы](https://disk.yandex.ru/i/VUEpPKLb3ZH2Bz)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Словари и множества - хэш-таблицы в питоне\n",
    "\n",
    "В python хэш-таблицы реализованы в виде словарей и множеств. Давайте с ними познакомимся. \n",
    "\n",
    "## Множества\n",
    "\n",
    "Все элементы уникальны, порядок элементов никак не гарантируется."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 2, 3, 4}"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = {1,2,3,4,4,3} # [] - листы  {} - словари и множества\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 1, 5, 6, 6, 7, 7]"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = [4,1,5,6,6,7,7]\n",
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 4, 5, 6, 7}"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = set(b)\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 2, 3, 4, 5, 6, 7}"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Операции\n",
    "a | d # объединение"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 4}"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a & d # пересечение"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{2, 3}"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a - d # разность"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 4, 5, 6, 7, 42}"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.add(42) # добавить новый элемент\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Это работает быстрее!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[254407, 604743, 79803, 298908, 464207, 735833, 875892, 857680, 181115, 261169]"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "x = [random.randint(1,1000000) for i in range(10000)]\n",
    "x[100:110]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(9947, 9947)"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = list(set(x)) # выкинул неуникальные, а потом вернул структуру листа\n",
    "y = set(x)\n",
    "len(x), len(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "691538 in x # O(n) линейный поиск по массиву"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "691538 in y # O(1) поиск в хэш-таблица"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Много-много раз попробуемм сделать одно и то же и замерим время работы."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12.6 µs ± 219 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "691538 in x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55.6 ns ± 0.562 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "691538 in y "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Словари\n",
    "\n",
    "То же самое, что и множества, но с ключами и значениями!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Маша': 10, 'Мирослав': 2, 'Тейлор': 12}"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = {\"Маша\": 10, \"Мирослав\": 2, \"Тейлор\": 12}\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 152,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d['Маша']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 153,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'Паша' in d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Маша': 10, 'Мирослав': 2, 'Тейлор': 12, 'Паша': 1}"
      ]
     },
     "execution_count": 154,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d['Паша'] = 1\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Маша': 10, 'Мирослав': 2, 'Тейлор': 12, 'Паша': 10}"
      ]
     },
     "execution_count": 155,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d['Паша'] += 9\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 156,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'Паша' in d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Маша': 12, 'Мирослав': 2, 'Тейлор': 12, 'Паша': 10}"
      ]
     },
     "execution_count": 157,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d['Маша'] = 12 # каждый ключ - уникальная штука\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{4: [7, 8.5, 'Маша'], 'Рома': 10, '5.5': {2: 4, 'g': 7}}"
      ]
     },
     "execution_count": 163,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ddd = {4: [7,8.5, 'Маша'], 'Рома': 10, '5.5': {2:4, 'g':7}}\n",
    "ddd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 165,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ddd['5.5']['g']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{4: [7, 8.5, 'Маша'], 'Рома': 10, '5.5': 4}"
      ]
     },
     "execution_count": 166,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ddd['5.5'] = 4\n",
    "ddd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задачка:\n",
    "\n",
    "Дан текст. Выведите слово, которое в этом тексте встречается чаще всего. Если таких слов несколько, выведите то, которое меньше в лексикографическом порядке."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'oh': 1,\n",
       " 'you': 1,\n",
       " 'a': 2,\n",
       " 'touch': 1,\n",
       " 'my': 2,\n",
       " 'tralala': 1,\n",
       " 'mmm': 1,\n",
       " 'ding': 2,\n",
       " 'dong': 1}"
      ]
     },
     "execution_count": 158,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text = \"oh you a a touch my tralala mmm my ding ding dong\"\n",
    "\n",
    "d = {}\n",
    "\n",
    "for word in text.split(' '):\n",
    "    if word in d:\n",
    "        d[word] = d[word] + 1\n",
    "    else:\n",
    "        d[word] = 1\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_keys(['oh', 'you', 'a', 'touch', 'my', 'tralala', 'mmm', 'ding', 'dong'])"
      ]
     },
     "execution_count": 159,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_values([1, 1, 2, 1, 2, 1, 1, 2, 1])"
      ]
     },
     "execution_count": 160,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.values()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_items([('oh', 1), ('you', 1), ('a', 2), ('touch', 1), ('my', 2), ('tralala', 1), ('mmm', 1), ('ding', 2), ('dong', 1)])"
      ]
     },
     "execution_count": 123,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.items()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('a', 2), ('ding', 2), ('my', 2)]"
      ]
     },
     "execution_count": 167,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x_max = max(d.items(), key=lambda w: w[1])[1]\n",
    "\n",
    "x = filter(lambda w: w[1]==x_max, d.items())\n",
    "\n",
    "x = sorted(x, key=lambda w: w[0])\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 169,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x[0][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Упрощаем код! В модуле `collecctions` собраны разные удобные структуры данных."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyError",
     "evalue": "'oh'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-172-7612b20d0b34>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mword\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mtext\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msplit\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[0m\n\u001b[0;32m----> 6\u001b[0;31m     \u001b[0md\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mword\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mword\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\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      7\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyError\u001b[0m: 'oh'"
     ]
    }
   ],
   "source": [
    "text = \"oh you a a touch my tralala mmm my ding ding dong\"\n",
    "\n",
    "d = {}\n",
    "\n",
    "for word in text.split(' '):\n",
    "    d[word] = d[word] + 1\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(<function __main__.<lambda>()>, {})"
      ]
     },
     "execution_count": 174,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "d = defaultdict(lambda: 0)\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(<function __main__.<lambda>()>,\n",
       "            {'oh': 1,\n",
       "             'you': 1,\n",
       "             'a': 2,\n",
       "             'touch': 1,\n",
       "             'my': 2,\n",
       "             'tralala': 1,\n",
       "             'mmm': 1,\n",
       "             'ding': 2,\n",
       "             'dong': 1})"
      ]
     },
     "execution_count": 175,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text = \"oh you a a touch my tralala mmm my ding ding dong\"\n",
    "\n",
    "for word in text.split(' '):\n",
    "    d[word] = d[word] + 1\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(list,\n",
       "            {'oh': ['oh'],\n",
       "             'you': ['you'],\n",
       "             'a': ['a', 'a'],\n",
       "             'touch': ['touch'],\n",
       "             'my': ['my', 'my'],\n",
       "             'tralala': ['tralala'],\n",
       "             'mmm': ['mmm'],\n",
       "             'ding': ['ding', 'ding'],\n",
       "             'dong': ['dong']})"
      ]
     },
     "execution_count": 176,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text = \"oh you a a touch my tralala mmm my ding ding dong\"\n",
    "\n",
    "d = defaultdict(list)\n",
    "\n",
    "for word in text.split(' '):\n",
    "    d[word].append(word)\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 192,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import Counter\n",
    "\n",
    "text = \"oh you a a touch my tralala mmm my ding ding dong\"\n",
    "\n",
    "cnt = Counter(text.split(' '))\n",
    "x = cnt.most_common()\n",
    "x_max = x[0][1]\n",
    "\n",
    "x = filter(lambda w: w[1]==x_max, x)\n",
    "x = sorted(x, key=lambda w: w[0])\n",
    "x[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([12, 3, 4])"
      ]
     },
     "execution_count": 198,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "deq = deque([12,3,4])\n",
    "deq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([12, 3, 4, 17])"
      ]
     },
     "execution_count": 199,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deq.append(17)\n",
    "deq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([5, 12, 3, 4, 17])"
      ]
     },
     "execution_count": 200,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deq.appendleft(5)\n",
    "deq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 201,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cur = deq.popleft()\n",
    "cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([12, 3, 4, 17])"
      ]
     },
     "execution_count": 202,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Через append докидывать в очередь новых людей\n",
    "# Через popleft убирать их из неё"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 203,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 203,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [1,2,3,4]\n",
    "x.append(5)\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'list' object has no attribute 'appendleft'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-204-e38c5410e9b0>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappendleft\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m: 'list' object has no attribute 'appendleft'"
     ]
    }
   ],
   "source": [
    "x.appendleft(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 205,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 206,
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'list' object has no attribute 'popleft'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-206-443b71f5b104>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpopleft\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;31mAttributeError\u001b[0m: 'list' object has no attribute 'popleft'"
     ]
    }
   ],
   "source": [
    "x.popleft()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://docs.python.org/3/library/collections.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Вопросы"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [10,1,2,-5,-3,0] # лист изменяемая структура, его можно изменять методами\n",
    "x.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-5, -3, 0, 1, 2, 10]"
      ]
     },
     "execution_count": 209,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос:__ можно ли самому писать такие структуры? \n",
    "\n",
    "__Ответ:__ Да, можно. Это обычно делают с помощью классов. Посмотрим на это на консультациях."
   ]
  },
  {
   "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
}