Question

斐波那契数列相信大家都不陌生，这是常见的编程题目，也是很多书籍中喜欢引用的例子。我们这里也不免落于俗套，就以这个例子开场吧。斐波那契是一个简单的递归数列，数列满足这样的规律：除了前两个数，任何其他数都可以由其前面两个数相加得到，即f(N)=f(N-1)+f(N-2)，n>2。Python中有多种方法实现这个数列，我们来看其中的一种。

>>> def fab(n):
...   i,a,b = 0,0,1
...   foblist = []
...   while i < n:
...       foblist.append(b)
...       a,b = b,a+b           #
不借助中间变量交换两个变量的方法
...       i = i+1
...   return foblist
...
>>> print fab(4)
[1, 1, 2, 3]

想一想，上面的例子有没有更好的实现方法呢？显然有！在介绍具体实现之前我们先来了解生成器的有关知识。

生成器的语法在Python2.2中就引入了，但实际应用过程中还是有人不会选择使用它，特别是有过其他语言基础的，主要是思维上难以转换过来。生成器的概念其实非常简单，如果一个函数体中包含有yield语句，则称为生成器（generator），它是一种特殊的迭代器（iterator），也可以称为可迭代对象（iterable）。可迭代对象、迭代器、生成器这三者之间的关系可以简单地表示成如图8-4所示的形式。

图8-4　可迭代对象、迭代器、生成器三者之间的关系

对生成器的调用会返回一个迭代器，使用next()方法可以获取下一个元素或者抛出StopIteration异常。

>>> def mygen(x):
...   for i in range(x):
...      yield i 
...
>>> d = mygen(1)
>>> d                  #
生成器对象，拥有iter()
和next()
方法
<generator object mygen at 0x005162B0>
>>> d.next()
0
>>> d.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>

实际上当需要在循环过程中依次处理一个序列中的元素的时候，就应该考虑生成器。当然，要深入理解生成器，必须透彻理解yield语句。yield语句与return语句相似，当解释器执行遇到yield的时候，函数会自动返回yield语句之后的表达式的值。不过与return不同的是，yield语句在返回的同时会保存所有的局部变量以及现场信息，以便在迭代器调用next()或者send()方法的时候还原，而不是直接交给垃圾回收器（return()方法返回后这些信息会被垃圾回收器处理）。这样就能够保证对生成器的每一次迭代都会返回一个元素，而不是一次性在内存中生成所有的元素。自Python2.5开始，yield语句变为表达式，可以直接将其值赋给其他变量，如x=(yield y)。结合一个例子来看yield语句在生成器函数调用的时候执行状态，下面的函数代表数列1，-3，5，-7，9，……。

>>> def series():
...   print "begin:"
...   m=1.0; n = 1
...   print "while begin"               
①
...   while(1):                     
②
...       print "yield a data"
...       yield m/n                 
③
...       m = m+2                 
④
...       n = n* -1
...       print "end"
...
>>>

上面的代码用状态机可以表示为如图8-5所示的形式。状态机中状态1表示从函数定义到标注1处的所有语句的集合，状态2表示标注2的语句，状态3表示标注2到3之间的所有语句的集合，状态4表示从标注4后到结束的语句。

图8-5　示例程序的状态机形式的表示

运行上面的程序你会惊讶地发现，即使while中的条件永远为真，代码也不会陷入无限循环的状态，而是每调用一次next()方法产生一个数，这样生成器的优势就体现出来了。

>>> d = series()
>>> d.next()      #
第一次调用next
执行到状态2
，循环条件为1
，转到状态3
，遇到yield
语句返回对
            #
应的值并保留现场
begin:
while begin
yield a data
1.0
>>> d.next()      #
之后每次调用d.next()
从状态3
开始转向状态4
，也就是yield
语句之后的第一句
            #
语句开始执行，4
直接转到2
，循环条件永远为真，从而再次转到状态3
end
yield a data
-3.0

生成器的优点总体来说有如下几条：

生成器提供了一种更为便利的产生迭代器的方式，用户一般不需要自己实现__iter__和next方法，它默认返回一个迭代器。

代码更为简洁、优雅。

充分利用了延迟评估（Lazy evaluation）的特性，仅在需要的时候才产生对应的元素，而不是一次生成所有的元素，从而节省了内存空间，提高了效率，理论上无限循环成为可能而不会导致MemoryError，这在大数据处理的情形下尤为重要。

使得协同程序更为容易实现。协同程序是有多个进入点，可以挂起恢复的函数，这基本就是yield的工作方式。Python2.5之后生成器的功能更加完善，加入了send()、close()和throw()方法。其中send()不仅可以传递值给yield语句，而且能够恢复生成器，因此生成器能大大简化协同程序的实现。

现在我们回过头来看看本节开头的例子，使用生成器来实现是不是更为简洁呢？

>>> def fib(n):
...   a = b =1
...   for i in range(n):
...      yield a
...      a,b = b,a+b
...