sem05_dict/sem05_dict_and_set.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center> Анализ данных на Python </center>\n",
    "\n",
    "# Семинар 5. Словари да множества\n",
    "\n",
    "Поговорим про словари, множества, хэш-таблицы и другие разные штуки! "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Что такое Хэш-таблица? \n",
    "\n",
    "Вы - продавец в магазине. Когда покупатель что-то у вас покупает, вы проверяете стоимость товара по книге. "
   ]
  },
  {
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 'бобы'\n",
    "\n",
    "for item in book:\n",
    "    if item[0] == x:\n",
    "        print(item[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос:__ Если у нас всего $n$ продуктов, сколько действий нам надо будет сделать в худшем случае? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как-то долговато. Давайте попробуем ускориться. Одной из идей ускорения может быть сортировка. Если отсортировать все продукты по их названию, искать будет легче. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "book = sorted(book, key=lambda w: w[0])\n",
    "book"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Будем открывать книгу в середине. Там буква \"п\". Нам нужна буква \"б\", она левее буквы \"п\". Откроем серидну левой части книги, там буква \"й\", нам нужно еще левее, снова откроем середину. Будем так делать до тех пор, пока не найдём бобы. Такая процедура будет работать быстрее, она называется __бинарный поиск.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Попытайтесь на досуге написать такой поиск самостоятельно :) \n",
    "\n",
    "    # ┬─┬ ノ( ゜-゜ノ)       Писать код самому? \n",
    "    \n",
    "    # (╯° □°)╯︵ ┻━┻ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос:__ Если у нас всего $n$ продуктов, сколько действий нам надо будет сделать в худшем случае? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Всё ещё долго. А можно ещё быстрее? Конечно можно. Давайте наймём помощницу по имени Алиса и заставим её выучить всю книгу с продуктами и ценами наизусть. Тогда мы сможем задавать ей вопрос и моментально будем получать ответ на него. Просто чудо, а не помощница! Где бы взять такую... \n",
    "\n",
    "Попробуем создать её из тех структур данных, которые мы уже знаем. А именно: из массивов. Для этого будем использовать __хеш-функцию.__ Хеш-функция - это такая функция, которая на вход получает строку и возвращает число. Они и поможет нам создать свою Алису."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [0]*33 # заведём пустой массив\n",
    "x[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пусть наша хэш-функция возвращает номер первой буквы слова в алфавите. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def simple_hash(x):\n",
    "    alph = 'абвгдеёжзийклмнопрстуфхцчшщъыьэюя'\n",
    "    return alph.index(x[0])\n",
    "\n",
    "simple_hash('яйца')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Положим в массив $x$ на $32$ позицию цену на яйца. По аналогии сделаем со всеми продуктами и их ценами. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for food, price in book:\n",
    "    x[simple_hash(food)] = price\n",
    "    \n",
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Хэщ-функция в нашем примере связывает каждое название с одним индексом. На месте этого индекса в векторе $x$ и лежит нужная цена. __Поздравляю, мы создали свою Алису!__\n",
    "\n",
    "А теперь к нам приходит клиент и спрашивает: \"А сколько стоит торт?\" Мы легко можем ответить на его вопрос: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ind = simple_hash('торт')\n",
    "x[ind]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И мы делаем это моментально, без перебора как в первых двух случаях. \n",
    "\n",
    "__Вопросы:__\n",
    "\n",
    "- Понятное дело, что на практике хеш-функции устроены сложнее, у той функции, которую мы тут использовали есть куча проблем: какие это проблемы? \n",
    "- Как можно попытаться решить эти проблемы? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В python хэш-таблицы реализованы в виде словарей и множеств. Давайте с ними познакомимся. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Работаем со словарями"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "product = ['яйца', 'чай', 'кофе', 'банан', 'петрушка', 'сода', \n",
    "           'яблочко', 'йогурт', 'соя', 'беозар', 'бобы', 'печень дракона']\n",
    "\n",
    "price = [60, 16, 35, 20, 15, 10, 60, 35, 20, 42, 10, 2]\n",
    "\n",
    "zip(product, price)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list( zip(product, price) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "book_dict = dict(zip(product, price))\n",
    "book_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "book_dict['яйца'] = 70  # цены растут! \n",
    "book_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "book_dict['дефлопе'] = 500 # ура! новый продукт! \n",
    "book_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = book_dict.pop('чай') # чай кончился :(\n",
    "book_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "book_dict['чай'] # мужчинаааа, говорю же у нас нет чаааяяяя"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "book_dict.get('чай', 'нет такого у нас') # если нет, отдавай второе значение"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'чай' in book_dict  # девушка девушка, а у вас есть чай?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'кофе' in book_dict  # а кофе?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'танцы' in book_dict  # а может потанцуем? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "book_dict.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "book_dict.values()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "book_dict.items()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for k, v in book_dict.items():\n",
    "    print(f\"Продукт {k} стоит {v} рублей\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ещё немного магии:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[i for i in range(2, 20, 3)]       # список"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "{i: i**3 for i in range(2, 20, 3)} # словарь "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(i for i in range(2, 20, 3)) # не показывает ((((( "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "range(1, 10)       # тоже не показывает"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(range(1,10))  # показал !!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос:__ а почему он себя так ведёт капризно? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Множества\n",
    "\n",
    "Это то же самое, что и словари, но без значений. Только ключи."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fruits = {\"banana\", \"apple\", \"orange\",  \"orange\"}\n",
    "fruits  # ты куда один апельсин дел?!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fruits = [\"banana\", \"apple\", \"orange\",  \"orange\",  \"apple\",  \"apple\",  \"apple\"]\n",
    "set(fruits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_fruits = {\"apple\", \"orange\"}\n",
    "your_fruits = {\"orange\", \"banana\", \"pear\"}\n",
    "\n",
    "my_fruits | your_fruits # объединение множеств"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_fruits & your_fruits  # пересечение множеств"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_fruits - your_fruits  # разность множеств"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'orange' in my_fruits "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "your_fruits.remove(\"banana\")  # удаление\n",
    "your_fruits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "your_fruits.add(\"banana\")  # добавление\n",
    "your_fruits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Задачки\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_problem_13(func, test_data):\n",
    "    for inputs, true_answer in test_data:\n",
    "        answer = func(*inputs)\n",
    "        assert answer == true_answer, f'Expected {true_answer}, got {answer}. Input: {inputs}'\n",
    "    print(\"OK!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_problem(func, test_data):\n",
    "    for inputs, true_answer in test_data:\n",
    "        answer = func(inputs)\n",
    "        assert answer == true_answer, f'Expected {true_answer}, got {answer}. Input: {inputs}'\n",
    "    print(\"OK!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задачка 1: [камешки](https://leetcode.com/problems/jewels-and-stones/)\n",
    "\n",
    "У Дори в глубинах океана есть кучка камней. Часть камней из этой кучки драгоценные. Недавно она пересчитала все драгоценные и забыла сколько их. Чтобы больше не забывать, Дори решила написать на питоне функцию, которая будет считать камни за неё.\n",
    "\n",
    "Напишите на python функцию, которая принимает на вход список драгоценных камней $J$ и список камней, которые есть у Дори $S$. На выход функция возвращает число драгоценных камней в запасах Дори.\n",
    "\n",
    "__Примеры:__ \n",
    "\n",
    "> Input: J = \"aA\", S = \"aAAbbbb\" <br />\n",
    "Output: 3\n",
    "\n",
    "Тут драгоценными считаются камни a и A. У Дори есть камни aAAbbbb. Среди них три драгоценных, aAA.\n",
    "\n",
    ">Input: J = \"z\", S = \"ZZ\" <br />\n",
    "Output: 0\n",
    "\n",
    "Драгоценными мы считаем только камень z. У Дори два камня, оба обычные."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def numJewelsInStones(J, S):\n",
    "    \n",
    "    ### ╰( ͡° ͜ʖ ͡° )つ▬▬ι═══════  bzzzzzzzzzz\n",
    "    # will the code be with you\n",
    "\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NUM_JEWELS_IN_STONES_TESTS_DATA = [\n",
    "        ((\"aA\", \"aAAbbbb\"), 3),\n",
    "        ((\"z\",\"ZZ\"),0)\n",
    "    ]\n",
    "test_problem_13(numJewelsInStones, NUM_JEWELS_IN_STONES_TESTS_DATA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Пара слов об эффективности:__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import random\n",
    "n_obs = 10**6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist = [random() for _ in range(n_obs)]\n",
    "myset = set(mylist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "0.5 in mylist  # список"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "0.5 in myset   # множество"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задачка 2: слова\n",
    "\n",
    "Напишите функцию `stats(s)`, принимающую на вход строку `s`, содержащую слова, разделённые пробелами, и находящую самое часто встречающееся слово. Если такое слово одно, верните его, если их несколько, верните список, отсортированный в лексикографическом порядке.\n",
    "\n",
    "Например: `stats(\"hello hello world\")` должна вернуть строчку `\"hello\"`, а `stats(\"a a b b c\")` должна вернуть список `['a','b']`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stats(s):\n",
    "    \n",
    "    ### ╰( ͡° ͜ʖ ͡° )つ▬▬ι═══════  bzzzzzzzzzz\n",
    "    # will the code be with you\n",
    "    \n",
    "    return ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "STATS_TESTS_DATA = [\n",
    "        (\"hello hello world\", \"hello\"),\n",
    "        (\"a a b b c\", ['a','b'])\n",
    "    ]\n",
    "test_problem(stats, STATS_TESTS_DATA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задачка 3: сумма двух \n",
    "\n",
    "Дан массив из целых чисел `nums` и ещё одно целое число `target`.  Найдите все такие пары чисел из массива `nums`, которые в сумме дают число `target`. Выведите на экран их индексы. Одно и то же число использовать при подсчёте суммы дважды нельзя. Попытайтесь решить эту задачу максимально эффективно. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def two_sum_fast(nums, target):\n",
    "    \n",
    "    # ┬─┬ ノ( ゜-゜ノ)\n",
    "    \n",
    "    # (╯° □°)╯︵ ┻━┻\n",
    "    \n",
    "    return ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "TWO_SUM_TESTS_DATA = [\n",
    "    (([2, 7, 11, 15], 9), [(0, 1)]),\n",
    "]\n",
    "\n",
    "test_problem_13(two_sum_fast, TWO_SUM_TESTS_DATA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задачка 4:  магазин\n",
    "\n",
    "Вам предостоит обработать базу данных о продажах некоторого интернет-магазина. База данных представляет собой набор кортежей, в каждом кортеже три элемента: (Покупатель, товар, количество), где Покупатель — имя покупателя (строка без пробелов), товар — название товара (строка без пробелов), количество — количество приобретенных единиц товара.\n",
    "\n",
    "Создайте словарь, ключами которого являются имена покупателей, а значениями — словари, ключами которых являются названия товаров, а значениями — количество единиц этого товара, которые купил этот покупатель.\n",
    "\n",
    "Напишите функцию `aggregate`, принимающую некоторое количество набор кортежей из базы данных и возвращающую сводную информацию в виде словаря."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def aggregate(names):\n",
    "    \n",
    "    # ┬─┬ ノ( ゜-゜ノ)\n",
    "    \n",
    "    # (╯° □°)╯︵ ┻━┻\n",
    "\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "AGG_TESTS_DATA = [\n",
    "    ([(\"Petrov\",\"pens\",5), (\"Ivanov\",\"marker\",3), (\"Ivanov\",\"paper\",7), \n",
    "      (\"Petrov\",\"envelope\",20), (\"Ivanov\",\"envelope\",5)], \n",
    "     {'Petrov': {'pens': 5, 'envelope': 20}, \n",
    "      'Ivanov': {'marker': 3, 'paper': 7, 'envelope': 5}}),\n",
    "    \n",
    "    ([(\"Ivanov\",\"aaa\",1), (\"Petrov\",\"aaa\",2), (\"Sidorov\",\"aaa\",3), (\"Ivanov\",\"aaa\",6), \n",
    "      (\"Petrov\",\"aaa\",7), (\"Sidorov\",\"aaa\",8), (\"Ivanov\",\"bbb\",3), (\"Petrov\",\"bbb\",7), \n",
    "      (\"Sidorov\",\"aaa\",345), (\"Ivanov\",\"ccc\",45), (\"Petrov\",\"ddd\",34), \n",
    "      (\"Ziborov\",\"eee\",234), (\"Ivanov\",\"aaa\",45)],\n",
    "    {'Ivanov': {'aaa': 52, 'bbb': 3, 'ccc': 45},\n",
    "     'Petrov': {'aaa': 9, 'bbb': 7, 'ddd': 34},\n",
    "     'Sidorov': {'aaa': 356},\n",
    "     'Ziborov': {'eee': 234}})\n",
    "]\n",
    "test_problem(aggregate, AGG_TESTS_DATA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://steemitimages.com/0x0/https://media.makeameme.org/created/repeat-repeat-repeat-5984a6.jpg\" height=\"400\" width=\"400\">"
   ]
  },
  {
   "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.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}