02_advanced/04_迭代器与生成器.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "48ac95ca",
   "metadata": {},
   "source": [
    "| [02_advanced/04_迭代器与生成器.ipynb](https://github.com/shibing624/python-tutorial/blob/master/02_advanced/04_迭代器与生成器.ipynb)  | 迭代器和yield生成器  |[Open In Colab](https://colab.research.google.com/github/shibing624/python-tutorial/blob/master/02_advanced/04_迭代器与生成器.ipynb) |\n",
    "\n",
    "# 迭代器\n",
    "\n",
    "迭代是Python最强大的功能之一，是访问集合元素的一种方式。\n",
    "\n",
    "迭代器是一个可以记住遍历的位置的对象。\n",
    "\n",
    "迭代器对象从集合的第一个元素开始访问，直到所有的元素被访问完结束。迭代器只能往前不会后退。\n",
    "\n",
    "迭代器有两个基本的方法：iter() 和 next()。\n",
    "\n",
    "字符串，列表或元组对象都可用于创建迭代器：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "9a1ffc83",
   "metadata": {},
   "outputs": [],
   "source": [
    "list=[1,2,3,4]\n",
    "it = iter(list)    # 创建迭代器对象"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "294b0965",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(it) # 输出迭代器的下一个元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "4af742e4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(it) # 再输出下一个元素"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "020051b6",
   "metadata": {},
   "source": [
    "## enumerate\n",
    "列表好处是不需要对下标进行迭代，直接输出列表的值："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "3e221629",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "4\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "x = [2, 4, 6]\n",
    "\n",
    "for i in x:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0b79c3f",
   "metadata": {},
   "source": [
    "但是有些情况下，我们既希望获得下标，\n",
    "也希望获得对应的值，那么：\n",
    "\n",
    "可以将迭代器传给 enumerate 函数，\n",
    "这样每次迭代都会返回一组 (index, value) 组成的元组：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "2d370838",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 is 2\n",
      "1 is 4\n",
      "2 is 6\n"
     ]
    }
   ],
   "source": [
    "x = [2, 4, 6]\n",
    "for i, n in enumerate(x):\n",
    "    print(i, 'is', n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b4979ee",
   "metadata": {},
   "source": [
    "## 自定义迭代器\n",
    "\n",
    "一个迭代器都有  `__iter__()` 与 `__next__()` \n",
    "\n",
    "`__iter__()` 方法返回一个特殊的迭代器对象， 这个迭代器对象实现了 `__next__()` 方法并通过 StopIteration 异常标识迭代的完成。\n",
    "\n",
    "`__next__()` 方法（Python 2 里是 next()）会返回下一个迭代器对象。\n",
    "\n",
    "自定义一个 list 的取反迭代器："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "5ee52663",
   "metadata": {},
   "outputs": [],
   "source": [
    "class ReverseListIterator(object):\n",
    "    def __init__(self, lst):\n",
    "        self.list = lst\n",
    "        self.index = len(lst)\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "    def __next__(self):\n",
    "        self.index -= 1\n",
    "        if self.index >= 0:\n",
    "            return self.list[self.index]\n",
    "        else:\n",
    "            raise StopIteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "22d635d1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n",
      "8\n",
      "7\n",
      "6\n",
      "5\n",
      "4\n",
      "3\n",
      "2\n",
      "1\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "x = range(10)\n",
    "for i in ReverseListIterator(x):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8d64a0b",
   "metadata": {},
   "source": [
    "只要我们定义了这三个方法(`__init__, __iter__, __next__`)，我们可以返回任意迭代值：\n",
    "\n",
    "\n",
    "## 实现Collatz 猜想\n",
    "这里我们实现 Collatz 猜想：\n",
    "\n",
    "- 奇数 n：返回 3n + 1\n",
    "- 偶数 n：返回 n / 2\n",
    "- 直到 n 为 1 为止："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "1d2351b7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16\n",
      "8.0\n",
      "4.0\n",
      "2.0\n",
      "1.0\n"
     ]
    }
   ],
   "source": [
    "class Collatz(object):\n",
    "    def __init__(self, start):\n",
    "        self.value = start\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "    def __next__(self):\n",
    "        if self.value == 1:\n",
    "            raise StopIteration\n",
    "        elif self.value % 2 == 0:\n",
    "            self.value = self.value / 2\n",
    "        else:\n",
    "            self.value = 3 * self.value + 1\n",
    "        return self.value\n",
    "\n",
    "\n",
    "for x in Collatz(5):\n",
    "    print(x)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b2e367ed",
   "metadata": {},
   "source": [
    "不过迭代器对象存在状态，**有问题**："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "aedbed5c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "22 11.0\n",
      "34.0 17.0\n",
      "52.0 26.0\n",
      "13.0 40.0\n",
      "20.0 10.0\n",
      "5.0 16.0\n",
      "8.0 4.0\n",
      "2.0 1.0\n"
     ]
    }
   ],
   "source": [
    "i = Collatz(7)\n",
    "for x, y in zip(i, i):\n",
    "    print(x, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99574e91",
   "metadata": {},
   "source": [
    "解决方法是将迭代器和可迭代对象分开处理。\n",
    "\n",
    "## 迭代器和可迭代对象分开处理\n",
    "\n",
    "这里提供了一个二分树的中序遍历实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "cfdd9b57",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryTree(object):\n",
    "    def __init__(self, value, left=None, right=None):\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "    def __iter__(self):\n",
    "        return InorderIterator(self)\n",
    "\n",
    "class InorderIterator(object):\n",
    "    def __init__(self, node):\n",
    "        self.node = node\n",
    "        self.stack = []\n",
    "\n",
    "    def __next__(self):\n",
    "        if len(self.stack) > 0 or self.node is not None:\n",
    "            while self.node is not None:\n",
    "                self.stack.append(self.node)\n",
    "                self.node = self.node.left\n",
    "            node = self.stack.pop()\n",
    "            self.node = node.right\n",
    "            return node.value\n",
    "        else:\n",
    "            raise StopIteration()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ae7a1af",
   "metadata": {},
   "source": [
    "测试："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "a44462fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree = BinaryTree(\n",
    "    left=BinaryTree(\n",
    "        left=BinaryTree(1),\n",
    "        value=2,\n",
    "        right=BinaryTree(\n",
    "            left=BinaryTree(3),\n",
    "            value=4,\n",
    "            right=BinaryTree(5)\n",
    "        ),\n",
    "    ),\n",
    "    value=6,\n",
    "    right=BinaryTree(\n",
    "        value=7,\n",
    "        right=BinaryTree(8)\n",
    "    )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "44a4c893",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "for value in tree:\n",
    "    print(value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f61bbfde",
   "metadata": {},
   "source": [
    "不会出现之前的问题："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "f62c83f8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1\n",
      "2 2\n",
      "3 3\n",
      "4 4\n",
      "5 5\n",
      "6 6\n",
      "7 7\n",
      "8 8\n"
     ]
    }
   ],
   "source": [
    "for x, y in zip(tree, tree):\n",
    "    print(x, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "074cbf92",
   "metadata": {},
   "source": [
    "# 生成器\n",
    "\n",
    "在 Python 中，使用了 yield 的函数被称为生成器（generator）。\n",
    "\n",
    "跟普通函数不同的是，生成器是一个返回迭代器的函数，只能用于迭代操作，更简单点理解生成器就是一个迭代器。\n",
    "\n",
    "1. 迭代器则通过 next 的 return 将值返回；\n",
    "2. 与迭代器不同的是，生成器会自动记录当前的状态，\n",
    "而迭代器则需要进行额外的操作来记录当前的状态。\n",
    "\n",
    "之前的 collatz 猜想，简单循环的实现如下：\n",
    "\n",
    "collatz:\n",
    "\n",
    "- 奇数 n：返回 3n + 1\n",
    "- 偶数 n：返回 n / 2\n",
    "- 直到 n 为 1 为止："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "f6e958b4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16\n",
      "8.0\n",
      "4.0\n",
      "2.0\n",
      "1.0\n"
     ]
    }
   ],
   "source": [
    "def collatz(n):\n",
    "    sequence = []\n",
    "    while n != 1:\n",
    "        if n % 2 == 0:\n",
    "            n /= 2\n",
    "        else:\n",
    "            n = 3 * n + 1\n",
    "        sequence.append(n)\n",
    "    return sequence\n",
    "\n",
    "\n",
    "for x in collatz(5):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad7aff3f",
   "metadata": {},
   "source": [
    "生成器的版本如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "63359a5e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16\n",
      "8.0\n",
      "4.0\n",
      "2.0\n",
      "1.0\n"
     ]
    }
   ],
   "source": [
    "def collatz(n):\n",
    "    while n != 1:\n",
    "        if n % 2 == 0:\n",
    "            n /= 2\n",
    "        else:\n",
    "            n = 3 * n + 1\n",
    "        yield n\n",
    "\n",
    "\n",
    "for x in collatz(5):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "494a0da3",
   "metadata": {},
   "source": [
    "迭代器的版本如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "6f610971",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16\n",
      "8.0\n",
      "4.0\n",
      "2.0\n",
      "1.0\n"
     ]
    }
   ],
   "source": [
    "class Collatz(object):\n",
    "    def __init__(self, start):\n",
    "        self.value = start\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "    def next(self):\n",
    "        if self.value == 1:\n",
    "            raise StopIteration\n",
    "        elif self.value % 2 == 0:\n",
    "            self.value = self.value / 2\n",
    "        else:\n",
    "            self.value = 3 * self.value + 1\n",
    "        return self.value\n",
    "    \n",
    "for x in collatz(5):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ec99ef9",
   "metadata": {},
   "source": [
    "事实上，生成器也是一种迭代器："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "0fe93e4d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object collatz at 0x7f93ce863190>"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = collatz(5)\n",
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "faa64425",
   "metadata": {},
   "source": [
    "它支持 next 方法，返回下一个 yield 的值：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "b70e758b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "21513a65",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8.0"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea1ad6ab",
   "metadata": {},
   "source": [
    "`__iter__` 方法返回的是它本身："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "82b06a17",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object collatz at 0x7f93ce863190>"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.__iter__()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a308a1b",
   "metadata": {},
   "source": [
    "本节完。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3388e5d1",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}