python中的生成器

发表于 更新于 分类于 Disqus：

目录

可迭代对象

要想理解python中的生成器，得先从可迭代对象Iterable说起。什么是可迭代对象呢？

定义了可以返回一个迭代器的__iter__方法的对象，或者定义了可以支持下标索引的__getitem__方法的对象，就是一个可迭代对象

所以我们可以用如下方法来判断一个实例是否为可迭代对象

1
2
3
4
5
6
7
8
hasattr((1,2,3), '__iter__') # True

hasattr([1,2,3], '__iter__') # True

hasattr({}, '__iter__') # True

hasattr('abc', '__getitem__') # True

知道了可迭代对象的定义，那么可迭代对象又有什么用呢，如下列所示，我们经常在python中使用for…in循环，那么for…in循环能在所有对象上使用吗？

1
2
3
4
5
6
my_list = [1, 2, 3]
for i in my_list:
  print(i) 
# 1 
# 2 
# 3

其实不然，只有在可迭代对象上，for…in循环才能使用，比如列表，元组，字典以及字符串。这就是可迭代对象的最大用途。然而问题有来了，这些可迭代对象虽然好用，但是它们却又一大弊端。可迭代对象在使用时，比如my_list，它会把列表[1, 2, 3]中所有元素都存贮在内存中，当列表长度非常可观时，python会遇到性能方面的问题(python2.7中range函数返回可迭代对象，xrange函数返回生成器，所以可以通过比较这两个函数的执行相同任务时间来直观的了解性能方面的问题，stackoverflow上便有回答来比较这两个函数的执行时间，问题链接点此)。

迭代器

对于上述列表对象遇到的性能问题，我们自然会问到有没有方法来解决这样的问题。比如，有没有一种类似列表的对象，但是它不会一下子把它所有的元素都放到内存里的对象？
有，它就是迭代器，还是先说迭代器Iterator的定义

定义了返回迭代器对象本身__iter()__(Python2)方法的对象，或者定义了方法返回容器的下一个元素__next__方法的对象，就是一个迭代器。

同时我们也说，实现了上述两个方法的对象是遵守了迭代器协议（iterator protocol）的对象。

判断一个对象我们除了可以检查它有没有__iter()__和__next__方法外，我们也可以用isinstance()方法。如下所示

1
2
3
4
5
6
7
8
9
10
11
from collections import Iterator

isinstance((1,2,3), Iterator) # False

isinstance([1,2,3], Iterator) # False

isinstance({}, Iterator) # False

isinstance('abc', Iterator) # False

isinstance((x for x in [1,2,3]), Iterator) # True

这下我们发现，元组，列表，字典，字符串都是可迭代对象，但同时它们也都不是迭代器。谁是迭代器呢？从上面例子可看到(x for x in [1,2,3])是迭代器对象的实例。

首先，为什么元组，列表，字典，字符串都不是迭代器Iterator呢？

这是因为Python的Iterator对象表示的是一个数据流，Iterator对象可以被next()函数调用并不断返回下一个数据，直到没有数据时抛出StopIteration错误。可以把这个数据流看做是一个有序序列，但我们却不能提前知道序列的长度，只能不断通过next()函数实现按需计算下一个数据，所以Iterator的计算是惰性的，只有在需要返回下一个数据时它才会计算。

从以上摘自廖雪峰官网上的解答中我们可以看出，迭代器表示一个数据流，它不会把这个数据流中每一个元素都存贮在内存中，而列表则不同，它会把列表中所有元素都存贮在内存中。

对于第二个问题，为什么(x for x in [1,2,3])是迭代器对象的实例呢？

1
2
3
4
5
6
7
8
9
from collections import Iterator

isinstance(iter((1,2,3)), Iterator) # True

isinstance(iter([1,2,3]), Iterator) # True

isinstance(iter({}), Iterator) # True

isinstance(iter('abc'), Iterator) # True

从以上例子可以看出，虽然元组，列表，字典，字符串都不是迭代器，但是通过iter()函数，可以获得一个Iterator对象。

所以Python的for循环本质上可以看做先通过iter()函数，获得一个迭代器Iterator对象，再在这个迭代器对象上通过不断调用next()函数实现的。

生成器

在了解了可迭代对象Iterable和迭代器Iterator的概念后，我们终于可以开始探讨生成器的概念了。

先放概念

生成器是一种迭代器，但是只能对其迭代一次。因为它们并没有把所有的值存在内存中，而是在运行时生成值。生成器可通过遍历来使用它们，要么用一个“for”循环，要么将它传递给任意可以进行迭代的函数和结构。

1
2
3
4
5
6
7
8
9
my_generator = (x for x in [1,2,3])
for i in my_generator:
  print(i)
# 1
# 2
# 3
for i in my_generator:
  print(i)
# nothing happens

上面是生成器的一个简单的例子，这个例子有点像for…in循环输出my_list的例子，除了这里用了一个迭代器(x for x in [1,2,3])替换了可迭代对象[1,2,3]。它们有什么不同吗？仔细观察上例，当我们再次使用for…in循环输出my_generator时，什么都没有发生，这也就是定义中说的

