深入了解Python暂缓列表生成器

Python  /  houtizong 发布于 2年前   189

有的时候你的程序精力过剩，把你不需要或者不希望它做的事情都给做了——你想要它懒一点才好。这就是生成器的用武之地。使用python的生成器（generator）能够让你精确地决定要它做多少以及什么时候去做。

上周我们向你介绍了python列表推导（list comprehension），它让你能以更加自然的方式来表示列表的内容。本文将介绍它们的同类：python生成器，它可以一段一段地构成一个序列，按照你的要求完成工作量。

这被叫做暂缓求值（lazy evaluation），用来推迟某个特定值的计算，直到程序某个点需要才开始。暂缓求值在很多类型的编程中非常有用，因为它不用计算从来都不使用的值，因而可以带来性能上的提升。有的语言，比如Haskell和Miranda，在默认情况下都使用暂缓求值；而其他的语言，像Scheme、Ocaml和python，都可以通过专门的句法来使用暂缓求值。在python里，实现暂缓求值的方式是使用生成器。

利用生成器你可以编写出这样一个函数，它能够返回结果然后暂停，当你下一次调用这个函数的时候它会从暂停的地方恢复。你不需要任何专门的句法来编写生成器，要做的只是表示一下什么时候使用yield语句返回一个中间值。说明这一点的最简单方法是举一个例子：

>>> def generator1():...yield "first"...yield "second"...yield "third"... >>> gen = generator1()>>> gen >>> gen.next()'first'>>> gen.next()'second'>>> gen.next()'third'>>> gen.next()Traceback (most recent call last):File "", line 1, in ?StopIteration>>>
在这个例子中，我们首先定义一个叫做generator1的生成器，它会生成三个值：“first”、“second”和“third”三个字符串。当我们创建一个新的生成器对象（gen）时，它就开始执行函数。每当你调用生成器next方法时，它会继续执行这个函数，直到生成下一个值。当生成器达到块结尾的时候，或者碰到返回语句时，它会产生一个StopIteration异常。

生成器本质上就是迭代器，这也就是说它们可以用在很多表达式里，而不需要用序列（列表等）。例如，你可以不使用上面的代码，而改用下面的：

>>> gen2 = generator1()>>> for i in gen2:...print i... firstsecondthird
类似的，你可以一次就把生成器转换成为列表：

>>> gen3 = generator1()>>> list(gen3)['first', 'second', 'third']

下面就让我们举一个真正派得上用场的例子。下面是一个相当标准的用于产生组合的函数，换句话说，一个序列可以以多种独特的方式被切割成小的序列：

def combination(seq, length):if not length: return [[]]else:l = []for i in xrange(len(seq)):for result in combination(seq[i+1:], length-1):l += [[seq[i]]+result]return l
它的用法是：

