Python函数式编程07 生成器

生成器的概念

为什么需要生成器

在 Python 中,如果一个函数不使用 return 关键字返回数据,而是使用 yield 关键字得到数据,那么该函数就称为生成器(generator)函数。也就是说,生成器函数的特征为:

def function(...):
    ... # statements
    yield expression

既然可以使用返回值,为什么需要生成器这种奇怪的语法?下面通过一个示例来说明函数存在的不足。

重新回到之前编写的生成斐波那契数列的函数,该函数的代码如下:

def fibonacci(n):
    result = []
    a, b = 0, 1
    while a < n:
        result.append(a)
        a, b = b, a + b
    return result

既然编写了这个函数,那么它肯定就会有用得到的地方。例如,假设要从斐波那契数列中找到是否存在一个完全平方数,那么可以再编写一个函数 issquare() ,然后使用以下代码判断:

for i in fibonacci(1000):
    if issqare(i):
        # do something
        break

这种形式有一个明显的不足,注意在程序中,调用了两次循环:一次用于挨个生成斐波那契数列的元素,另一次用于从得到的斐波那契数列中挨个判断是否满足条件,这就会造成有一半的时间都会浪费在重复地将一个无用的元素塞入列表,然后再取出上。

除此之外,这个函数还返回了一个列表,这是另一个问题:如果要判断的数据量很多,那么这个列表也势必很大,但是真正要用到的值只有一个,那么这个列表又浪费了太多无用的空间。而且必须得等到列表生成完毕以后,再去列表中取值;但问题是在生成列表时,还不知道结果是多少,那么也不知道生成的列表到底要多大,这样要么得到的列表长度不足,其中不包含结果;要么得到的列表结果过大,其中包含了许多压根不会用上的元素。

这样的缺点不仅降低了效率,还可能招致严重的问题。

如果是在命令式编程,那么只需要在同一个循环内,在生成元素的时候顺便判断一下结果是否满足就行了。当然也可以把它封装成一个函数,但是如果判断斐波那契数列中是否存在平方数这种宏观的问题都需要用一个函数处理的话,那么判断斐波那契数列中素数的个数是否大于 10 个是否也要编写一个函数?这种问题塞到一个函数显然不够合适,因为它处理的问题太过细致了,这种函数显然不会用很多次,如果程序中都是这样不太能复用的函数,那么肯定不够合适。

生成器就是为了解决以上问题的。接下来先介绍生成器的特征,这样可以更好地明白使用生成器解决上述问题的优点所在。

什么是生成器

首先看看 yield 关键字会得到什么样的结果,以下编写了一个最基本的生成器函数:

def func():
    yield 3

然后检查一下函数对象:

>>> func <function func at 0x0000013CD9737C10>

结果表明函数依旧是函数,这点没有发生改变。那么再试着调用一下函数:

>>> func() <generator object func at 0x0000013CD934F890>

调用函数的结果显示,该函数返回了一个生成器对象。

生成器(generator)是一种特殊的数据类型,生成器只在需要的时候,才会产生具体的值,这就避免了时间上的浪费;生成器在产生一个值时,会将上一次产生的值抛弃,这就避免了空间上的浪费。生成器是 Python 的一大特性,使用生成器可以让代码变得更加简洁、优雅。

以上说法可能只能让人似懂非懂,下面结合一个具体的示例说明。以下将上面的斐波那契函数改成生成器函数的形式,如下所示:

def fibonacci():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

一个生成器最基本、最实用的用法就是使用 for 循环对生成器迭代,每一次迭代过程中,如果遇到 yield 语句,那么后面的表达式就会被作为本次迭代的结果返回给中间变量如 i 后续利用。

