Skip to content

每周一个设计模式之迭代器和生成器

迭代

可迭代对象

Python中的Iterable代表可迭代对象,这种抽象的概念可以打比方讲,可迭代的就是“一排东西”。比如:

In [1]: iter([1, 2, 3])
Out[1]: <list_iterator at 0x13363ea4860>

In [2]: iter({1, 2, 3})
Out[2]: <set_iterator at 0x13363e9c9d8>

In [3]: iter((1, 2, 3))
Out[3]: <tuple_iterator at 0x13363ec3fd0>

In [4]: iter({1:1, 2:2, 3:3})
Out[4]: <dict_keyiterator at 0x13363e98598>

In [5]: iter('123')
Out[5]: <str_iterator at 0x13363ed5e80>

In [6]: iter(123)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-7-c76acad08c3c> in <module>()
----> 1 iter(123)

TypeError: 'int' object is not iterable

int类型不属于可迭代类型,因此会直接报错。

自建可迭代类

但假如将iter作用于自定义类时,又会发生什么?

In [1]: class Foo(object):
   ...:     pass

In [2]: foo = Foo()

In [3]: iter(foo)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-3-1f52e18d59f1> in <module>()
----> 1 iter(foo)

TypeError: 'Foo' object is not iterable

十分确信的时Python的iter函数不会仅支持内建类的迭代,所以一定会有一些操作让自定义类支持迭代。那接下来修改刚刚的代码。

In [4]: class Foo(object):
   ...:     def __init__(self, val):
   ...:         self.val = val
   ...:     def __str__(self, val):
   ...:         return str(self.val)
   ...:     def __iter__(self):
   ...:         return iter(self.val)

In [5]: foo = Foo(val='1234')

In [6]: iter(foo)
Out[6]: <str_iterator at 0x1c83990e080>

在添加__iter__()方法之后,自定义类就支持了迭代。这意味着iter(iterable)内部实际在调用iterable.__iter__()。但这不仅仅是唯一的方式。

In [7]: class Foo(object):
   ...:     def __init__(self, val):
   ...:         self.val = val
   ...:     def __str__(self, val):
   ...:         return str(self.val)
   ...:     def __getitem__(self, index):
   ...:         return self.val[index]
   ...:

In [8]: foo = Foo(val='1234')

In [9]: iter(foo)
Out[9]: <iterator at 0x1c839952ba8>

所以__getitem__()方法也是可以的。

自动迭代

在Python中提供了for来自动完成迭代:

for x in iterable:
    pass

当然了我们可以对for进行模拟。

In [16]: def iterate(iterable):
    ...:     index = 0
    ...:     while(index < len(iterable)):
    ...:         print(iterable[index])
    ...:         index += 1
    ...:

In [17]: iterate(iterable=[1, 2, 3, 4])
1
2
3
4

但这种方式无法作用在字典上,很显然iterate()并没有实现for的所有功能。

In [18]: iterate(iterable=dict(a=1, b=2, c=3, d=4))
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-18-b4d7fee1e520> in <module>()
----> 1 iterate(iterable=dict(a=1, b=2, c=3, d=4))

<ipython-input-16-c7dd7eb7d7bf> in iterate(iterable)
      2     index = 0
      3     while(index < len(iterable)):
----> 4         print(iterable[index])
      5         index += 1
      6

KeyError: 0

迭代器

next()或者__next__()方法提供迭代器对象在迭代过程中提供返回的值。在结尾时会抛出StopIteration异常。前面提到的iter()函数为一个可迭代对象返回一个迭代器。如果iter()的参数变为迭代器,他会直接返回。

所以,在这里继续可以改写for的一些操作。

In [1]: def iterate(iterable):
   ...:     it = iter(iterable)
   ...:     while True:
   ...:         try:
   ...:             print(next(it))
   ...:         except StopIteration:
   ...:             break
   ...:

In [2]: iterate(iterable=[1, 2, 3, 4])
1
2
3
4

当然也可以自建一个迭代器类,比如这样:

In [1]: import collections

In [2]: class Foo(collections.Iterable):
   ...:     pass

但是请不要心急,如果此时实例化会引起一些尴尬的事情:

In [3]: foo = Foo()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-3-e0e83b409765> in <module>()
----> 1 foo = Foo()

TypeError: Can't instantiate abstract class Foo with abstract methods __iter__

这是因为你需要自已实现__iter__()方法。但如果不借助内建库依然可以实现:

In [4]: class FakeIterator(object):
   ...:     def __init__(self, num):
   ...:         self.max = num
   ...:         self.start = 0
   ...:
   ...:     def __iter__(self):
   ...:         return self
   ...:
   ...:     def __next__(self):
   ...:         if self.start <= self.max:
   ...:             res = self.start
   ...:             self.start += 1
   ...:             return res
   ...:         else:
   ...:             raise StopIteration
   ...:

In [5]: foo = FakeIterator(num=5)

In [6]: next(foo)
Out[6]: 0

In [7]: next(foo)
Out[7]: 1

In [8]: next(foo)
Out[8]: 2

In [9]: next(foo)
Out[9]: 3

In [10]: next(foo)
Out[10]: 4

In [11]: next(foo)
Out[11]: 5

In [12]: next(foo)
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-12-3d38d98df622> in <module>()
----> 1 next(foo)

<ipython-input-4-1801d114f1f1> in __next__(self)
     13             return res
     14         else:
---> 15             raise StopIteration
     16

StopIteration:

生成器

在编程时,可以很容易的生成一个列表。但迫于内存压力,往往列表的容量也是有限的。如果列表元素可以按照某种方式推演出来,那就可以避免创建完整的列表,从而达到了节省空间的目的。Python当然也提供了这种方法,也就是生成器(Generator)。

创建一个生成器

In [1]: a = [i for i in range(10)]

In [2]: a
Out[2]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In [3]: b = (i for i in range(10))

In [4]: b
Out[4]: <generator object <genexpr> at 0x000002673DF3B5C8>

这里的a与b在定义时的区别仅在于[](),但a是一个列表,b却是一个生成器。

当然在函数中也可以使用yield返回一个生成器。

In [1]: def foo(n):
   ...:     yield n**n
   ...:

In [2]: foo
Out[2]: <function __main__.foo(n)>

In [3]: _foo = foo(n=10)

In [4]: _foo
Out[4]: <generator object foo at 0x00000290186DDDB0>

foo()就是一个生成器函数,调用该函数会返回一个生成器对象(_foo),而生成器与迭代器十分相似,可以使用在for循环中。

In [5]: for _ in _foo:
   ...:     print(_)
   ...:
10000000000

生成器的意义

使用生成器可以让代码看起来简洁,并且在性能上能够提升不少。

In [6]: def fib(n):
   ...:     prev, curr = 0, 1
   ...:     while n > 0:
   ...:         n -= 1
   ...:         yield curr
   ...:         prev, curr = curr, curr + prev
   ...:

In [7]: print([i for i in fib(10)])
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]