Python Generator

  参考：

http://www.ibm.com/developerworks/cn/opensource/os-cn-python-yield/

http://blog.shine-it.net/python/dive-into-generator

 

您可能听说过，带有 yield 的函数在 Python 中被称之为 generator（生成器），何谓 generator ？

我们先抛开 generator，以一个常见的编程题目来展示 yield 的概念。

清单 1. 简单输出斐波那契數列前 N 个数

				
 def fab(max): 
    n, a, b = 0, 0, 1 
    while n < max: 
        print b 
        a, b = b, a + b 
        n = n + 1 

执行 fab(5)，我们可以得到如下输出：

 >>> fab(5) 
 1 
 1 
 2 
 3 
 5 

结果没有问题，但有经验的开发者会指出，直接在 fab 函数中用 print 打印数字会导致该函数可复用性较差，因为 fab 函数返回 None，其他函数无法获得该函数生成的数列。

要提高 fab 函数的可复用性，最好不要直接打印出数列，而是返回一个 List。以下是 fab 函数改写后的第二个版本：

清单 2. 输出斐波那契數列前 N 个数第二版

				
 def fab(max): 
    n, a, b = 0, 0, 1 
    L = [] 
    while n < max: 
        L.append(b) 
        a, b = b, a + b 
        n = n + 1 
    return L 

可以使用如下方式打印出 fab 函数返回的 List：

 >>> for n in fab(5): 
 ...     print n 
 ... 
 1 
 1 
 2 
 3 
 5 

改写后的 fab 函数通过返回 List 能满足复用性的要求，但是更有经验的开发者会指出，该函数在运行中占用的内存会随着参数 max 的增大而增大，如果要控制内存占用，最好不要用 List来保存中间结果，而是通过 iterable 对象来迭代。例如，在 Python2.x 中，代码：

清单 3. 通过 iterable 对象来迭代

				
 for i in range(1000): pass 

会导致生成一个 1000 个元素的 List，而代码：

 for i in xrange(1000): pass 

则不会生成一个 1000 个元素的 List，而是在每次迭代中返回下一个数值，内存空间占用很小。因为 xrange 不返回 List，而是返回一个 iterable 对象（满足iterator协议）。

迭代器(Iterator)概述
迭代器是访问集合内元素的一种方式。迭代器对象从集合的第一个元素开始访问，直到所有的元素都被访问一遍后结束。

迭代器不能回退，只能往前进行迭代。这并不是什么很大的缺点，因为人们几乎不需要在迭代途中进行回退操作。

迭代器也不是线程安全的，在多线程环境中对可变集合使用迭代器是一个危险的操作。但如果小心谨慎，或者干脆贯彻函数式思想坚持使用不可变的集合，那这也不是什么大问题。

对于原生支持随机访问的数据结构（如tuple、list），迭代器和经典for循环的索引访问相比并无优势，反而丢失了索引值（可以使用内建函数enumerate()找回这个索引值，这是后话）。但对于无法随机访问的数据结构（比如set）而言，迭代器是唯一的访问元素的方式。

迭代器的另一个优点就是它不要求你事先准备好整个迭代过程中所有的元素。迭代器仅仅在迭代至某个元素时才计算该元素，而在这之前或之后，元素可以不存在或者被销毁。这个特点使得它特别适合用于遍历一些巨大的或是无限的集合，比如几个G的文件，或是斐波那契数列等等。这个特点被称为延迟计算或惰性求值(Lazy evaluation)。

迭代器更大的功劳是提供了一个统一的访问集合的接口。只要是实现了__iter__()方法的对象，就可以使用迭代器进行访问。

Iterables, Iterators, and the Iterator Protocol

