Seminars/Seminar 07. Iterators and generators/iterators-generators.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "88e6e85e",
   "metadata": {},
   "source": [
    "# Занятие на кафедре ММП ВМК МГУ. Итераторы и генераторы\n",
    "\n",
    "Подготовил Александр Чернышёв."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "809f0d2a",
   "metadata": {},
   "source": [
    "## Итераторы"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2fc93037",
   "metadata": {},
   "source": [
    "### Цикл `for`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7463a06",
   "metadata": {},
   "source": [
    "Можно использовать, чтобы пробежаться по списку:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "50f350a5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 "
     ]
    }
   ],
   "source": [
    "for i in [1, 2, 3, 4]:\n",
    "    print(i, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2789398a",
   "metadata": {},
   "source": [
    "Можно использовать, чтобы пробежаться по строке:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "fbc2cdb7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p y t h o n "
     ]
    }
   ],
   "source": [
    "for ch in \"python\":\n",
    "    print(ch, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "718ae1b0",
   "metadata": {},
   "source": [
    "Можно использовать, чтобы пробежаться по ключам словаря:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "61cd8943",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x y "
     ]
    }
   ],
   "source": [
    "for k in {\"x\": 1, \"y\": 2}:\n",
    "    print(k, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5c7dd90",
   "metadata": {},
   "source": [
    "Можно использовать, чтобы пробежаться по строкам файла:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "b039e54b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello, world!\n",
      "Cat and dog.\n",
      "Python 3.9.\n"
     ]
    }
   ],
   "source": [
    "with open(\"a.txt\", \"w\") as f:\n",
    "    print(\"Hello, world!\", \"Cat and dog.\",\n",
    "          \"Python 3.9.\", sep='\\n', file=f)\n",
    "\n",
    "with open(\"a.txt\", \"r\") as f:\n",
    "    for line in f:\n",
    "        print(line, end=\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0afa1d56",
   "metadata": {},
   "source": [
    "Такие объекты называются итерируемыми (`iterable`)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1488f8d",
   "metadata": {},
   "source": [
    "Многие функции в Python принимают на вход итерируемые объекты:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9e5cadb2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a, b, c'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\", \".join([\"a\", \"b\", \"c\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "ee12e327",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'x, y'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\", \".join({\"x\": 1, \"y\": 2})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "fc1c0317",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['p', 'y', 't', 'h', 'o', 'n']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(\"python\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "fc4ee279",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('x', 'y')"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tuple({\"x\": 1, \"y\": 2})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "17aedbda",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum([1, 2, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "50b389a9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all((True, False, True, True))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c7c4eab",
   "metadata": {},
   "source": [
    "### Протокол итерации"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b5c0b974",
   "metadata": {},
   "source": [
    "Встроенная функция `iter` принимает на вход итерируемый объект и возвращает итератор."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "efdd1621",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<list_iterator at 0x2095a66e4c0>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = [1, 2, 3]\n",
    "x = iter(lst)  # Под капотом: x = lst.__iter__()\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "2a72b365",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(x)  # Под капотом: x.__next__()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "f18b5988",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "d3a4e07d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "707ed6b7",
   "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;32mC:\\Users\\ALEXAN~1\\AppData\\Local\\Temp/ipykernel_59008/3485793935.py\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[0mx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05e7fbdc",
   "metadata": {},
   "source": [
    "Каждый раз, когда мы вызываем функцию `next` от итератора, она выдает нам следующий элемент. Если элементов в итераторе больше нет, то он поднимает исключение `StopIteration`.\n",
    "\n",
    "Итераторы реализованы в виде классов. Вот пример итератора, который работает так же, как встроенный `range` (за исключением меньшей функциональности)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "d4aff9f0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(range(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "906b96d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "class yrange:\n",
    "    def __init__(self, n):\n",
    "        self.i = 0\n",
    "        self.n = n\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "    def __next__(self):\n",
    "        if self.i >= self.n:\n",
    "            raise StopIteration()\n",
    "\n",
    "        i = self.i\n",
    "        self.i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d0b0e7f",
   "metadata": {},
   "source": [
    "Метод `__iter__` — это то, что делает объекты итерируемыми. Вызов функции `iter` от объекта просто вызывает его метод `__iter__`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd621d62",
   "metadata": {},
   "source": [
    "Метод `__iter__` возвращает итератор. Итератор должен иметь метод `__next__` и поднимать исключение `StopIteration`, когда в итераторе больше не осталось элементов.\n",
    "\n",
    "Из-за такой специфики работы метода `__next__` по объектам итератора можно пробежаться только 1 раз. После первого прохода по всем его элементам далее он просто будет каждый раз поднимать исключение `StopIteration`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "36f85ee3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = yrange(3)\n",
    "next(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "2a20f2ec",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "772bf00d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "ccf6befa",
   "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;32mC:\\Users\\ALEXAN~1\\AppData\\Local\\Temp/ipykernel_59008/1131913922.py\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[0my\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32mC:\\Users\\ALEXAN~1\\AppData\\Local\\Temp/ipykernel_59008/792458693.py\u001b[0m in \u001b[0;36m__next__\u001b[1;34m(self)\u001b[0m\n\u001b[0;32m      9\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0m__next__\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     10\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mi\u001b[0m \u001b[1;33m>=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 11\u001b[1;33m             \u001b[1;32mraise\u001b[0m \u001b[0mStopIteration\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     12\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     13\u001b[0m         \u001b[0mi\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d0bc422",
   "metadata": {},
   "source": [
    "Многие встроенные функции принимают итерируемые объекты в качестве аргументов:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "afcc987e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(yrange(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "0d293154",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(yrange(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "467c6ae6",
   "metadata": {},
   "source": [
    "В приведенном выше случае итерируемое и итератор являются одним и тем же объектом, потому что метод `__iter__` возвращает `self`. Не обязательно так делать всегда:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "1a819d13",
   "metadata": {},
   "outputs": [],
   "source": [
    "class zrange:\n",
    "    \"\"\"Реализация zrange, имитирующего range\"\"\"\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "\n",
    "    def __iter__(self):\n",
    "        return zrange_iter(self.n)\n",
    "\n",
    "\n",
    "class zrange_iter:\n",
    "    \"\"\"Реализация итератора для zrange\"\"\"\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.i = 0\n",
    "        self.n = n\n",
    "\n",
    "    def __iter__(self):\n",
    "        # Iterators are iterables too.\n",
    "        # Adding this functions to make them so.\n",
    "        return self\n",
    "\n",
    "    def __next__(self):\n",
    "        if self.i < self.n:\n",
    "            i = self.i\n",
    "            self.i += 1\n",
    "            return i\n",
    "        else:\n",
    "            raise StopIteration()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "395a81f6",
   "metadata": {},
   "source": [
    "Так как итератор поглащается за один проход (см. выше, почему), то в случае, когда итерируемое и итератор являются одним и тем же объектом, то и итерируемое поглощается за один проход:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "4f4a7374",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rng = yrange(3)\n",
    "\n",
    "list(rng)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a716d889",
   "metadata": {},
   "source": [
    "_Небольшое лирическое отступление._\n",
    "\n",
    "Что под капотом, когда мы вызываем list(rng):\n",
    "\n",
    "```python\n",
    "res = []\n",
    "\n",
    "it = iter(rng)\n",
    "while True:\n",
    "    try:\n",
    "        x = next(it)\n",
    "    except StopIteration:\n",
    "        break\n",
    "    res.append(x)\n",
    "res\n",
    "```\n",
    "\n",
    "Получается, вызов ```list()``` от итерируемого объекта сначала получает итератор на этот объект, после чего достает все элементы из этого итератора и складывает их в список. То есть вызов `list()` от объекта поглащает все элементы из его итератора."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "1f425f01",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2]\n"
     ]
    }
   ],
   "source": [
    "rng = yrange(3)\n",
    "print(list(rng))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "e1cfd5db",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, 3)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rng.i, rng.n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "61fe03c8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n"
     ]
    }
   ],
   "source": [
    "print(list(rng))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01c0ae71",
   "metadata": {},
   "source": [
    "Эту проблему можно исправить, например, переместив зануление атрибута `i` в метод `__iter__`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "b71f4d5c",
   "metadata": {},
   "outputs": [],
   "source": [
    "class yrange:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "\n",
    "    def __iter__(self):\n",
    "        self.i = 0\n",
    "        return self\n",
    "\n",
    "    def __next__(self):\n",
    "        if self.i >= self.n:\n",
    "            raise StopIteration()\n",
    "\n",
    "        i = self.i\n",
    "        self.i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "a1a30473",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rng = yrange(3)\n",
    "list(rng)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "cc37d0e8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(rng)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66f9e7e3",
   "metadata": {},
   "source": [
    "Но у такого подхода в принципе есть проблема с невозможностью создать одновременно несколько корректных итераторов для объекта, потому что сам объект и является итератором для себя.\n",
    "\n",
    "Создадим первый итератор:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "e126c293",
   "metadata": {},
   "outputs": [],
   "source": [
    "rng = yrange(3)\n",
    "it1 = iter(rng)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "bcb2ffd1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(it1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "eb7d24bd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(it1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e7f6b06",
   "metadata": {},
   "source": [
    "Создадим второй итератор:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "a6328f32",
   "metadata": {},
   "outputs": [],
   "source": [
    "it2 = iter(rng)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "ecdec6ba",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(it1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c976449",
   "metadata": {},
   "source": [
    "Первый итератор обнулился!\n",
    "\n",
    "Все из-за того, что первый и второй итераторы суть один и тот же объект:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "b0cd1b43",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it1 is it2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e704d38",
   "metadata": {},
   "source": [
    "`zrange` не является итератором, поэтому он не будет никогда истощаться:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "5c3a8521",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2]\n",
      "[0, 1, 2]\n"
     ]
    }
   ],
   "source": [
    "rng = zrange(3)\n",
    "print(list(rng))\n",
    "print(list(rng))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af978d61",
   "metadata": {},
   "source": [
    "А итератор для него, как писалось выше, истощаться будет:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "6a8bfe97",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it = iter(rng)\n",
    "list(it)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "115b3c86",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(it)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78b1941f",
   "metadata": {},
   "source": [
    "В таком подходе проблемы с созданием одновременно нескольких итераторов на объект нет, потому что реализации класса объекта и итератора для него разделены."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "517363d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "rng = zrange(3)\n",
    "it1 = iter(rng)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "ca84e3bf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(it1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "3a653796",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(it1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "6f5e8752",
   "metadata": {},
   "outputs": [],
   "source": [
    "it2 = iter(rng)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "35c3717e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(it1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "49d0ec59",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it1 is it2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15cfa2e5",
   "metadata": {},
   "source": [
    "### Итого\n",
    "Протокол итераций (протокол итераторов, iterator protocol) заключается в концепции итерирования по контейнерам с помощью методов `__iter__` и `__next__`.\n",
    "\n",
    "Итерируемое (iterable) — то, что имеет метод `__iter__`.\n",
    "\n",
    "Итератор (iterator) — то, что имеет методы `__iter__` (должен возвращать `self`) и `__next__`, т.е. поддреживает протокол итераций."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f872c216",
   "metadata": {},
   "source": [
    "### Обратно к циклу `for`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0f19c16",
   "metadata": {},
   "source": [
    "```python\n",
    "for elem in elem_collection:\n",
    "    do_something(elem)\n",
    "```\n",
    "\n",
    "Концептуально такой цикл `for` делает следующее:\n",
    "\n",
    "```python\n",
    "it = iter(elem_collection) # инициализация\n",
    "while True:\n",
    "    try:\n",
    "        elem = next(it) # получить следующий элемент\n",
    "    except StopIteration: # если элементов больше нет\n",
    "        break\n",
    "    do_something(elem)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26c913f6",
   "metadata": {},
   "source": [
    "### Особенности `iter` и `next`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39be190a",
   "metadata": {},
   "source": [
    "Другая форма вызова `iter`: принимает функцию и значение, вызывает функцию, пока она не вернёт это значение:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "70dae970",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 1 1 0 8 4 "
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "random.seed(179)\n",
    "\n",
    "for x in iter(lambda: random.randint(0, 9), 7):\n",
    "    print(x, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6eee92e4",
   "metadata": {},
   "source": [
    "Для функции `next` можно вторым аргументом указать значение, которое необходимо вернуть в случае исключения:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "e7af0122",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "153"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(iter([]), 153)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "a8e18a06",
   "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;32mC:\\Users\\ALEXAN~1\\AppData\\Local\\Temp/ipykernel_59008/768943942.py\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[0miter\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(iter([]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88de9ebf",
   "metadata": {},
   "source": [
    "### Протокол итераций и `__getitem__`\n",
    "Напоминание: `__getitem__` возвращает элемент по индексу либо поднимает `IndexError`, если элемента нет."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "213b925a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = [1, 2, 3]\n",
    "lst[1]  # Под капотом: lst.__getitem__(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96c902c4",
   "metadata": {},
   "source": [
    "Если реализован метод `__getitem__`, протокол итераций будет реализован автоматически:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "c2437079",
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyList:\n",
    "    def __init__(self, *args):\n",
    "        self.list = list(args)\n",
    "\n",
    "    def __getitem__(self, i):\n",
    "        return self.list[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "8bdff91d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 "
     ]
    }
   ],
   "source": [
    "for elem in MyList(1, 2):\n",
    "    print(elem, end=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "5327209c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<iterator at 0x2095b83ea90>"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iter(MyList(1, 2, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f7c1904",
   "metadata": {},
   "source": [
    "Как реализован протокол итераций исходя из примера?\n",
    "\n",
    "Примерно следующим образом. Обратите внимание, метод `__getitem__` я переименовал в `getitem`, чтобы не сложилось впечатление, что за нас всю работу сделал `Python`.\n",
    "\n",
    "В реализации мы создали дополнительный класс для итератора по объектам класса `MyList`. Вообще говоря, написанный итератор подходит для любого объекта, в котором реализован метод `getitem`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "3528a3c1",
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyList:\n",
    "    def __init__(self, *args):\n",
    "        self.list = list(args)\n",
    "\n",
    "    def getitem(self, i):\n",
    "        return self.list[i]\n",
    "\n",
    "    def __iter__(self):\n",
    "        return MyListIterator(self)\n",
    "\n",
    "\n",
    "class MyListIterator:\n",
    "    def __init__(self, obj):\n",
    "        self.i = 0\n",
    "        self.obj = obj\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "    def __next__(self):\n",
    "        try:\n",
    "            ret = self.obj.getitem(self.i)\n",
    "        except IndexError:\n",
    "            raise StopIteration\n",
    "        self.i += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "ce560dcc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 "
     ]
    }
   ],
   "source": [
    "for elem in MyList(1, 2):\n",
    "    print(elem, end=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "3f83e240",
   "metadata": {},
   "outputs": [],
   "source": [
    "lst = MyList(1, 2, 3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "347d6a41",
   "metadata": {},
   "outputs": [],
   "source": [
    "it = iter(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "95217ae5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it.obj is lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "b5fa30aa",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.MyListIterator at 0x2095b8250d0>"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1143b1e5",
   "metadata": {},
   "source": [
    "### Протокол итераций и `__contains__`\n",
    "Напоминание: `__contains__` возвращает `True` если переданный элемент содержится в экземпляре (перегрузка `in` и `not in`).\n",
    "\n",
    "Если класс реализует протокол итераций, метод `__contains__` реализуется автоматически следующим образом:\n",
    "\n",
    "```python\n",
    "class SomeClass:\n",
    "    # это реализуется автоматически\n",
    "    def __contains__(self, target_elem):\n",
    "        for elem in self:\n",
    "            if target_elem == elem:\n",
    "                return True\n",
    "        return False\n",
    "```\n",
    "\n",
    "Пример для `MyList`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "f9d88e6a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2 in MyList(1, 2, 3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "36885dd2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "123 in MyList(1, 2, 3, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ba39c10",
   "metadata": {},
   "source": [
    "#### Задача 1\n",
    "\n",
    "Напишите класс итератора `my_reversed` (аналог `reversed`), который принимает на вход __список__ и выдает его в обратном направлении."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "47f2f0f6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 3, 2, 1]"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(reversed([1, 2, 3, 4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d66071e3",
   "metadata": {},
   "source": [
    "Кстати, в чем отличие `reversed([1, 2, 3, 4])` от `[1, 2, 3, 4][::-1]`?\n",
    "\n",
    "В первом случае не выделяется дополнительная память под еще один список (мы получаем в итоге итератор), во втором случае — выделяется (мы получаем в итоге список).\n",
    "\n",
    "По сути в этом и заключается прелесть итераторов — они позволяют модифицировать данные \"на лету\", без выделения дополнительной памяти."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "600ddb14",
   "metadata": {},
   "source": [
    "Пример решения:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "9cdc52fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "class my_reversed:\n",
    "    def __init__(self, lst):\n",
    "        self.lst = lst\n",
    "        self.i = len(lst) - 1\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "    def __next__(self):\n",
    "        if self.i < 0:\n",
    "            raise StopIteration\n",
    "        ret = self.lst[self.i]\n",
    "        self.i -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "8bd402a5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 3, 2, 1]"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it = my_reversed([1, 2, 3, 4])\n",
    "list(it)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "baf9e3ae",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 3 2 1 "
     ]
    }
   ],
   "source": [
    "for x in my_reversed([1, 2, 3, 4]):\n",
    "    print(x, end=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "d1b675cf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, 3, 2, 1)"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it = my_reversed([1, 2, 3, 4])\n",
    "next(it), next(it), next(it), next(it)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "f5f8e22f",
   "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;32mC:\\Users\\ALEXAN~1\\AppData\\Local\\Temp/ipykernel_59008/600241529.py\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[0mit\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32mC:\\Users\\ALEXAN~1\\AppData\\Local\\Temp/ipykernel_59008/2672176280.py\u001b[0m in \u001b[0;36m__next__\u001b[1;34m(self)\u001b[0m\n\u001b[0;32m      9\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0m__next__\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     10\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mi\u001b[0m \u001b[1;33m<\u001b[0m \u001b[1;36m0\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 11\u001b[1;33m             \u001b[1;32mraise\u001b[0m \u001b[0mStopIteration\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     12\u001b[0m         \u001b[0mret\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mlst\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     13\u001b[0m         \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mi\u001b[0m \u001b[1;33m-=\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(it)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae12d8a8",
   "metadata": {},
   "source": [
    "Аналогично можно сравнить по используемой памяти следующие куски кода:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "c7ec6d0b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "b81d5351",
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 0.0\n",
    "for x in np.arange(10 ** 7):\n",
    "    s += x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "0dd929db",
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 0\n",
    "for x in range(10 ** 7):\n",
    "    s += x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7cd0fc3c",
   "metadata": {},
   "source": [
    "В случае с использованием `numpy.arange` выделяется дополнительная память."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3eb112f9",
   "metadata": {},
   "source": [
    "Интереснее сравнить эти примеры по времени работы."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "6a4c193f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.3 s ± 49.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "s = 0.0\n",
    "for x in np.arange(10 ** 7):\n",
    "    s += x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "0363edb5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "330 ms ± 4.15 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "s = 0\n",
    "for x in range(10 ** 7):\n",
    "    s += x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "abb7d79f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "245 ms ± 6.77 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "s = sum(range(10 ** 7))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92c0c6cd",
   "metadata": {},
   "source": [
    "Как видим, в первом случае выделение памяти и последующая итерация по ячейкам оказывается в 3-4 раза медленнее, чем итерация по итератору `range`.\n",
    "\n",
    "Еще интересно, что встроенная функция `sum` работает быстрее цикла примерно на 34%."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "0907eccc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "51 ms ± 585 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "s = np.arange(10 ** 7).astype(float).sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f060bc1b",
   "metadata": {},
   "source": [
    "Правда, использование встроенной функции для суммирования в `numpy` оказывается в 5-6 раз быстрее, чем реализация на чистом `python`. Это обсуловлено тем, что операции в `numpy` реализованы на `C/C++`, из-за чего они работают быстрее питоновских (то есть, получается, цикл на `C/C++` работает примерно в 25 раз быстрее, чем цикл на `python`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "21567ce8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "82.1 ns ± 1.22 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "n = 10 ** 7\n",
    "s = n * (n - 1) // 2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec226bc2",
   "metadata": {},
   "source": [
    "Ну и не стоит забывать, что иногда можно вывести аналитическую формулу для ответа и тогда вычисления могут стать гораздо быстрее (но это не всегда работает)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31f71d75",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## Генераторы"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23197fbf",
   "metadata": {},
   "source": [
    "Генераторы — более простой способ создания итераторов. Генератор — это функция, которая выдает последовательность результатов вместо одного значения."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "0f098a61",
   "metadata": {},
   "outputs": [],
   "source": [
    "def yrange(n):\n",
    "    i = 0\n",
    "    while i < n:\n",
    "        yield i\n",
    "        i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "eff42645",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object yrange at 0x000002096B48C190>"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = yrange(3)\n",
    "y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "e886b4c0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "d375226f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "95423075",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "e59a2b0f",
   "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;32mC:\\Users\\ALEXAN~1\\AppData\\Local\\Temp/ipykernel_59008/1131913922.py\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[0my\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3b8927e",
   "metadata": {},
   "source": [
    "Генератор также является итератором. Вам не нужно беспокоиться о протоколе итераций.\n",
    "\n",
    "Слово “генератор” ошибочно используется как для обозначения функции, которая генерирует, так и для того, что она генерирует. Будем использовать слово “генератор” для обозначения созданного генератором объекта, а “функция-генератор” — для обозначения функции, которая его генерирует.\n",
    "\n",
    "Когда вызывается функция-генератор, она возвращает генератор, даже не начиная выполнение функции. Когда `next` вызывается в первый раз, функция начинает выполняться до тех пор, пока не достигнет оператора `yield`. Полученное значение возвращается на вызов `next`.\n",
    "\n",
    "Следующий пример демонстрирует взаимодействие между `yield` и вызовом метода `__next__` у генератора:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "2ee8ba22",
   "metadata": {},
   "outputs": [],
   "source": [
    "def foo():\n",
    "    print(\"begin\")\n",
    "    for i in range(3):\n",
    "        print(\"before yield\", i)\n",
    "        yield i\n",
    "        print(\"after yield\", i)\n",
    "    print(\"end\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "37e5845e",
   "metadata": {},
   "outputs": [],
   "source": [
    "f = foo()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "1761d373",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "begin\n",
      "before yield 0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "eb73504c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "after yield 0\n",
      "before yield 1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "fb62c765",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "after yield 1\n",
      "before yield 2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "e7e9d551",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "after yield 2\n",
      "end\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;32mC:\\Users\\ALEXAN~1\\AppData\\Local\\Temp/ipykernel_59008/4256387510.py\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[0mf\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(f)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adae00fd",
   "metadata": {},
   "source": [
    "Рассмотрим пример:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "590c865a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def integers():\n",
    "    \"\"\"Infinite sequence of integers.\"\"\"\n",
    "    i = 1\n",
    "    while True:\n",
    "        yield i\n",
    "        i = i + 1\n",
    "\n",
    "\n",
    "def squares():\n",
    "    for i in integers():\n",
    "        yield i * i\n",
    "\n",
    "\n",
    "def take(n, seq):\n",
    "    \"\"\"Returns first n values from the given sequence.\"\"\"\n",
    "    seq = iter(seq)\n",
    "    result = []\n",
    "    try:\n",
    "        for i in range(n):\n",
    "            result.append(next(seq))\n",
    "    except StopIteration:\n",
    "        pass\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "b9e8d410",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "take(10, integers())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "id": "184f0f74",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 9, 16, 25]"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "take(5, squares())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "766d37a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Если запустите, то получите длинное полотно вывода...\n",
    "for x in integers():\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1d956a5",
   "metadata": {},
   "source": [
    "Еще пример.\n",
    "\n",
    "Генератор `unique` возвращает из итерируемого объекта только уникальные значения в нем."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "id": "f66f948f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object unique at 0x000002096B48C970>"
      ]
     },
     "execution_count": 99,
     "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",
    "\n",
    "xs = [1, 1, 2, 3]\n",
    "unique(xs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "3a23bf4c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3]"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(unique(xs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "id": "1a1a6f32",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3]"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(unique(xs, [2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16846025",
   "metadata": {},
   "source": [
    "Еще пример.\n",
    "\n",
    "Генератор `chain` объединяет несколько итерируемых объектов в один."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "e387574e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object chain at 0x000002096B48CB30>"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def chain(*iterables):\n",
    "    for iterable in iterables:\n",
    "        for item in iterable:\n",
    "            yield item\n",
    "\n",
    "xs = range(3)\n",
    "ys = [42]\n",
    "chain(xs, ys)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "3260a82b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 42]"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(chain(xs, ys))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "6d97c98d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "42 in chain(xs, ys)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7617d294",
   "metadata": {},
   "source": [
    "### Истощение\n",
    "\n",
    "Генераторы, как и любые итераторы, истощаются:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "id": "3be3b736",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[42]"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f():\n",
    "    yield 42\n",
    "\n",
    "gen = f()\n",
    "list(gen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "c81ec669",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(gen)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4f1a3dd",
   "metadata": {},
   "source": [
    "Не надо переиспользовать генераторы!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb3906ca",
   "metadata": {},
   "source": [
    "### Генераторные выражения\n",
    "\n",
    "Генераторное выражение — это генераторная версия генератора списков (list comprehensions). Генераторные выражения выглядят как генераторы списков, но вместо списка возвращают генератор."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "ba8b5c49",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object <genexpr> at 0x000002096B48CF20>"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gen = (x ** 2 for x in range(0, 5))\n",
    "gen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "2a5da3d3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(gen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "f1061914",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(gen)  # Генераторные выражения тоже истощаются"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "id": "6aa2850c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16]"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gen = (x ** 2 for x in range(0, 5))\n",
    "list(gen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "c8ed2acf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 4 9 16 "
     ]
    }
   ],
   "source": [
    "for x in (x ** 2 for x in range(0, 5)):\n",
    "    print(x, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be9b451a",
   "metadata": {},
   "source": [
    "Генераторы списков, словарей множеств не являются генераторами!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a202ccb",
   "metadata": {},
   "source": [
    "### `yield from`\n",
    "\n",
    "Оператор `yield from` позволяет делегировать выполнение другому генератору:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "fc104b1d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4, 12, 25, 1, 2]"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f():\n",
    "    yield 1\n",
    "    yield 2\n",
    "\n",
    "def g():\n",
    "    yield 4\n",
    "    yield 12\n",
    "    yield 25\n",
    "\n",
    "def h():\n",
    "    yield from f()\n",
    "    yield from g()\n",
    "    yield from f()\n",
    "\n",
    "list(h())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f047cf43",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## Стандартные итераторы"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e2202e0",
   "metadata": {},
   "source": [
    "### `range`\n",
    "\n",
    "`range` возвращает итерируемый объект `range object` (не итератор!).\n",
    "\n",
    "`range` при любых аргументах требует константный объём памяти."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "9d886a26",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "range(0, 5)"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_range = range(0, 5)\n",
    "my_range"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "9e953faf",
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'range' object is not an iterator",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32mC:\\Users\\ALEXAN~1\\AppData\\Local\\Temp/ipykernel_59008/2111157206.py\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[0mmy_range\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: 'range' object is not an iterator"
     ]
    }
   ],
   "source": [
    "next(my_range)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "e10a4a4e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<range_iterator at 0x2096b480830>"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iter(my_range)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "0efb8c5a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(iter(my_range))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "b735da86",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(range(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8662129",
   "metadata": {},
   "source": [
    "### `zip`\n",
    "\n",
    "`zip` возвращает итератор."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "c30d7a17",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<zip at 0x2095c163700>"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_list_1 = [1, 2]\n",
    "my_list_2 = ['a', 'b']\n",
    "my_tuples = zip(my_list_1, my_list_2)\n",
    "my_tuples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "id": "f26d7ec3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<zip at 0x2095c163700>"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iter(my_tuples)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "id": "d628fe62",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 'a')"
      ]
     },
     "execution_count": 121,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(my_tuples)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "id": "1c7f40d7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 'b')"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(my_tuples)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "id": "c1a12bbe",
   "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;32mC:\\Users\\ALEXAN~1\\AppData\\Local\\Temp/ipykernel_59008/2903448030.py\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[0mmy_tuples\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(my_tuples)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eeec8ed1",
   "metadata": {},
   "source": [
    "### `enumerate`\n",
    "\n",
    "`enumerate` возвращает итератор"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "id": "1154f8dc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<enumerate at 0x2095c172dc0>"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_list = ['a', 'b', 'c']\n",
    "it = enumerate(my_list)\n",
    "it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "id": "a4f76c94",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 'a')"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(it)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d9dca48",
   "metadata": {},
   "source": [
    "### `map`\n",
    "\n",
    "`map(func, sequence1, sequence2 ... )` возвращает итератор, состоящий из результатов применений функции `func` к элементам `sequence1`, `sequence2`, ....\n",
    "\n",
    "* `func` — функция, которая применяется к каждому элементу `sequence`\n",
    "* `sequence1`, `sequence2` ... — итераторы"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "id": "038e74a6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 4, 6]"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it = map(lambda x: x * 2, [0, 1, 2, 3])\n",
    "list(it)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "id": "07819da7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 101, 502]"
      ]
     },
     "execution_count": 127,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it = map(lambda x, y: x + y, [0, 1, 2, 3], [10, 100, 500])\n",
    "list(it)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f94aa3b4",
   "metadata": {},
   "source": [
    "### `filter`\n",
    "`filter(func, sequence)` возвращает итератор, состоящий из элементов `sequence`, для которых `func` вернула `True`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "id": "0e78c017",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 5]"
      ]
     },
     "execution_count": 128,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "it = filter(lambda x: x > 0, [0, -1, 2, -3, 5])\n",
    "list(it)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57d4ea51",
   "metadata": {},
   "source": [
    "И `filter`, и `map` можно проще записать через генераторы списков!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8cb423e5",
   "metadata": {},
   "source": [
    "### `reduce`\n",
    "`reduce(func, sequence)` — кумулятивное применение функции `func` к элементам последовательности `sequence`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "id": "be345453",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 129,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from functools import reduce\n",
    "\n",
    "res = reduce(lambda x, y: x * y, [1, 2, 3, 4])\n",
    "res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "id": "c9cd4a25",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'(((1*2)*3)*4)'"
      ]
     },
     "execution_count": 130,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res = reduce(lambda x, y: '({}*{})'.format(str(x), str(y)),\n",
    "             [1, 2, 3, 4])\n",
    "res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4086e469",
   "metadata": {},
   "source": [
    "### Соединение и повторение итераторов\n",
    "Написанная нами `chain` есть в `itertools`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "id": "0a451f25",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 131,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import chain\n",
    "\n",
    "it1 = iter([1, 2, 3])\n",
    "it2 = iter([4, 5])\n",
    "list(chain(it1, it2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efeee9bd",
   "metadata": {},
   "source": [
    "`repeat` для создания итератора повторяющейся последовательности:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "id": "90ec42ff",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2], [1, 2], [1, 2], [1, 2]]"
      ]
     },
     "execution_count": 132,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import repeat\n",
    "\n",
    "list(repeat([1, 2], 4))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ecfcd5ce",
   "metadata": {},
   "source": [
    "### Бесконечные итераторы"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "id": "90cede4c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 5, 10, 15, 20, 25]"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import count # бесконечный range\n",
    "\n",
    "c = []\n",
    "for i in count(0, 5):\n",
    "    c.append(i)\n",
    "    if i > 20:\n",
    "        break\n",
    "c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "id": "807eaf49",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 1, 2, 3, 1]\n"
     ]
    }
   ],
   "source": [
    "from itertools import cycle # бесконечный повтор последовательности\n",
    "\n",
    "d = []\n",
    "it = cycle([1, 2, 3])\n",
    "for i, j in enumerate(it):\n",
    "    if i > 6:\n",
    "        break\n",
    "    d.append(j)\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1fed7c58",
   "metadata": {},
   "source": [
    "### Срезы и взятие частей\n",
    "Срез для произвольного итератора:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "id": "ec0d0a63",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 4, 6]"
      ]
     },
     "execution_count": 135,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import islice\n",
    "\n",
    "e = islice(range(10), 0, 8, 2)\n",
    "list(e)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e99fac2",
   "metadata": {},
   "source": [
    "Выбрасывать из итератора элементы, пока не найдётся элемент, удовлетворяющий условию:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "id": "c4586d1a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 136,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import dropwhile\n",
    "\n",
    "f = dropwhile(lambda x: x < 5, range(10))\n",
    "list(f)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a529f677",
   "metadata": {},
   "source": [
    "### Комбинаторные итераторы"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "id": "5c407675",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "123\n",
      "132\n",
      "213\n",
      "231\n",
      "312\n",
      "321\n"
     ]
    }
   ],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "it = permutations(\"123\")\n",
    "for x in it:\n",
    "    print(''.join(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "id": "41cfd8b0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "AB\n",
      "AC\n",
      "BC\n"
     ]
    }
   ],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "it = combinations(\"ABC\", 2)\n",
    "for x in it:\n",
    "    print(''.join(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "id": "6eac77e7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "AA\n",
      "AB\n",
      "BA\n",
      "BB\n"
     ]
    }
   ],
   "source": [
    "from itertools import product\n",
    "\n",
    "it = product(\"AB\", repeat=2)\n",
    "for x in it:\n",
    "    print(''.join(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "437735c6",
   "metadata": {},
   "source": [
    "### Задача 2\n",
    "\n",
    "Написать `permutations`, `combinations`, `product`.\n",
    "\n",
    "TBD..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7288f9a",
   "metadata": {},
   "source": [
    "## Итераторы в задачах с данными большого объёма\n",
    "\n",
    "Итераторы могут быть полезны в ситуациях, когда хранить всю выборку в памяти невозможно.\n",
    "\n",
    "Алгоритм работы:\n",
    "\n",
    "1. Сохранить данные на жёстком диске в хорошем формате;\n",
    "2. Написать итератор, считывающий данные неполностью и преобразующий их в вектора;\n",
    "3. Обучать алгоритм по батчам данных."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc1448c6",
   "metadata": {},
   "source": [
    "## Варианты применения итераторов в data science\n",
    "* Работа с огромной текстовой коллекцией (коллекцией изображений, и т.д.);\n",
    "* Изменение порядка подачи объектов на обучение;\n",
    "* Быстрая генерация из сложных объектов более простых (например, по тексту генерируем пары предложений)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dec3b390",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## Заключение\n",
    "* Итераторы позволяют не хранить одновременно в памяти все значения последовательности;\n",
    "* Итераторы можно задавать с помощью описания специальных методов `__iter__` и `__next__` или декларативно с помощью генераторов;\n",
    "* Многие операции с операторами уже реализованы в библиотеке `itertools` либо средствами `itertools` их можно реализовать проще;\n",
    "* Итераторы необходимо применять тогда, когда невозможно хранить весь объём данных в памяти."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}