Python学习笔记（9）-迭代器与生成器

前言

在学Python时，我对于生成器和迭代器理解得不清楚，检索到了一篇文章，把这两个东西讲得很透，应该是我能找到的最好的理解迭代器与生成器的文章，原文是《完全理解Python迭代对象、迭代器、生成器》，原文章作者提到，他是参考了别人的另外一篇文章写的，另外的文章题目是《Iterables vs. Iterators vs. Generators》。

数据结构背景

在了解迭代器与生成器之前，需要了解一下Python的一些数据结构方面的知识，下图说明了容器(container)、可迭代对象(iterable)、迭代器(iterator)、生成器(generator)、列表/集合/字典推导式(list,set,dict comprehension)这些概念的关系图：

容器(container)

容器是一种把多个元素组织在一起的数据结构，容器中的元素可以逐个地迭代获取，可以用in, not in关键字判断元素是否包含在容器中。通常这类数据结构把所有的元素存储在内存中（也有一些特例，并不是所有的元素都放在内存，比如迭代器和生成器对象）在Python中，常见的容器对象有：

1. list, deque（双端队列）, ….
2. set, frozensets, ….
3. dict, defaultdict, OrderedDict, Counter, ….
4. tuple, namedtuple, …
5. str

容器比较容易理解，因为你就可以把它看作是一个盒子、一栋房子、一个柜子，里面可以塞任何东西。从技术角度来说，当它可以用来询问某个元素是否包含在其中时，那么这个对象就可以认为是一个容器，比如 list，set，tuples都是容器对象，看下面的案例：

assert()函数

关于assert这个函数，这个函数是Python断言句，它的功能就是判断某个表达式是否为真，运行后，如果什么都不返回，它就是True，如果语句是假，就返回异常，看一个案例，如下所示：

>>> assert 1 in [11,22,33] # 1不在[11,22,33]里面，这个表达式就是False，返回异常
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError
>>> assert 2 < 1 # 2小于1，是False，返回异常
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError
>>> assert 1 in [1,2,3] # 1在[1,2,3]里，是True，不返回任何信息

再继续看容器的相关知识。可以寻问某元素是否在dict中用dict中的key：

>>> d = {1:'foo',2:'bar',3:'qux'} # dict
>>> print(d)
{1: 'foo', 2: 'bar', 3: 'qux'}
>>> assert 1 in d
>>> 1 in d
True
>>> assert 'foo' not in d # 'foo'不是d的元素，它只是一个值，不是key
>>>

询问某substring是否在string中：

>>> s = 'test'
>>> assert 'a' in s
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError
>>> assert 'a' not in s
>>> assert 'te' in s
>>>

尽管绝大多数容器都提供了某种方式来获取其中的每一个元素，但这并不是容器本身提供的能力，而是可迭代对象赋予了容器这种能力，当然并不是所有的容器都是可迭代的，比如：Bloom filter（布隆过滤器），虽然Bloom filter可以用来检测某个元素是否包含在容器中，但是并不能从容器中获取其中的每一个值，因为Bloom filter压根就没把元素存储在容器中，而是通过一个散列函数映射成一个值保存在数组中。

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

可迭代对象（iterable）

很多容器都是可迭代对象，此外还有更多的对象同样也是可迭代对象，比如处于打开状态的files，sockets等等。但凡是可以返回一个迭代器的对象都可称之为可迭代对象，看下面的例子：

>>> x = [1,2,3]
>>> y = iter(x) #创建迭代对象
>>> print(y)
<list_iterator object at 0x000001F8308B7470>
>>> z = iter(x)
>>> next(y)
1
>>> next(y)
2
>>> next(z)
1
>>> type(x)
<class 'list'>
>>> type(y)
<class 'list_iterator'>