• Iterables are Python objects that define an __iter__() method, which, when called, returns an iterator.
• Iterators define the __iter__() method as well, but implement it by simply returning the iterator itself. Iterators also implement a next() method, which returns the next element in a sequence. To signal the end of a sequence, next() raises a StopIteration exception.
• Any object that implements both __iter__ and next in the aforementioned manner is said to implement the iterator protocol.
• 常用的几个内建数据结构tuple、list、set、dict都支持迭代器，字符串也可以使用迭代操作。你也可以自己实现一个迭代器，如上所述，只需要在类的__iter__方法中返回一个对象，这个对象拥有一个next()方法，这个方法能在恰当的时候抛出StopIteration异常即可。但是需要自己实现迭代器的时候不多，即使需要，使用生成器会更轻松。后面我们将讨论生成器的部分。

参考

　　iterator protocol 使得我们可以对不同的容器（其实是任何支持遍历操作的对象，不一定是用来存放数据的容器）使用相同的方式（for 语句）进行遍历。容器可以是 list, dictionary 或者是其他用户定义的数据结构，它只需要实现 iter()方法，返回一个 iterator object 即可。真正关心如何遍历的是 iterator object，它的两个方法构成了 iterator protocol。

• iter() 返回自身
• next() 返回容器中的下一个对象，没有更多对象时应 raise StopIteration，一旦抛出此异常，后续的调用一定也必须抛出此异常。

PythonDoc

　　container.iter() Return an iterator object 。
　　The iterator objects themselves are required to support the following two methods, which together form the iterator protocol:

• 2.1 iterator.iter() Return the iterator object itself. 
• 2.2 iterator.next() Return the next item from the container.
• Python’s generators provide a convenient way to implement the iterator protocol. If a container object’s iter() method is implemented as a generator, it will automatically return an iterator object (technically, a generator object) supplying the iter() and next() methods.
  
  
  ps: Python内置了一个模块itertools，包含了很多函数用于creating iterators for efficient looping（创建更有效率的循环迭代器）

利用 iterable 我们可以把 fab 函数改写为一个支持 iterable 的 class，以下是第三个版本的 Fab：

 

清单 4. 第三个版本

				
 class Fab(object): 

    def __init__(self, max): 
        self.max = max 
        self.n, self.a, self.b = 0, 0, 1 

    def __iter__(self): 
        return self 

    def next(self): 
        if self.n < self.max: 
            r = self.b 
            self.a, self.b = self.b, self.a + self.b 
            self.n = self.n + 1 
            return r 
        raise StopIteration() 

Fab 类通过 next() 不断返回数列的下一个数，内存占用始终为常数：

 >>> for n in Fab(5): 
 ...     print n 
 ... 
 1 
 1 
 2 
 3 
 5 

然而，使用 class 改写的这个版本，代码远远没有第一版的 fab 函数来得简洁。如果我们想要保持第一版 fab 函数的简洁性，同时又要获得 iterable 的效果，yield 就派上用场了：

清单 5. 使用 yield 的第四版

				
 def fab(max): 
    n, a, b = 0, 0, 1 
    while n < max: 
        yield b 
        # print b 
        a, b = b, a + b 
        n = n + 1 