生成器是一种迭代器，但是只能对其迭代一次。

因为生成器首先生成1，接着从内存中清空1，接下来生成2，接着从内存中清空2，最后生成3，接着从内存中清空3。

关键词Yield

我们知道了一种由迭代器来获得生成器的方式，那么还有其他的方式来获得生成器吗？用Python关键词yield就可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
def createGenerator():
  my_list = [1,2,3]
  for i in my_list:
    yield i

my_generator = createGenerator()
print(my_generator) # <generator object createGenerator at 0x7ff6a5c785c8>

for i in my_generator:
  print(i)
# 1
# 2
# 3

虽然上面的例子没有人在实际中会使用，但是用它来了解yield的用法还是很通俗易懂的。关于yield的难点，首先我们可以看到，通过createGenerator()函数来获得生成器my_generator时，函数createGenerator()并没有被执行，它只是返回了一个位于内存中处于某个位置上的该生成器对象。直到我们用for…in循环作用于这个对象上时，函数createGenerator()才被真正的执行，我们可以把它当做是一种惰性求值。

那么生成器my_generator是如何求值的呢？当for…in循环第一次调用生成器时，createGenerator()被执行，直到被执行到yield关键词这里，返回循环的第一个值。余下的循环在调用生成器时，会继续上次的循环，再次遇到yield关键词时返回这一次循环的值，直到循环结束，再也遇不到yield关键词为止。

什么时候使用生成器

生成器的一个典型应用场景是：你不想把同一时间将所有计算出来的大量结果贮存到内存中，因为这样做会消耗大量资源，所以使用生成器来进行惰性求值，只有在需要某个结果时，再计算该结果。

举一个生成斐波那契数列的例子

1
2
3
4
5
6
7
def listFibonacci(n):
  a = b = 1
  fib_list = []
  for i in range(n):
    fib_list.append(a)
    a, b = b, a + b
  return fib_list

当输入参数很大时，内存资源会被严重消耗。

下面是该函数的生成器版本

1
2
3
4
5
def genFibonacci(n):
  a = b = 1
  for i in range(n):
    yield a
    a, b = b, a + b

由于惰性求值的缘故，即便参数很大时，我们也不用担心内存资源的消耗。

我们刚刚谈到了内存消耗情况，有什么工具能帮助我们直观的感受到内存的消耗呢？ python有个叫memory_profiler的工具可以来帮我们进行内存消耗情况的测试。为了对比上述两个方法的内存消耗，我们让这两个方法同时生100000个斐波那契数列，并观察内存消耗情况。

测试listFibonacci()代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from memory_profiler import profile

def listFibonacci(n):
  a = b = 1
  fib_list = []
  for i in range(n):
    fib_list.append(a)
    a, b = b, a + b
  return fib_list

@profile
def testListFib():
  for i in listFibonacci(100000):
    pass

if __name__ == '__main__':
    testListFib()

测试genFibonacci()代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from memory_profiler import profile

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

@profile
def testGenFib():
  for i in genFibonacci(100000):
    pass
 
if __name__ == '__main__':
  testGenFib()

使用listFibonacci()测试结果如下

1
2
3
4
5
6
7
8
Filename: listFib.py

Line #    Mem usage    Increment   Line Contents
================================================
    11     14.2 MiB      0.0 MiB   @profile
    12                             def testListFib():
    13    460.5 MiB    446.2 MiB     for i in listFibonacci(100000):
    14    460.5 MiB      0.0 MiB       pass

使用genFibonacci()测试结果如下

1
2
3
4
5
6
7
8
Filename: genFib.py

Line #    Mem usage    Increment   Line Contents
================================================
     9     14.4 MiB      0.0 MiB   @profile
    10                             def testGenFib():
    11     14.4 MiB      0.0 MiB     for i in genFibonacci(100000):
    12     14.4 MiB      0.0 MiB       pass

从上面的测试结果可以看出，在生成大于100000个斐波那契数列的任务中，listFibonacci()消耗了460.5 MiB内存，而genFibonacci()只消耗了14.4 MiB内存。其实，如果我们绘制一个内存消耗随生成斐波那契数列长度变化的折线图，我们可以发现，随着生成斐波那契数列长度的增加，listFibonacci()的内存消耗情况是指数递增的，而genFibonacci()的内存消耗情况则是不变的，总是维持在消耗14.4 MiB 左右。通过这个测试，我们可以直观的感受到，在计算大量不需要被保存结果且只需计算一次的任务下，我们为什么不用担心生成器对内存资源的消耗。

从Design Pattern角度看生成器

如果从Design Pattern的角度来看生成器，生成器就是一个无参数版本的工厂模式。通常工厂模式需要通过参数来确定生成什么对象以及如何生成该对象，但是生成器则不需要参数，它通过内部算法来确定生成什么对象以及如何生成该对象。

参考

  1. Stackoverflow, What does the “yield” keyword do?
  2. 廖雪峰的官方网站, 迭代器
  3. 极客学院, 迭代器
  4. Bruce Eckel, Thinking in Python