Question

读完本章之后你将能够回答下列问题

生成器是怎样节约内存的？

使用生成器的最佳时机是什么？

我如何使用itertools来创建复杂的生成器工作流？

延迟估值何时有益，何时无益？

当许多其他语言的使用者开始学习Python时，他们在for循环的记法差异上吓了一跳。这是因为，在其他语言中的写法可能是这样：

# 其他语言 for (i=0; i<N; i++) { do_work(i); }

而在Python中他们遇到了一个叫range或xrange的新函数：

# Python
for i in range(N):
  do_work(i)

这两个函数让我们见识到了使用生成器编程的范例。为了彻底理解生成器，让我们首先试着简单实现range和xrange函数：

def range(start, stop, step=1):
  numbers = []
  while start < stop:
    numbers.append(start)
    start += step

  return numbers

def xrange(start, stop, step=1):
  while start < stop:
    yield start #❶
    start += step

for i in range(1,10000):
  pass

for i in xrange(1,10000):
  pass

❶ 这个函数会yield很多值而不是只返回一个。这就让一个看上去很普通的函数转变成一个生成器，一种可以被重复轮询下一个可用值的函数。

首先要注意的是range的实现必须预先创建一个列表保存范围内的所有数字。所以，如果范围从1到10000，这个函数会对numbers列表进行10000次append（在第3章我们已经讨论过这部分开销），然后返回整个列表。而另一方面，生成器则能够“返回”很多值。每次代码运行到yield，该函数都会发射出一个值，然后当外部代码需求另一个值时，该函数才会继续运行（之前的状态保持不变）并发射新的值。当该函数运行结束时，一个StopIteration异常会被抛出表明该生成器已经没有更多的值了。结果就是，虽然两个函数最终运行了同样的计算次数，使用range版本的循环多消耗了10000倍的内存（如果范围从1到N则是N倍）。

牢记这段代码，我们就能在for循环中使用自己实现的range和xrange。在Python语言中，for循环要求被循环的对象支持迭代。这意味着我们必须能够在循环对象上创建一个迭代器。而在任何对象上创建迭代器，我们都只需要使用Python内建的iter函数。这个函数，对于列表、元组、字典和集合都返回一个对象内部元素或键的迭代器。对于更复杂的对象，iter函数会返回对象的__iter__属性。由于xrange已经返回了一个迭代器，对其调用iter就不会做任何事，只是简单返回原始的对象（因此type(xrange(1, 10)) == type(iter(xrange(1, 10)))）。不过，由于range返回的是一个列表，我们就不得不创建一个新的对象，一个列表的迭代器，来迭代列表中的所有值。一旦一个迭代器被创建，我们只需要对其调用next()函数，来获得新值，直到StopIteration异常被抛出。这给我们提供了一个能够很好解析for循环的视图，如例5-1所示。

例5-1　Python的for循环解析

# python 循环
for i in object:
  do_work(i)

# 等同于
object_iterator = iter(object)
while True:
  try:
    i = object_iterator.next()
    do_work(i)
  except StopIteration:
    break

for循环的代码显示了我们在使用range而不是xrange时需要额外调用iter。在使用xrange时，我们不需要做任何事情（因为它已经是一个迭代器了！）；然而在使用range时，我们需要分配一个新的列表并预先计算其内的值，然后我们还要创建一个迭代器！

更重要的是，预先计算range列表需要为整个数据集分配足够的空间并为每一个元素赋正确的值，即使我们每次仅需要一个值。为列表分配的空间其实并没有什么意义。实际上，循环甚至根本无法运行，因为range尝试去分配的内存可能根本无法被满足（range(100,000,000)会创建一个3.1GB大小的列表！）。通过对结果计时，我们可以很明显地看到这一点：

def test_range():
  """
  >>> %timeit test_range()
  1 loops, best of 3: 446 ms per loop
  """
  for i in range(1, 10000000):
    pass

def test_xrange():
  """
  >>> %timeit test_xrange()
  1 loops, best of 3: 276 ms per loop
  """
  for i in xrange(1, 10000000):
    pass

这个问题现在看上去可能并不算什么——我们只需要将所有的range调用替换成xrange——但是实际的问题可能隐藏在非常深的角落。比如假设我们有一个数字的长列表，我们想要知道其中有多少个数字可以被3整除。你可能会这样写：

divisible_by_three = len([n for n in list_of_numbers if n % 3 == 0])

然而，这种写法的问题跟range一样。因为我们使用了列表表达式，我们预先生成了一个能被3整除的数字的列表，仅仅只是为了对其进行计算并丢弃。如果这个列表很长，这可能会导致无意义地分配大量内存——大到根本无法被满足。

我们的列表表达式使用了如下公式[<value> for <item> in <sequence> if <condition>]。这会创建一个列表，内含所有满足条件的值。相对的，我们也可以使用一个类似的语法(<value> for <item> in <sequence> if <condition>)来创建一个满足条件的值的生成器而不是一个列表。

利用列表表达式和生成器表达式之间的这种细微的差别，我们就能对divisible_by_three的代码进行优化。然而，生成器并没有一个length属性，所以我们必须要干的聪明点：

divisible_by_three = sum((1 for n in list_of_numbers if n % 3 == 0))

这里，我们的生成器在每当遇到一个能被3整除的数字时就会发射一个1，而不是别的数字。对该生成器发射的所有值求和，我们就能得到跟列表表达式一样的结果。这两个版本的代码性能几乎一样，但是生成器表达式需要的内存远小于列表表达式。另外，我们可以将列表版本轻易转化成生成器版本的原因是我们只关心列表中每个元素的当前值——该值要么可以被3整除要么不可以，而跟它在列表中的位置无关，跟其前后的数字也无关。更复杂的函数也可以被转成生成器，但是根据它们的复杂度，这种转换有可能会比较困难。