这也揭示出了生成器函数与普通函数的区别:

  • 普通函数在执行到 return 语句后就终止,后面的所有语句都会被忽略;生成器函数执行到 yield 语句后,只是暂时将结果返回,下一次遍历时,又会从暂停的位置继续执行下去
  • 因此,一个生成器函数在执行时,可以遇到多个yield 语句;普通函数虽然可以串列多个 return 语句,但是遇到第一个语句后就会终止
  • 也正是因为这个特点,生成器会在迭代过程中一直保存其中的局部变量,直到迭代结束

以下示例展示了生成器的用法:

for i in fibonacci():
    print(i, end=' ')
    if i > 30:
        break

以上代码的执行结果为:

$ python -u demo.py 0 1 1 2 3 5 8 13 21 34

这里简单分析一下程序的执行过程,首先生成器函数执行到 yield 语句时,变量 a 的值是 0 ,因此 0 被作为生成结果传递给迭代的中间变量 i ;第二次进入迭代时函数从 yield 语句后继续运行,变量的值发生改变,a 变成了 1 ,再次作为生成结果传递给迭代的中间变量;以此类推,第三次执行到 yield 时返回的结果是 1 ,第四次是 2 ……。

使用集成开发环境的读者可以使用 debug 功能,对程序下断点,进一步观察每一步代码是如何执行、变量的值是如何变化的。

下图表示了这一过程:

最后,在外部使用 break 语句强行终止了这一过程。如果不手动终止的话,迭代会一直发生下去,生成器可以一直生成新的值出来,因此这类的生成器也称为无限生成器。这又是生成器相对普通函数的优点:普通函数不可能返回一个具有无穷长度的列表,但是生成器可以一直源源不断地计算新的结果。

可以从这个角度理解:函数返回的是结果,而生成器返回的是过程

实际上,在第四节中介绍的内置函数 map()enumerate() 等,得到的结果就是一个类似生成器的对象。

生成器与生成器函数

前面介绍了生成器的概念,并通过示例展示了生成器的用法。但是注意,生成器在使用时有一些注意事项。

以上提到了一个基本的事实:生成器函数在调用时,才会返回一个生成器。但是注意,在介绍生成器时,还提到了:生成器在产生一个值时,会将上一次产生的值抛弃 。这种性质虽然节约了空间的开销,但也使得一个生成器只能被迭代一次,一旦调用完成后该值便不再保存在内存当中,因此生成器中生成的值只能访问一次。

为了理解这句话,给定以下生成器:

def odd():
    i = 0
    while True:
        yield i * 2 + 1
        i += 1

第一次对生成器迭代的结果很正常:

>>> for i in g1: ... print(i, end=' ') ... if i > 15: ... break ... 0 2 4 6 8 10 12 14 16

但是第二次生成的结果就有些变化了:

>>> for i in g1: ... print(i, end=' ') ... if i > 30: ... break ... 18 20 22 24 26 28 30 32

这一次,生成器是顺着上一次的结果继续执行了下去,这说明前面的值都被抛弃了,再也访问不到了。或者也可以从生成器的执行过程分析:生成器还没执行完成,只是这一过程暂停了。

因此,以下两种使用生成器的方式:

# 1
g2 = odd()
for i in g2:
    ...
for i in g2:
    ...
# 2
for i in odd():
    ...
for i in odd():
    ...

得到的是完全不同的结果,因为第一次只创建了一个生成器,第二次创建了两个生成器。

这种特性是生成器的优点,但它有时也会带来问题。因为生成器的迭代可能是显式的,也有可能是隐式的,有些时候生成器在生成值时难以被察觉。考虑以下简单的函数:

def average(l):
    return sum(l) / len(tuple(l))

该函数用于求一个序列或可迭代对象的平均值,为了弥补 len() 函数不可作用于可迭代对象的缺点,它在内部将其转换为元组。但是真正使用的结果可能出乎意料:

>>> average(map(lambda x: x ** 2, range(10))) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 2, in average ZeroDivisionError: division by zero

这段代码直接产生了错误。不过定义的函数不长,稍微分析就能发现问题所在:序列的长度变成 0 了,因此发生了错误。