代码解释：在这段代码中，x是一个可迭代对象，可迭代对象和容器一样是一种总称，范围很大，在Python中，它并不是指某种具体的数据类型，例如list是可迭代对象，dict是可迭代对象，set也是可迭代对象。在这段代码中，y和z是两个独立的迭代器，迭代器内部持有一个状态，该状态用于记录当前迭代所在的位置，以方便下次迭代的时候获取正确的元素。迭代器有一种具体的迭代器类型，比如list_iterator，set_iterator，可迭代对象实现了__iter__方法，这种方法会返回一个迭代对象，现在运行以下代码：

x = [1, 2, 3]
for elem in x:
    ...

这段代码的执行过程如下所示：

反编译该段代码，你可以看到解释器显示地调用GET_ITER指令，相当于调用iter(x)，FOR_ITER指令就是调用next()方法，不断地获取迭代器中的下一个元素，但是你没法直接从指令中看出来，因为他被解释器优化过了，下面是反编译的过程：

>>> import dis
>>> x = [1, 2, 3]
>>> dis.dis('for _ in x: pass')
  1           0 SETUP_LOOP              14 (to 17)
              3 LOAD_NAME                0 (x)
              6 GET_ITER
        >>    7 FOR_ITER                 6 (to 16)
             10 STORE_NAME               1 (_)
             13 JUMP_ABSOLUTE            7
        >>   16 POP_BLOCK
        >>   17 LOAD_CONST               0 (None)
             20 RETURN_VALUE

注：dis模块主要是用来分析字节码的一个内置模块，经常会用到的方法是dis.dis，它支持对Python代码进行反汇编，生成字节码指令。

判断可迭代对象

判断一个对象是否是迭代器，可以使用isinstance函数来判断，如下所示：

>>> from collections import Iterable
>>> a = [1,2,34]
>>> isinstance(a,Iterable)
True
>>>

迭代器(iterator)

迭代器协议

迭代器协议是指：对象需要提供next方法，它要么回返迭代中的下一项，要么引起一个StopIteration异常，以终止迭代。协议是一种约定，可迭代对象实现迭代器协议，Python的内置工具，例如for循环，sum，min，max等函数都可以使用迭代器协议访问对象。

在Python中可以使用for循环来遍历数组，PYhton的list底层就是一个数组，因此也可以使用for循环来遍历list，如下所示：

>>> for n in [3, 2, 4, 3]:
...     print(n)
...
3
2
4
3

Python的for循环也可以用于遍历文件（文件位于C:\Users\20161111目录下，内容是1到4这四个数字）如下所示：

>>> import os
>>> os.getcwd()
'C:\\Users\\20161111'
>>> with open('practice.py') as text:
...     for line in text:
...         print(line)
...
1
2
3
4

在Python中，文件也能使用for循环，这是因为在Python中，文件对象实现了迭代器协议，for循环使用迭代器协议访问即对象时，并不需要对象是否是一个文件。

迭代器定义

那么什么迭代器呢？它是一个带状态的对象，他能在你调用next()方法的时候返回容器中的下一个值，任何实现了__iter__和__next__()方法的对象都是迭代器，__iter__返回迭代器自身，__next__返回容器中的下一个值，如果容器中没有更多元素了，则抛出Stop Iteration异常。

所以，迭代器就是实现了工厂模式（什么是工厂模式？有空了补充笔记）的对象，它在你每次你询问要下一个值的时候给你返回。有很多关于迭代器的例子，比如itertools函数返回的都是迭代器对象。

生成无限序列

>>> from itertools import count
>>> counter = count(start=13)
>>> next(counter)
13
>>> next(counter)
14

代码解释：itertools这个模块用于构建迭代器，count这个函数用于生成连续的整数，count(start=13)表示生成从13开始的整数无限序列，即13,14,15….。

从一个有限序列中生成无限序列

代码如下所示：

>>> from itertools import cycle
>>> colors = cycle(['red','white','blue'])
>>> next(colors)
'red'
>>> next(colors)
'white'
>>> next(colors)
'blue'
>>> next(colors)
'red'
>>> next(colors)
'white'

这段代码使用了cycle函数，它的功能在于生成一个循环的无限序列。

从无限的序列中生成有限序列

代码如下所示：