>>> combination("ABCDE", 3)
[['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'B', 'E'], ['A', 'C', 'D'], ['A', 'C', 'E'], ['A', 'D', 'E'], ['B', 'C', 'D'], ['B', 'C', 'E'], ['B', 'D', 'E'], ['C', 'D', 'E']]
>>> combination("ABCDE", 2)
[['A', 'B'], ['A', 'C'], ['A', 'D'], ['A', 'E'], ['B', 'C'], ['B', 'D'], ['B', 'E'], ['C', 'D'], ['C', 'E'], ['D', 'E']]
>>> combination("ABCDE", 5)
[['A', 'B', 'C', 'D', 'E']]

现在让我们改用生成器来做同样的事情。你想要在某些点往最终结果列表里加入一个值并用yield语句替换掉它，因此这里的技巧是简单地替换掉每一个这样的点。

def xcombination(seq,length):
if not length: yield []
else:
for i in xrange(len(seq)):
for result in xcombination(seq[i+1:], length-1):
yield [seq[i]]+result

现在我们用另一种方式获得了同样结果，唯一的不同是它只会按照你的需要来工作：

>>> comb = xcombination("ABCDE", 3)
>>> comb.next()
['A', 'B', 'C']
>>> comb.next()
['A', 'B', 'D']
>>> list(comb)
[['A', 'B', 'E'], ['A', 'C', 'D'], ['A', 'C', 'E'], ['A', 'D', 'E'], ['B', 'C', 'D'], ['B', 'C', 'E'], ['B', 'D', 'E'], ['C', 'D', 'E']]
>>> comb2 = xcombination("ABCDE",2)
>>> for i in xrange(3):
... print comb2.next()
... ['A', 'B']
['A', 'C']
['A', 'D']

在最后一条命令里，尽管有10种不同的字母组合，但是只生成了3个，与标准的函数相比，这就节省了70％的计算时间。

生成器真正的有用之处在于，在大多数情况下它们可以用作替代列表推导的放下（Drop）。你需要做的是用圆括号替换掉列表推导前后的方括号。我们就举《列表推导》一文中的最后一个例子。我们不需要：

>>> guests = ['Chris', 'Brendan', 'Jimmy', 'Mel', 'Mike', 'Jess']
>>> [(seat1, seat2) for seat1 in guests for seat2 in guests if seat1 != seat2]
...

你可以改用：

>>> guests = ['Chris', 'Brendan', 'Jimmy', 'Mel', 'Mike', 'Jess']
>>> ((seat1, seat2) for seat1 in guests for seat2 in guests if seat1 != seat2)


然后你可以像使用其他任何生成器一样使用它：

>>> seating = ((seat1, seat2) for seat1 in guests for seat2 in guests if seat1 != seat2)
>>> for i in xrange(10):
... print seating.next()
...
('Chris', 'Brendan')
('Chris', 'Jimmy')
('Chris', 'Mel')
('Chris', 'Mike')
('Chris', 'Jess')
('Brendan', 'Chris')
('Brendan', 'Jimmy')
('Brendan', 'Mel')
('Brendan', 'Mike')
('Brendan', 'Jess')

到现在我们已经在使用生成器了，在创建列表上它比其他方法节约计算时间。这非常好，但是它大展拳脚的地方是在不可能计算整个列表的时候。我们就以Fibonacci序列为例，在这个序列里，每个数字都是前面两个数字的和。假设我们想要一个能够生成到指定数字的序列：

>>> def fib(n):...a, b = 0, 1...l = [a]...while b < n:...l += [b]...a, b = b, a+b...return l... >>> fib(20)[0, 1, 1, 2, 3, 5, 8, 13]

现在它运行良好，除非我们想要它停止，否则它会一直计算到我们指定的数字。但是，如果我们想要更改停止的条件，我们就必须重写这个函数。但是我们可以用生成器来实现它（从python的《python.org/dev/peps/pep-0255/">PEP生成器》一文借用的实现）：

>>> def xfib():...a,b = 0,1...while True:...yield b...a, b = b, a+b... >>> fibseries = xfib()>>> b = fibseries.next()>>> while b < 20:...print b...b = fibseries.next()... 11235813
或者，如果我们想要在第一个回文（超过一位）处停止，我们只需要改变循环条件就行了：

>>> fibseries = xfib()
>>> b = fibseries.next()
>>> while b < 10 or not list(str(b)) == list(reversed(str(b))):
... print b
... b = fibseries.next()
...
1
1
2
3
5
8
13
21
34

这就行了（这个数列的下一个值是55）。但是我们通过使用生成器可以让列表生成实现与什么时候停止生成它的逻辑分离，同时只用计算我们需要的那么多值。

你应该在什么时候使用生成器而不用列表推导呢？首先，如果你准备使用完整的列表，你就最好使用列表推导——它们的速度会更快一些，因为不会有调用生成器函数所增加的系统开销。如果你准备使用列表的第一部分，那就使用生成器吧，因为这会节约你的CPU时间