08 Итераторы генераторы itertools.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Программирование на Python (SCS)](https://compscicenter.ru/courses/python/2015-autumn/classes/)\n",
    "\n",
    "## Лектор Сергей Лебедев:  sergei.a.lebedev@gmail.com\n",
    "\n",
    "\n",
    "|     **Дата**     |   **Название**  |     |\n",
    "|:----------------:|:---------------:|:-----------------:|\n",
    "| 26 октября 2015      |    Итераторы, генераторы itertools| \n",
    "\n",
    "# 8. Итераторы, генераторы, itertools\n",
    "\n",
    "Напоминание: оператор **for** в Python работает с любой\n",
    "последовательностью."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  1           0 SETUP_LOOP              20 (to 22)\n",
      "              2 LOAD_NAME                0 (xs)\n",
      "              4 GET_ITER\n",
      "        >>    6 FOR_ITER                12 (to 20)\n",
      "              8 STORE_NAME               1 (x)\n",
      "             10 LOAD_NAME                2 (do_something)\n",
      "             12 LOAD_NAME                3 (name)\n",
      "             14 CALL_FUNCTION            1\n",
      "             16 POP_TOP\n",
      "             18 JUMP_ABSOLUTE            6\n",
      "        >>   20 POP_BLOCK\n",
      "        >>   22 LOAD_CONST               0 (None)\n",
      "             24 RETURN_VALUE\n"
     ]
    }
   ],
   "source": [
    "import dis\n",
    "dis.dis(\"for x in xs: do_something(name)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Инструкция **GET_ITER** вызывает у аргумента оператора **for**\n",
    "метод `__iter__`, который возвращает итератор.\n",
    "- Инструкция FOR_ITER вызывает метод `__next__` у\n",
    "итератора до тех пор, пока не будет поднято исключение <font color=red>**StopIteration**</font>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 2. Протокол итераторов\n",
    "\n",
    " Протокол итераторов состоит из двух методов:\n",
    "- Метод `__iter__` возвращает экземпляр класса,\n",
    "реализующего протокол итераторов, например, **self**.\n",
    "- Метод `__next__` возвращает следующий по порядку\n",
    "элемент итератора. Если такого элемента нет, то метод\n",
    "должен поднять исключение <font color=red>**StopIteration**</font>.\n",
    "\n",
    "\n",
    " Важный инвариант метода `__next__`: если метод поднял\n",
    "исключение <font color=red>**StopIteration**</font>, то все последующие вызовы\n",
    "метода `__next__` тоже должны поднимать исключение.\n",
    "\n",
    " В отличие от, например, Java в Python **iterator** также\n",
    "является **iterable**.\n",
    "\n",
    "**Iterable** - то, что реализует iter()\n",
    "```\n",
    "Iterable is an object, which one can iterate over. It generates an Iterator when passed to iter() method. \n",
    "```\n",
    "\n",
    "**Iterator** - то, что релазует iter() и next()\n",
    "```\n",
    "Iterator is an object, which is used to iterate over an iterable object using __next__() method. Iterators have __next__() method, which returns the next item of the object.\n",
    "\n",
    "Note that every iterator is also an iterable, but not every iterable is an iterator. For example, a list is iterable but a list is not an iterator. An iterator can be created from an iterable by using the function iter(). To make this possible, the class of an object needs either a method __iter__, which returns an iterator, or a __getitem__ method with sequential indexes starting with 0.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 3. Коллекции и итераторы\n",
    "\n",
    "Для коллекций обычно нет смысла реализовывать\n",
    "протокол итераторов целиком, достаточно реализовать\n",
    "только метод `__iter__`.\n",
    "\n",
    " Иногда элементы коллекции можно перечислить более\n",
    "чем одним способом. В этом случае удобно реализовывать\n",
    "дополнительные методы, возвращающие итераторы"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryTree:\n",
    "    def __iter__(self):\n",
    "        return self.inorder_iter()\n",
    "    def preorder_iter(self):\n",
    "        # ...\n",
    "    def inorder_iter(self):\n",
    "        return InOrderIterator(self)\n",
    "    def postorder_iter(self):\n",
    "        # ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 4. Функции iter и next\n",
    " У функции `iter` две формы вызова:\n",
    "- принимает итератор и вызывает у него метод `__iter__`,\n",
    "- принимает функцию и терминальное значение и вызывает\n",
    "функцию до тех пор, пока она не вернёт нужное значение\n",
    "\n",
    "http://bit.ly/beautiful-python\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# читаем файл до конца порциями и обрабатываем каждую часть\n",
    "# на помощь приходят Partial и iter\n",
    "from functools import partial\n",
    "    with open(path, \"rb\") as handle:\n",
    "        read_block = partial(handle.read, 64)\n",
    "        for block in iter(read_block, \"\"):\n",
    "            do_something(block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Функция next принимает итератор и вызывает у него\n",
    "метод __next__. Можно также указать значение, которое\n",
    "нужно вернуть в случае возникновения исключения\n",
    "<font color=red>**StopIteration**</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(iter([1, 2, 3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(iter([]), 42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 5. “Семантика” оператора for\n",
    "\n",
    "Напоминание:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in xs:\n",
    "    do_something(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Процесс исполнения оператора `for` можно концептуально\n",
    "записать так:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "it = iter(xs)\n",
    "while True:\n",
    "    try:\n",
    "        x = next(it)\n",
    "    except StopIteration:\n",
    "        break\n",
    "    do_something(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 6. Протокол итераторов и операторы in и not in\n",
    "Операторы `in` и `not in` используют “магический” метод\n",
    "`__contains__`, который возвращает **True**, если переданный\n",
    "элемент содержится в экземпляре класса.\n",
    "- По умолчанию метод `__contains__` реализован через\n",
    "протокол итераторов:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class object:\n",
    "    # ...\n",
    "    def __contains__(self, target):\n",
    "        for item in self:\n",
    "            if item == target:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "id = Identity()  # -реализован на следующем слайде\n",
    "5 in id          # ≡ id.__contains__(5)\n",
    "42 not in id     # ≡ not id.__contains__(42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 7. Протокол итераторов и реализация “по умолчанию”\n",
    "В Python предусмотрен упрощённый вариант реализации\n",
    "протокола итераторов с использованием метода\n",
    "`__getitem__`.\n",
    "\n",
    " Метод `__getitem__` принимает один аргумент — индекс\n",
    "элемента в последовательности и:\n",
    "- либо возвращает элемент, соответствующий индексу,\n",
    "- либо поднимает **IndexError**, если элемента с таким\n",
    "индексом нет.\n",
    "\n",
    "После каждого обращения `__getitem__` увеличивает idx на 1, генерируя тем самым итератор по умолчанию:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 127,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Identity:\n",
    "    def __getitem__(self, idx):\n",
    "        if idx > 5:\n",
    "            raise IndexError(idx)\n",
    "        return idx\n",
    "list(Identity())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 8. “Семантика” упрощённого протокола итераторов: seq_iter\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [],
   "source": [
    "class seq_iter:\n",
    "    def __init__(self, instance):\n",
    "        self.instance = instance\n",
    "        self.idx = 0\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "    def __next__(self):\n",
    "        try:\n",
    "            res = self.instance[self.idx]\n",
    "        except IndexError:\n",
    "            raise StopIteration\n",
    "        self.idx += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд  9. “Семантика” упрощённого протокола итераторов: object\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class object:\n",
    "# ...\n",
    "    def __iter__(self):\n",
    "        if not hasattr(self, \"__getitem__\"):\n",
    "            cls = self.__class__\n",
    "            msg = \"{} object is not iterable\"\n",
    "            raise TypeError(msg.format(cls.__name__))\n",
    "        return seq_iter(self)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 10. Резюме: итераторы\n",
    "В Python `iterator` также является `iterable`.\n",
    "- Итератор — это экземпляр класса, который реализует два\n",
    "метода `__init__` и `__next__`.\n",
    "- Альтернативно можно воспользоваться реализацией этих\n",
    "методов по умолчанию и определить метод `__getitem__`.\n",
    "- Протокол итераторов используется:\n",
    ">- оператором **for**,\n",
    ">- операторами **in** и **not in**.\n",
    "- Протокол итераторов реализуется всеми встроенными\n",
    "коллекциями, а также, например, файлами и объектами\n",
    "типа **map**, **filter** и **zip**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 11. Что такое генератор?\n",
    "http://python.org/dev/peps/pep-0255\n",
    "\n",
    "Генератор — это функция, которая использует не только\n",
    "оператор **return**, но и оператор **yield**.\n",
    "- В результате выполнения оператора **yield** работа функции\n",
    "приостанавливается, а не прерывается, как при\n",
    "использовании оператора **return**.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [],
   "source": [
    "def g():\n",
    "    print(\"Started\")\n",
    "    x = 42\n",
    "    yield x\n",
    "    x += 1\n",
    "    yield x\n",
    "    print(\"Done\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function"
      ]
     },
     "execution_count": 131,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(g)  # - g это функция"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "generator"
      ]
     },
     "execution_count": 132,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gen = g()\n",
    "type(gen)  # вызов функции возвращает генератор!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Started\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(gen)  # next \"проматывает\" генератор до 1-го yield и возвращает значение х"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "43"
      ]
     },
     "execution_count": 134,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(gen)  # - \"промотка\" до следующего yield "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Done\n"
     ]
    },
    {
     "ename": "StopIteration",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m                             Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-135-6e72e47198db>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mnext\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mgen\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(gen)   # \"промотка\" до конца, который, как в итераторе вызывает \n",
    "            # StopIteration, если значения закончились"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 12. Примеры генераторов: unique"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object unique at 0x05915060>"
      ]
     },
     "execution_count": 139,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def unique(iterable, seen=None):\n",
    "    seen = set(seen or [])\n",
    "    for item in iterable:\n",
    "        if item not in seen:\n",
    "            seen.add(item)\n",
    "            yield item\n",
    "xs = [1, 1, 2, 3, 4]\n",
    "unique(xs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 140,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(unique(xs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 in unique(xs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Исчерпывание итератора свойственно также и генераторам:\n",
    "def g():\n",
    "    for i in range(5):\n",
    "        print(i)\n",
    "        yield i\n",
    "gen = g()\n",
    "\n",
    "2 in gen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "4\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[3, 4]"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(gen)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 13. Примеры генераторов: map\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object map at 0x05915750>"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def map(func, iterable, *rest):\n",
    "#     zip склеит последовательности аргументов в кортежи аргументов\n",
    "    for args in zip(iterable, *rest):\n",
    "        yield func(*args)  # генерация результатов ф-ии по кортежам арг-ов\n",
    "        \n",
    "xs = range(5)\n",
    "map(lambda x: x*x, xs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16]"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(lambda x: x * x, xs))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "9 in map(lambda x: x * x, xs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 14. Примеры генераторов: chain\n",
    "Конкатенация для людей, думающих о использовании памяти - перечисляет все итерабл:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object chain at 0x05915510>"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def chain(*iterables):\n",
    "    for iterable in iterables:\n",
    "        for item in iterable:\n",
    "            yield item\n",
    "xs = range(3)\n",
    "ys = [42]\n",
    "chain(xs, ys)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 42]"
      ]
     },
     "execution_count": 152,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(chain(xs, ys))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 153,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "42 in chain(xs, ys)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 15. Примеры генераторов: count и enumerate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count(start=0):\n",
    "    while True:\n",
    "        yield start\n",
    "        start += 1\n",
    "next(count())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "counter = count()\n",
    "next(counter)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next(counter)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def enumerate(iterable, start=0):\n",
    "    pass  # как?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next(enumerate(count(42)))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 16. Переиспользование генераторов\n",
    "Основное правило переиспользования генераторов: **не\n",
    "делайте этого**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def g():\n",
    "    yield 42\n",
    "gen = g()\n",
    "list(gen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(gen)  # не тут-то было!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Если вы хотите переиспользовать генератор, подумайте\n",
    "ещё раз.\n",
    "\n",
    "Если вы уверены, что без переиспользования не обойтись,\n",
    "воспользуйтесь функцией **tee** из модуля **itertools**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 17. Коллекции и генераторы\n",
    "Генераторы позволяют компактно реализовывать метод\n",
    "`__iter__` у коллекций\n",
    "\n",
    "Рассмотрим уже знакомый нам класс бинарного дерева"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryTree:\n",
    "    def __init__(self, value, left=None, right=None):\n",
    "        self.value = value\n",
    "        self.left, self.right = left, right\n",
    "    def __iter__(self): # inorder\n",
    "        for node in self.left:\n",
    "            yield node.value\n",
    "        yield self.value\n",
    "        for node in self.right:\n",
    "            yield node.value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Плюс генераторов в том, что они позволяют обойтись без\n",
    "лишних классов, например, **InOrderIterator**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 18. Выражения-генераторы\n",
    "Напоминание: в Python есть генераторы списков, множеств\n",
    "и словарей.\n",
    "- Выражения-генераторы работают аналогичным образом,\n",
    "но не порождают коллекцию в процессе работы:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gen = (x ** 2 for x in range(10**42) if x % 2 == 1)\n",
    "gen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next(gen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(filter(lambda x: x % 2 == 1, (x ** 2 for x in range(10))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Если выражение-генератор — единственный аргумент\n",
    "функции, скобки можно опустить:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum(x ** 2 for x in range(10) if x % 2 == 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 19. Выражение yield\n",
    "Оператор **yield** можно использовать как выражение:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def g():\n",
    "    a = (yield)\n",
    "    b = (yield)\n",
    "    print(f'b={b}')\n",
    "    res1 = yield 12 # точка входа 1\n",
    "    print(\"res1 {!r}\".format(res1))\n",
    "    res2 = yield 42 # точка входа 2\n",
    "    print(\"res1 {!r}\".format(res1))\n",
    "    print(\"res2 {!r}\".format(res2))\n",
    "# gen = g()\n",
    "# print(next(gen))  # \"промотаем\" до первого yield\n",
    "# print(next(gen))  # \"промотаем\" до первого yield\n",
    "# print(next(gen))  # \"промотаем\" до end yield\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gen():\n",
    "    while True:\n",
    "        print('loop')\n",
    "        c = yield\n",
    "        print('c = ', c)\n",
    "        d = yield c\n",
    "        print('d = ', d)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "loop\na type &lt;class &#39;NoneType&#39;&gt;\na None\nc =  sss\nb type  &lt;class &#39;str&#39;&gt;\nb sss\nd =  vasya\nloop\nnext iter value:  None\n"
    }
   ],
   "source": [
    "gena = gen()\n",
    "a = next(gena)\n",
    "print('a type', type(a))\n",
    "\n",
    "print('a', a)\n",
    "b = gena.send('sss')\n",
    "print('b type ', type(b))\n",
    "print('b', b)\n",
    "print('next iter value: ', gena.send('vasya'))\n",
    "# gen.send('sbbbss')\n",
    "# next(gen)\n",
    "# next(gen)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "На первый взгляд выражение **yield** выглядит бесполезно,\n",
    "но первое впечатление обманчиво."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 20. Интерфейс генераторов: send\n",
    "Метод **send** возобновляет выполнение генератора и\n",
    "“отправляет” свой аргумент в следующий **yield**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "res1 None\n"
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "42"
     },
     "metadata": {},
     "execution_count": 15
    }
   ],
   "source": [
    "gen = g()\n",
    "gen.send(None)\n",
    "next(gen)\n",
    "# gen.send(\"foobar\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Чтобы инициализировать генератор нужно “отправить” ему\n",
    "**None**. Функция **next** делает ровно это:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gen = g()\n",
    "next(gen)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Результатом метода send является следующее значение\n",
    "генератора или исключение <font color=red>StopIteration</font>, если такого\n",
    "исключения нет."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gen = g()\n",
    "gen.send(None)  # == next(gen)\n",
    "gen.send(\"foobar\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 21. Интерфейс генераторов: throw\n",
    "Метод **throw** поднимает переданное исключение в месте,\n",
    "где генератор приостановил исполнение и возвращает\n",
    "следующее значение генератора\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def g():\n",
    "    try:\n",
    "        yield 42\n",
    "    except Exception as e:\n",
    "        yield e\n",
    "gen = g()\n",
    "next(gen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gen.throw(ValueError, \"something is wrong\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gen.throw(RuntimeError, \"another error\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Если генератор не обработал брошенное в него\n",
    "исключение, то выполнение генератора прекращается и\n",
    "исключение передаётся наверх по стеку вызовов."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 22. Интерфейс генераторов: close\n",
    "Метод **close** поднимает специальное исключение\n",
    "<font color=red>**GeneratorExit**</font> в месте, где генератор приостановил\n",
    "исполнение:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def g():\n",
    "    try:\n",
    "        yield 42\n",
    "    finally:\n",
    "        print(\"Done\")\n",
    "        \n",
    "gen = g()\n",
    "next(gen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gen.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Если всё хорошо, то метод **close** завершает работу\n",
    "генератора и ничего не возвращает.\n",
    "\n",
    " Что может пойти не так? Генератор может обработать\n",
    "исключение <font color=red>**GeneratorExit**</font> и поднять другое исключение."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 23. Генераторы ∼ сопрограммы aka coroutines\n",
    "http://dabeaz.com/coroutines\n",
    "\n",
    "Сопрограмма — это программа, которая может иметь\n",
    "больше одной точки входа, а также поддерживает\n",
    "остановку и продолжение с сохранением состояния.\n",
    "\n",
    "Звучит как определение генератора наоборот:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def grep(pattern):\n",
    "    print(\"Looking for {!r}\".format(pattern))\n",
    "    while True:\n",
    "        line = yield\n",
    "        if pattern in line:\n",
    "            print(line)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gen = grep(\"Gotcha!\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "next(gen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gen.send(\"This line doesn't have what we're looking for\")\n",
    "gen.send(\"This one does. Gotcha!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 24. Инициализация сопрограмм\n",
    "\n",
    "http://python.org/dev/peps/pep-0380\n",
    "\n",
    "Прежде, чем начать работать с сопрограммой, её нужно\n",
    "инициализировать с помощью вызова функции next.\n",
    "• Объявим декоратор coroutine, который скроет эту деталь\n",
    "реализации"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import functools\n",
    "def coroutine(g):\n",
    "    @functools.wraps(g)\n",
    "    def inner(*args, **kwargs):\n",
    "        gen = g()\n",
    "        next(gen)\n",
    "        return gen\n",
    "    return inner\n",
    "grep = coroutine(grep)\n",
    "gen = grep(\"Gotcha!\")\n",
    "gen.send(\"One more line for ya!\")\n",
    "# Зачем это всё нужно? Ответ в домашнем задании"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 26. Оператор yield from\n",
    "\n",
    "Оператор **yield from** позволяет делегировать выполнение\n",
    "другому генератору:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "def chain(*iterables):\n",
    "    for iterable in iterables:\n",
    "        yield from iterable\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Любые вызовы методов **send** и **throw** у родительского\n",
    "генератора будут переданы вложенному генератору без\n",
    "изменений."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 27. Оператор return и исключение StopIteration\n",
    "Кроме оператора **yield** в теле генератора можно\n",
    "использовать оператор **return**.\n",
    "- На человеческом языке использование **return** означает:\n",
    "«У меня больше нет элементов, извини, возьми лучше вот\n",
    "это.»"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "def g():\n",
    "    yield 42\n",
    "    return [] # держи!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gen = g()\n",
    "next(gen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "ename": "StopIteration",
     "evalue": "[]",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m                             Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-73-6e72e47198db>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mnext\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mgen\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m: []"
     ]
    }
   ],
   "source": [
    "next(gen)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 28. return !≡ raise StopIteration\n",
    "Несмотря на схожесть, использование оператора **return** в\n",
    "генераторе не эквивалентно поднятию исключения\n",
    "<font color=red>**StopIteration**</font>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def g():\n",
    "    try:\n",
    "        yield 42\n",
    "        raise StopIteration([]) # !≡ return []\n",
    "    except Exception as e:\n",
    "        pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 29. Выражение yield from\n",
    "Оператор yield from, как и оператор yield, можно\n",
    "использовать в качестве выражения.\n",
    "• При этом значением выражения yield from будет\n",
    "значение атрибута value у поднятого вложенным\n",
    "генератором исключения <font color=red>**StopIteration**</font>:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f():\n",
    "    yield 42\n",
    "    return []\n",
    "\n",
    "def g():\n",
    "    res = yield from f()\n",
    "    print(\"Got {!r}\".format(res))\n",
    "\n",
    "gen = g()\n",
    "next(gen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Got []\n"
     ]
    }
   ],
   "source": [
    "next(gen, None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 30. Менеджеры контекста и генераторы: мотивация\n",
    "Протокол менеджеров контекста требует реализации двух\n",
    "методов: `__enter__` и `__exit__`,\n",
    "- Если мы хотим, чтобы у менеджера было какое-то\n",
    "состояние, то мы вынуждены также добавить метод\n",
    "`__init__`.\n",
    "\n",
    "В итоге получаем:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "class cd:\n",
    "    def __init__(self, path):\n",
    "        self.path = path\n",
    "    def __enter__(self):\n",
    "        self.saved_cwd = os.getcwd()\n",
    "        os.chdir(self.path)\n",
    "    def __exit__(self, *exc_info):\n",
    "        os.chdir(self.saved_cwd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 31. Менеджеры контекста и генераторы: @contextmanager\n",
    "Декоратор **contextmanager** из модуля **contextlib**\n",
    "принимает генератор специального вида и строит по нему\n",
    "менеджер контекста."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from contextlib import contextmanager\n",
    "\n",
    "@contextmanager\n",
    "def cd(path): # __init__\n",
    "    old_path = os.getcwd() # __enter__\n",
    "    os.chdir(path)\n",
    "    try:\n",
    "        yield # ---------\n",
    "    finally:\n",
    "        os.chdir(old_path) # __exit__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Генераторы позволяют сократить количество\n",
    "синтаксического шума при реализации менеджеров\n",
    "контекста"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 32. Ещё один пример использования @contextmanager\n",
    "Метод ``__enter__``, построенный декоратором `contextmanager`,\n",
    "возвращает аргумент оператора `yield`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import tempfile\n",
    "import shutil\n",
    "@contextmanager\n",
    "def tempdir(): # __init__\n",
    "    outdir = tempfile.mkdtemp() # __enter__\n",
    "    try:\n",
    "        yield outdir # ---------\n",
    "    finally:\n",
    "        shutil.rmtree(outdir) # __exit__\n",
    "    \n",
    "with tempdir() as path:\n",
    "    print(path) # ==> /tmp/tmpvfzsmvsv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 33. Генераторы: резюме\n",
    "Генератор в Python — это функция, которая использует\n",
    "операторы ``yield`` или `yield from`.\n",
    "\n",
    " В мире Python генераторы вездесущи не менее, чем\n",
    "любимые всеми декораторы.\n",
    "\n",
    " Мы поговорили о том, что генераторы можно использовать\n",
    "- как итераторы,\n",
    "- как сопрограммы,\n",
    "- как легкие потоки,\n",
    "- для компактной реализации менеджеров контекста."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 34. Модуль itertools: islice\n",
    "Функция `islice` обобщает понятие слайса на\n",
    "произвольный итератор:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2]"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import islice\n",
    "xs = range(10)\n",
    "list(islice(xs, 3))  # ≡ xs[:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(islice(xs, 3, None)) # ≡ xs[3:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5, 7]"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(islice(xs, 3, 8, 2)) # ≡ xs[3:8:2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Прелесть функций из модуля `itertools` в том, что с\n",
    "помощью них легко выражаются самые разнообразные\n",
    "операции над последовательностями.\n",
    "\n",
    "<font color=blue> Вопрос</font><br>\n",
    "Как будет выглядеть функция `drop`, “выкидывающая” префикс\n",
    "длины `n` из переданного ей итератора?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 35. Модуль itertools: бесконечные итераторы\n",
    "ля удобства реализуем родственника функции `drop`:\n",
    "функцию `take`, которая строит список из более, чем `n`\n",
    "первых элементов переданного ей итератора."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "def take(n, iterable):\n",
    "    return list(islice(iterable, n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2]"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(take(3, range(10)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 5, 10]"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Названия бесконечных итераторов говорят сами за себя:\n",
    "from itertools import count, cycle, repeat\n",
    "take(3, count(0, 5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3]"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "take(3, cycle([1, 2, 3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[42, 42, 42]"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "take(3, repeat(42))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[42, 42]"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "take(3, repeat(42, 2)) # не совсем бесконечность"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 36. Модуль itertools: dropwhile и takewhile\n",
    "Функции `dropwhile` и `takewhile` обобщают логику функций\n",
    "`drop` и `take` на произвольный предикат.\n",
    "\n",
    "Обратите внимание, что обе функции возвращают\n",
    "**итератор**, а не список, как реализованная нами функция\n",
    "take:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "from itertools import dropwhile, takewhile\n",
    "list(dropwhile(lambda x: x < 5, range(10)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<itertools.takewhile at 0x59002d8>"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it = takewhile(lambda x: x < 5, range(10))\n",
    "it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4]"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(it)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 37. Модуль itertools: chain\n",
    "В модуле `itertools` реализован уже знакомый нам\n",
    "генератор `chain`, который конкатенирует произвольное\n",
    "число итераторов:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 5, 6, 7]"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import chain\n",
    "take(5, chain(range(2), range(5, 10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сконкатенировать итератор итераторов (!) можно с\n",
    "помощью метода `chain.from_iterable`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 3, 4, 5]"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it = (range(x, x ** x) for x in range(2, 4))\n",
    "take(5, chain.from_iterable(it))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=blue>Вопрос</font><br>\n",
    "Чем `chain.from_iterable(it)` отличается от `chain(*it)`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 38. Модуль itertools: tee\n",
    "Функция `tee` создаёт `n` независимых копий переданного ей\n",
    "итератора:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([0, 1, 2], [0, 1, 2], [0, 1, 2])"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import tee\n",
    "it = range(3)\n",
    "a, b, c = tee(it, 3)\n",
    "list(a), list(b), list(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Использовать it после копирования не рекомендуется,\n",
    "потому что в этом случае скопированные итераторы\n",
    "a, b, c могут пропустить элемент:\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([], [])"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it = iter(range(3))\n",
    "a, b = tee(it, 2)\n",
    "used = list(it)\n",
    "list(a), list(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=blue>Вопрос</font><br>\n",
    "Что изменится, если убрать вызов функции iter из второго\n",
    "примера?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 39. Модуль itertools: комбинаторные итераторы\n",
    "В модуле `itertools` в виде итераторов реализованы полезные\n",
    "комбинаторные операции, например:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('A', 'A'), ('A', 'B'), ('B', 'A'), ('B', 'B')]"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import itertools\n",
    "# декартово произведение итераторов,\n",
    "list(itertools.product(\"AB\", repeat=2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('A', 'A', 'A'),\n",
       " ('A', 'A', 'B'),\n",
       " ('A', 'B', 'A'),\n",
       " ('A', 'B', 'B'),\n",
       " ('B', 'A', 'A'),\n",
       " ('B', 'A', 'B'),\n",
       " ('B', 'B', 'A'),\n",
       " ('B', 'B', 'B')]"
      ]
     },
     "execution_count": 115,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(itertools.product(\"AB\", repeat=3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('A', 'B'), ('B', 'A')]"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# перестановки элементов итератора,\n",
    "list(itertools.permutations(\"AB\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('A', 'B'), ('A', 'C'), ('B', 'C')]"
      ]
     },
     "execution_count": 121,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# сочетания (с повторениями и без) из элементов итератора.\n",
    "from itertools import combinations, \\\n",
    "    combinations_with_replacement\n",
    "list(combinations(\"ABC\", 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(combinations_with_replacement(\"ABC\", 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 40. Комбинаторные итераторы и функция build_graph\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_graph(words, mismatch_percent):\n",
    "    g = ...\n",
    "    n_words = len(words)\n",
    "    for u, v in itertools.combinations(range(n_words), 2):\n",
    "        if len(words[u]) != len(words[v]):\n",
    "            continue\n",
    "        distance = hamming(words[u], words[v])\n",
    "        # ...\n",
    "    return g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=blue>Вопрос</font><br>\n",
    "Выглядит неплохо, но можно лучше. Как?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Слайд 41. Модуль itertools: резюме\n",
    "Модуль `itertools` предоставляет обширный набор\n",
    "компонент для реализации операций над\n",
    "последовательностями.\n",
    " Мы обсудили:\n",
    "- `islice`,\n",
    "- бесконечные итераторы `count`, `cycle`, `repeat`,\n",
    "- `chain`,\n",
    "- `tee`,\n",
    "- комбинаторные итераторы `product`, ``permutations``,\n",
    "`combinations` и `combinations_with_replacement`."
   ]
  }
 ],
 "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.8.5-final"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "metadata": {
     "collapsed": false
    },
    "source": []
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}