>>> from itertools import islice
>>> counter = count(start=13)
>>> limited = islice(counter,2,5)
>>> for x in limited:
...     print(x)
...
15
16
17

代码解释，先用count生成了一个无限的整数序列，即13，14，15，16，17，18…..，接着使用islice从这个无限序列中提取第2到第4个元素（第2个元素是15，因为Python计数时，是从0开始的），15,16,17。

自定义迭代器

为了更直观地感受迭代器内部的执行过程，我们自定义一个迭代器，以斐波那契数列为例：

from itertools import islice

class Fib:
    def __init__(self):
        self.prev = 0
        self.curr = 1


    def __iter__(self):
        return self

    def __next__(self):
        value = self.curr
        self.curr += self.prev
        self.prev = value
        return value

f = Fib()
print(list(islice(f,0,10)))

运行结果如下所示：

C:\Users\20161111>python practice.py
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Fib是一个可迭代对象，因为它有__iter__方法，又是一个迭代器，因为它实现了__next__方法，实例变量prev和curr用于维持迭代器的内部状态，每次调用next()方法时，做两件事情，第一：为下一次调用next()方法修改状态；第二：为当前这次调用生成返回结果。

迭代器就像一个懒加载的工厂，等到有人需要的时候才给它生成值返回，没调用的时候就处于休眠状态等待下一次调用。

为什么要使用迭代器？

先看一段代码，如下所示：

list = [3,5,1,4,5]
it = iter(list)
for x in it:
    print(x,end=" ")

print("\n---------")
for y in list:
    print(y,end=" ")

运行结果如下所示：

C:\Users\20161111>python practice.py
3 5 1 4 5
---------
3 5 1 4 5

从运行结果来看，貌似迭代器与普通的for循环没什么区别。但Python中为什么设计出迭代器种对象？下面列出了一些迭代器的使用场景：

场景1：访问集合中的一个元素。

例如我要访问集合中的一个元素，怎么处理？

思路：集合是没有顺序的，因此也没有索引，要访问元素，有两种方法：第一，将集合转换为列表；第二，使用迭代器，先看第一种方法：

>>> set1 = {5,3,8,4,11}
>>> print(set1)
{3, 4, 5, 8, 11}
>>> list1 = list(set1)
>>> print(list1)
[3, 4, 5, 8, 11]
>>> list1[2]
5

再看第2种方法：

>>> set1=iter(set1)
>>> next(set1)
3
>>> next(set1)
4
>>> next(set1)
5
>>> next(set1)
8
>>> next(set1)
11

场景2:

如果我有一个文件，例如6G的测序文件，要遍历里面的所有元素，此时如果使用列表，元组等序列明显不现实。此时就需要使用迭代器子，它的一大优点就是不需要事先准备好整个迭代过程中所有的元素 ，迭代器仅仅在迭代到某个元素时才计算该元素，而在这之前或之后，元素可以不存在或者被销毁。 这个特点使得它特别适合用于遍历一些巨大的或是无限的集合。因此，它的使用过程有点像内存，我们把正在运行的程序放进内存，运行完就退出内存，每次只放正在运行的程序进入，而不是一次把全部内容都扔进去。

生成器（generator）

在Python中，使用了yield的函数被称为生成器（generator），跟普通函数不同的是，生成器是一个返回迭代器的函数，只能用于迭代操作，更简单点理解生成器就是一个特殊的迭代器，调用一个生成器函数，返回的是一个迭代器对象。它不需要再像上面的类一样写__iter__()和__next__()方法了，只需要一个yiled关键字，每次遇到yield时函数会暂停并保存当前所有的运行信息，返回yield的值,并在下一次执行next()方法时从当前位置继续运行（这也是生成器的主要使用场景）。

从上述描述中可以知道，生成器可以支持延迟操作，延迟操作是指，只在需要的时候产生结果，而不是立即产生结果，这是生成器的主要好处。Python有两种不同的方式提供生成器：第一，生成器函数：常规函数定义，但是，使用yield语句而不是return语句返回结果。yield语句一次返回一个结果，在每个结果中间，挂起函数的状态，以便下次重它离开的地方继续执行。第二，生成器表达式：类似于列表推导，但是，生成器返回按需产生结果的一个对象，而不是一次构建一个结果列表

