Tips/2016-04-13-Iterator-Tools.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python 迭代器工具\n",
    "\n",
    "[0x01](https://github.com/rainyear/pytips/blob/master/Markdowns/2016-03-07-iterator-and-generator.md) 介绍了迭代器的概念，即定义了 `__iter__()` 和 `__next__()` 方法的对象，或者通过 `yield` 简化定义的“可迭代对象”，而在一些函数式编程语言（见 [0x02 Python 中的函数式编程](https://github.com/rainyear/pytips/blob/master/Markdowns/2016-03-08-Functional-Programming-in-Python.md)）中，类似的迭代器常被用于产生特定格式的列表（或序列），这时的迭代器更像是一种数据结构而非函数（当然在一些函数式编程语言中，这两者并无本质差异）。Python 借鉴了 `APL, Haskell, and SML` 中的某些迭代器的构造方法，并在 [`itertools`](https://docs.python.org/3/library/itertools.html) 中实现（该模块是通过 C 实现，源代码：[/Modules/itertoolsmodule.c](https://github.com/rainyear/cpython/blob/master/Modules%2Fitertoolsmodule.c)）。\n",
    "\n",
    "`itertools` 模块提供了如下三类迭代器构建工具：\n",
    "\n",
    "1. 无限迭代\n",
    "2. 整合两序列迭代\n",
    "3. 组合生成器\n",
    "\n",
    "#### 1. 无限迭代\n",
    "\n",
    "所谓**无限（infinite）**是指如果你通过 `for...in...` 的语法对其进行迭代，将陷入无限循环，包括：\n",
    "\n",
    "1. `count(start, [step])`\n",
    "2. `cycle(p)`\n",
    "3. `repeat(elem [,n])`\n",
    "\n",
    "从名字大概可以猜出它们的用法，既然说是无限迭代，我们自然不会想要将其所有元素依次迭代取出，而通常是结合 `map`/`zip` 等方法，将其作为一个取之不尽的数据仓库，与有限长度的可迭代对象进行组合操作："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "count(start=0, step=1) --> count object\n",
      "\n",
      "Return a count object whose .__next__() method returns consecutive values.\n",
      "Equivalent to:\n",
      "\n",
      "    def count(firstval=0, step=1):\n",
      "        x = firstval\n",
      "        while 1:\n",
      "            yield x\n",
      "            x += step\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from itertools import cycle, count, repeat\n",
    "print(count.__doc__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]\n",
      "Odd#1\n",
      "Odd#3\n"
     ]
    }
   ],
   "source": [
    "counter = count()\n",
    "print(next(counter))\n",
    "print(next(counter))\n",
    "print(list(map(lambda x, y: x+y, range(10), counter)))\n",
    "\n",
    "odd_counter = map(lambda x: 'Odd#{}'.format(x), count(1, 2))\n",
    "print(next(odd_counter))\n",
    "print(next(odd_counter))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cycle(iterable) --> cycle object\n",
      "\n",
      "Return elements from the iterable until it is exhausted.\n",
      "Then repeat the sequence indefinitely.\n"
     ]
    }
   ],
   "source": [
    "print(cycle.__doc__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 0)]\n",
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "cyc = cycle(range(5))\n",
    "print(list(zip(range(6), cyc)))\n",
    "print(next(cyc))\n",
    "print(next(cyc))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "repeat(object [,times]) -> create an iterator which returns the object\n",
      "for the specified number of times.  If not specified, returns the object\n",
      "endlessly.\n"
     ]
    }
   ],
   "source": [
    "print(repeat.__doc__)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Py', 'Py', 'Py']\n",
      "[('p', 'y'), ('p', 'y'), ('p', 'y')]\n"
     ]
    }
   ],
   "source": [
    "print(list(repeat('Py', 3)))\n",
    "rep = repeat('p')\n",
    "print(list(zip(rep, 'y'*3)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2. 整合两序列迭代\n",
    "\n",
    "所谓整合两序列，是指**以两个有限序列为输入，将其整合操作之后返回为一个迭代器**，最为常见的 `zip` 函数就属于这一类别，只不过 `zip` 是内置函数。这一类别完整的方法包括：\n",
    "\n",
    "1. `accumulate()`\n",
    "2. `chain()`/`chain.from_iterable()`\n",
    "3. `compress()`\n",
    "4. `dropwhile()`/`filterfalse()`/`takewhile()`\n",
    "5. `groupby()`\n",
    "6. `islice()`\n",
    "7. `starmap()`\n",
    "8. `tee()`\n",
    "9. `zip_longest()`\n",
    "\n",
    "这里就不对所有的方法一一举例说明了，如果想要知道某个方法的用法，基本通过 `print(method.__doc__)` 就可以了解，毕竟 `itertools` 模块只是提供了一种快捷方式，并没有隐含什么深奥的算法。这里只对下面几个我觉得比较有趣的方法进行举例说明。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['P', 'P']\n",
      "['P', 'Y']\n",
      "[0, 1, 2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "from itertools import cycle, compress, islice, takewhile, count\n",
    "\n",
    "# 这三个方法（如果使用恰当）可以限定无限迭代\n",
    "# print(compress.__doc__)\n",
    "print(list(compress(cycle('PY'), [1, 0, 1, 0])))\n",
    "\n",
    "# 像操作列表 l[start:stop:step] 一样操作其它序列\n",
    "# print(islice.__doc__)\n",
    "print(list(islice(cycle('PY'), 0, 2)))\n",
    "\n",
    "# 限制版的 filter\n",
    "# print(takewhile.__doc__)\n",
    "print(list(takewhile(lambda x: x < 5, count())))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "groupby(iterable[, keyfunc]) -> create an iterator which returns\n",
      "(key, sub-iterator) grouped by each value of key(value).\n",
      "\n",
      "A ['A', 'A']\n",
      "B ['B', 'B']\n",
      "C ['C']\n",
      "c, c++\n",
      "python, ruby\n"
     ]
    }
   ],
   "source": [
    "from itertools import groupby\n",
    "from operator import itemgetter\n",
    "print(groupby.__doc__)\n",
    "\n",
    "for k, g in groupby('AABBC'):\n",
    "    print(k, list(g))\n",
    "db = [dict(name='python', script=True),\n",
    "      dict(name='c', script=False),\n",
    "      dict(name='c++', script=False),\n",
    "      dict(name='ruby', script=True)]\n",
    "keyfunc = itemgetter('script')\n",
    "\n",
    "db2 = sorted(db, key=keyfunc) # sorted by `script'\n",
    "for isScript, langs in groupby(db2, keyfunc):\n",
    "    print(', '.join(map(itemgetter('name'), langs)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('A', '1'), ('B', '2'), ('C', '3'), ('D', 0)]\n"
     ]
    }
   ],
   "source": [
    "from itertools import zip_longest\n",
    "\n",
    "# 内置函数 zip 以较短序列为基准进行合并，\n",
    "# zip_longest 则以最长序列为基准，并提供补足参数 fillvalue\n",
    "# Python 2.7 中名为 izip_longest\n",
    "\n",
    "print(list(zip_longest('ABCD', '123', fillvalue=0)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3. 组合生成器\n",
    "\n",
    "关于生成器的排列组合：\n",
    "\n",
    "1. `product(*iterables, repeat=1)`：两输入序列的笛卡尔乘积\n",
    "2. `permutations(iterable, r=None)`：对输入序列的完全排列组合\n",
    "3. `combinations(iterable, r)`：有序版的排列组合\n",
    "4. `combinations_with_replacement(iterable, r)`：有序版的笛卡尔乘积"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, 0), (0, 1), (1, 0), (1, 1)]\n",
      "[('A', 'A'), ('A', 'B'), ('B', 'A'), ('B', 'B')]\n"
     ]
    }
   ],
   "source": [
    "from itertools import product, permutations, combinations, combinations_with_replacement\n",
    "print(list(product(range(2), range(2))))\n",
    "print(list(product('AB', repeat=2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('A', 'A'), ('A', 'B'), ('B', 'B')]\n"
     ]
    }
   ],
   "source": [
    "print(list(combinations_with_replacement('AB', 2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('B', 'A'), ('B', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'A'), ('C', 'B'), ('C', 'D'), ('C', 'E'), ('D', 'A'), ('D', 'B'), ('D', 'C'), ('D', 'E'), ('E', 'A'), ('E', 'B'), ('E', 'C'), ('E', 'D')]\n"
     ]
    }
   ],
   "source": [
    "# 赛马问题：4匹马前2名的排列组合（A^4_2）\n",
    "print(list(permutations('ABCDE', 2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]\n"
     ]
    }
   ],
   "source": [
    "# 彩球问题：4种颜色的球任意抽出2个的颜色组合（C^4_2）\n",
    "print(list(combinations('ABCD', 2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 总结\n",
    "\n",
    "迭代器工具在产生数据的时候将会显得非常便捷、高效，掌握了这些基本的方法之后，通过简单的组合就可以获得更多迭代器工具。"
   ]
  }
 ],
 "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.5.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}