这就是对同一个生成器两次迭代带来的后果,在第一次使用 sum() 函数时,它就会隐式迭代生成器,迭代完成后,生成器就变空了,因此第二次得到的是一个空序列,自然就会出错。

生成器的高级用法

生成器与递归调用

普通的函数允许递归,通过在函数中调用自身是实现循环的一种方式。而生成器函数有时为了实现类似迭代生成的功能,也会需要类似递归的用法。

考虑以下生成器,该生成器用于将一个任意嵌套的列表碾平成一维列表:

ls = ['1', [2, 'a', [['hello'], 'w'], 6], [[['o']], 7, 9], 'd']

def flatten(nest):
    for i in nest:
        if not isinstance(i, list):
            yield i
        else:
            ...

首先看看生成器该如何处理这种问题:首先生成器遍历列表的每一个元素,如果已经是一个基本的元素,那就将其生成出来。如果是一个嵌套的列表的话,那么应该将该列表内的元素生成出来,再次嵌套的列表继续作类似处理。

上下级之间以相同的逻辑处理,这就很符合递归的一些特性。但是注意,如果按照普通函数递归的思路,可能有些人的第一印象是写作

            yield flatten(nest)

这是完全错误的写法,因为仔细分析该语句的目的是生成出了一个生成器对象作为本次迭代的结果。回想一下,函数递归的特点是函数在函数体调用时,又在内部调用自身,是 return func() 这种嵌套调用的形式而不是 return func 直接把函数对象返回。

类比这种特点,那么生成器在递归时,也应该是生成器函数在生成值时,包含了一个自身的生成器,并将自身生成的结果作为生成的结果。

这种说法可能有点绕,下面借用代码说明。以下是函数递归的特性,函数在调用时,又在内部调用自身:

func(...)  # function call
=> func(...)  # nested function call

那么,生成器函数的递归思路也是如此。生成器函数在迭代时,又在内部迭代自身:

for i in gener(...):
    ...    # generator iterate
=> for i in gener():
=>       ...  # nested generator iterate

这样,上述生成器递归部分的代码为:

            for k in flatten(i):
                yield k

生成器在迭代自身时,自身的迭代过程又迭代了自身,这就是递归的过程。

以上代码的检验结果为:

>>> list(flatten(ls)) ['1', 2, 'a', 'hello', 'w', 6, 'o', 7, 9, 'd']

可以看到它很好地完成了工作。并且这种情况下生成器比函数的递归调用方便,因为这种混乱嵌套的列表,很难将其拆解成上下级的递推关系。

实际上,Python 中还新增了组合关键字 yield from ,用于生成器的递归调用。也就是说,以上递归部分可以简单地改成:

            yield from flatten(i)

这样的表述非常清晰,每次遇到一个 yield from ,就转从另一个生成器里面生成结果,这样就实现了生成器的递归。

以下再次给出了一个生成器函数示例,该生成器函数从一个给定的文件夹中找出文件,如果遇到嵌套的文件夹,它便递归地从嵌套的文件夹中找出包含的文件:

import os

def get_files(dir):
    for f in os.listdir(dir):
        path = os.path.join(dir, f)
        if os.path.isfile(path):
            yield path
        else:
            yield from get_files(path)

这样就可以实现文件的搜索功能。

生成器表达式

除了使用函数和 yield 关键字创建生成器外,简短的生成器还有另一种创建方式:

g = (i ** 2 for i in range(1000) if isprime(i))

熟悉列表解析语法的读者应该可以很容易理解它的语法。列表解析的介绍可以参见 这篇文章

>>> g <generator object <genexpr> at 0x0000013CD934F890> >>> type(g) <class 'generator'>

这种最外层使用圆括号的语法不是什么元组解析,而是生成器表达式,它本质就是一个生成器。这种短小的生成器表达式一般用于简单的应用场景中。

京ICP备2021034974号
contact me by hello@frozencandles.fun