'''

第四个版本的 fab 和第一版相比，仅仅把 print b 改为了 yield b，就在保持简洁性的同时获得了 iterable 的效果。

调用第四版的 fab 和第二版的 fab 完全一致：

 >>> for n in fab(5): 
 ...     print n 
 ... 
 1 
 1 
 2 
 3 
 5 

简单地讲，yield 的作用就是把一个函数变成一个 generator，带有 yield 的函数不再是一个普通函数，Python 解释器会将其视为一个 generator，调用 fab(5) 不会执行 fab 函数，而是返回一个 iterable 对象！在 for 循环执行时，每次循环都会执行 fab 函数内部的代码，执行到 yield b 时，fab 函数就返回一个迭代值，下次迭代时，代码从 yield b 的下一条语句继续执行，而函数的本地变量看起来和上次中断执行前是完全一样的，于是函数继续执行，直到再次遇到 yield。

也可以手动调用 fab(5) 的 next() 方法（因为 fab(5) 是一个 generator 对象，该对象具有 next() 方法），这样我们就可以更清楚地看到 fab 的执行流程：

清单 6. 执行流程

				
 >>> f = fab(5) 
 >>> f.next() 
 1 
 >>> f.next() 
 1 
 >>> f.next() 
 2 
 >>> f.next() 
 3 
 >>> f.next() 
 5 
 >>> f.next() 
 Traceback (most recent call last): 
  File "<stdin>", line 1, in <module> 
 StopIteration 

当函数执行结束时，generator 自动抛出 StopIteration 异常，表示迭代完成。在 for 循环里，无需处理 StopIteration 异常，循环会正常结束。

我们可以得出以下结论：

一个带有 yield 的函数就是一个 generator，它和普通函数不同，生成一个 generator 看起来像函数调用，但不会执行任何函数代码，直到对其调用 next()（在 for 循环中会自动调用 next()）才开始执行。虽然执行流程仍按函数的流程执行，但每执行到一个 yield 语句就会中断，并返回一个迭代值，下次执行时从 yield 的下一个语句继续执行。看起来就好像一个函数在正常执行的过程中被 yield 中断了数次，每次中断都会通过 yield 返回当前的迭代值。

yield 的好处是显而易见的，把一个函数改写为一个 generator 就获得了迭代能力，比起用类的实例保存状态来计算下一个 next() 的值，不仅代码简洁，而且执行流程异常清晰。

generator函数的一大功用是能非常便利的编写获得一个 iterator
你不必再去关心神马iterator协议（比如 .next, .__iter__, 诸如此类）

如何判断一个函数是否是一个特殊的 generator 函数？可以利用 isgeneratorfunction 判断：

清单 7. 使用 isgeneratorfunction 判断

				
 >>> from inspect import isgeneratorfunction 
 >>> isgeneratorfunction(fab) 
 True 

要注意区分 fab 和 fab(5)，fab 是一个 generator function，而 fab(5) 是调用 fab 返回的一个 generator，好比类的定义和类的实例的区别：

清单 8. 类的定义和类的实例

				
 >>> import types 
 >>> isinstance(fab, types.GeneratorType) 
 False 
 >>> isinstance(fab(5), types.GeneratorType) 
 True 

fab 是无法迭代的，而 fab(5) 是可迭代的：

 >>> from collections import Iterable 
 >>> isinstance(fab, Iterable) 
 False 
 >>> isinstance(fab(5), Iterable) 
 True 

每次调用 fab 函数都会生成一个新的 generator 实例，各实例互不影响：

 >>> f1 = fab(3) 
 >>> f2 = fab(5) 
 >>> print 'f1:', f1.next() 
 f1: 1 
 >>> print 'f2:', f2.next() 
 f2: 1 
 >>> print 'f1:', f1.next() 
 f1: 1 
 >>> print 'f2:', f2.next() 
 f2: 1 
 >>> print 'f1:', f1.next() 
 f1: 2 
 >>> print 'f2:', f2.next() 
 f2: 2 
 >>> print 'f2:', f2.next() 
 f2: 3 
 >>> print 'f2:', f2.next() 
 f2: 5 

 

另一个 yield 的例子来源于文件读取。如果直接对文件对象调用 read() 方法，会导致不可预测的内存占用。好的方法是利用固定长度的缓冲区来不断读取文件内容。通过 yield，我们不再需要编写读文件的迭代类，就可以轻松实现文件读取：（使用generator expression可以更简洁，见后文）

清单 9. 另一个 yield 的例子

				
 def read_file(fpath): 
    BLOCK_SIZE = 1024 
    with open(fpath, 'rb') as f: 
        while True: 
            block = f.read(BLOCK_SIZE) 
            if block: 
                yield block 
            else: 
                return 

---

 

我们目前有两种创建generator对象的方法： Yield expressions

• Generator函数：  yield_expression ::= "yield" [expression_list]

def countdown(n):
　　while n > 0:
　　　　yield n
　　　　n -= 1

• Generator 表达式： yield_atom ::= "(" yield_expression ")"

　　squares = (x*x for x in s)

1.需要注意yield_atom ::= "(" yield_expression ")"方式和列表推导式(list comprehension)的区别：

>>> a = (x  for x in range(10))
>>> a
<generator object <genexpr> at 0x7f7bd7007b40>
>>> a = [x  for x in range(10)]
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

• 结果的值是通过generator一次一个生成出来的
• 与列表推导式的重要不同是

不会构建一个列表
唯一用途是遍历枚举
一旦被消费，无法重用

2.这种生成generator的方式也可以变得复杂：

　　如果if子句里的条件需要计算，同时结果也需要进行同样的计算，不希望计算两遍，就像这样：

　　　　　   (x.doSomething() for x in lst if x.doSomething()>0)

　　　　如果doSomething的代价比较大，有没有办法优化呢？可以这样改写：　　　　

　　(x for x in (y.doSomething() for y in lst) if x>0)
内部的列表解析变量其实也可以用x，但为清晰起见我们改成了y。或者更清楚的，可以写成两个表达式：

　　tmp = (x.doSomething() for x in lst)
　　(x for x in tmp if x > 0)
列表解析可以替代绝大多数需要用到map和filter的场合，可能正因为此，著名的静态检查工具pylint将map和filter的使用列为了警告

 3.另附set，map，list的compresions：

>>> from math import pi
>>> [str(round(pi, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

矩阵的转职
>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]
The following list comprehension will transpose rows and columns:
>>>
>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]
>>> transposed = []
>>> for i in range(4):
...     transposed.append([row[i] for row in matrix])
...
同
>>> zip(*matrix)
[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]


Similarly to list comprehensions, set comprehensions are also supported:
>>>
>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
set(['r', 'd'])

In addition, dict comprehensions can be used to create dictionaries from arbitrary key and value expressions:
>>>
>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

 

---

文件处理

• 一个非-Generator 的解决方案

仅仅简单的使用一个for循环

wwwlog = open("access-log")
total = 0
for line in wwwlog:
    bytestr = line.rsplit(None, 1)[1]
    if bytestr != '-':
        total += int(bytestr)

print "Total", total
    

我们一行一行的读取值并更新汇总数据

可是，这个程序竟然运行了90秒钟...

• 一个Generator的解决方案

我们会用到一些generator表达式

wwwlog = open("access-log")
bytecolumn = (line.rsplit(None, 1)[1] for line in wwwlog)
bytes = (int(x) for x in bytecolumn if x != '-')
print "Total", sum(bytes)

              +--------+    +------------+    +-------+    +-------+
access-log -> | wwwlog | -> | bytecolumn | -> | bytes | -> | sum() | -> total
              +--------+    +------------+    +-------+    +-------+

---

Added 2013 0506 

Iterator Types¶

New in version 2.2.

Python supports a concept of iteration over containers. This is implemented using two distinct methods; these are used to allow user-defined classes to support iteration. Sequences, described below in more detail, always support the iteration methods.

One method needs to be defined for container objects to provide iteration support:

container.__iter__()

Return an iterator object. The object is required to support the iterator protocol described below. If a container supports different types of iteration, additional methods can be provided to specifically request iterators for those iteration types. (An example of an object supporting multiple forms of iteration would be a tree structure which supports both breadth-first and depth-first traversal.) This method corresponds to the tp_iterslot of the type structure for Python objects in the Python/C API.

The iterator objects themselves are required to support the following two methods, which together form the iterator protocol:

iterator.__iter__()

Return the iterator object itself. This is required to allow both containers and iterators to be used with the for and instatements. This method corresponds to the tp_iter slot of the type structure for Python objects in the Python/C API.

iterator.next()

Return the next item from the container. If there are no further items, raise the StopIteration exception. This method corresponds to the tp_iternext slot of the type structure for Python objects in the Python/C API.