用生成器来实现斐波那契数列的例子是：

from itertools import islice

def fib():
    prev, curr = 0, 1
    while True:
        yield curr
        prev, curr = curr, curr + prev

f = fib()
print(list(islice(f, 0, 10)))

代码运行如下所示：

C:\Users\20161111>python practice.py
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

fib就是一个普通的python函数，它特殊的地方在于函数体中没有return关键字，函数的返回值是一个生成器对象。当执行f=fib()返回的是一个生成器对象，此时函数体中的代码并不会执行，只有显示或隐示地调用next的时候才会真正执行里面的代码。

生成器表达式

生成器表达式是列表推倒式的生成器版本，看起来像列表推导式，但是它返回的是一个生成器对象而不是列表对象。，如下所示：

def something():
    result = []
    for ... in ...:
        result.append(x)
    return result

生成器的优点

第一，代码量更少。

生成器在Python中是一个非常强大的编程结构，可以用更少地中间变量写流式代码，此外，相比其它容器对象它更能节省内存和CPU，当然它可以用更少的代码来实现相似的功能。但凡看到类似以下的代码，就能够用生成器替代：

def something():
    result = []
    for ... in ...:
        result.append(x)
    return result

将上述代码用生成器函数来替换：

def iter_something():
    for ... in ...:
        yield x

再看一个案例：

使用生成器返回自然数的平方

常规写法如下所示：

C:\Users\20161111>type practice.py
def get_square(n):
    res = []
    for i in range(n):
        res.append(i*i)
    return res

for item in get_square(5):
    print(item)
    
    
C:\Users\20161111>python practice.py
0
1
4
9
16

生成器函数写法如下所示：

C:\Users\20161111>type practice.py
def get_square(n):
    for i in range(n):
        yield i*i

for item in get_square(5):
    print(item)
    
C:\Users\20161111>python practice.py
0
1
4
9
16

生成器表达式的写法如下所示：

>>> squares = (x*x for x in range(5))
>>> squares
<generator object <genexpr> at 0x000001F167983DB0>
>>> next(squares)
0
>>> next(squares)
1
>>> next(squares)
4
>>> next(squares)
9
>>> next(squares)
16
>>> next(squares)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

生成器总结

现在总结一下生成器函数的格式，如下所示：

def 函数名:
    statements
        yield

1. 生成器函数和常规函数几乎是一样的。它们都是使用def语句进行定义，差别在于，生成器使用yield语句返回一个值，而常规函数使用return语句返回一个值。
2. 自动实现迭代器协议：对于生成器，Python会自动实现迭代器协议，以便应用到迭代背景中（如for循环，sum函数）。由于生成器自动实现了迭代器协议，所以，我们可以调用它的next方法，并且，在没有值可以返回的时候，生成器自动产生StopIteration异常。
3. 状态挂起：生成器使用yield语句返回一个值。yield语句挂起该生成器函数的状态，保留足够的信息，以便之后从它离开的地方继续执行。

结论

1. 容器是一系列元素的集合，str、list、set、dict、file、sockets对象都可以看作是容器，容器都可以被迭代（用在for，while等语句中），因此他们被称为可迭代对象。
2. 可迭代对象实现了__iter__方法，该方法返回一个迭代器对象。
3. 迭代器持有一个内部状态的字段，用于记录下次迭代返回值，它实现了__next__和__iter__方法，迭代器不会一次性把所有元素加载到内存，而是需要的时候才生成返回结果。
4. 生成器是一种特殊的迭代器，它的返回值不是通过return而是用yield。

参考资料

1. Python 迭代器和生成器
2. 完全理解Python迭代器对象、迭代器、生成器
3. Iterables vs. Iterators vs. Generators
4. Bloom Filter概念和原理
5. Python进阶系列连载（4）——迭代器
6. 如何更好地理解Python迭代器与生成器.知乎.赖明星的回答