python生成器简析

python基础

浏览数:396

2019-8-29

生成器generator

生成器具体是什么?简单来说,生成器就是一种迭代器,它实现的功能与迭代器是一样的,即通过next()build-in调用算出下一个迭代值,同时可以被for循环迭代访问。

现将如何写一个生成器,有两种方式。一是直接通过类似于列表生成式的方式:

g = (i**2 for i in range(5))#注意与列表生成式的区别,这里是(),而不是[]
for i in g:
    print(i)
0
1
4
9
16

另一种是通过定义一种特殊的函数,在这里我们称之为生成函数。这个函数与普通函数的区别在于,它并不是一次执行到底,而是每次遇到yield语句就返回一个值。

事实上,生成函数并不算是一种普遍意义上的“函数”。python会识别出这个函数,调用它的时候将返回一个生成器,这个生成器其实就是一种迭代器。

但是在程序员的角度,与迭代器不同的是:迭代器每一次next()都是调用一次自己的__next__()方法,而生成器则是开始执行生成函数,遇到yield语句时暂停函数并返回一个值,等下一个next()调用时,继续执行刚才未执行完的生成函数。

例如下面定义的一个迭代器和一个生成器,他们就是等价的

class it(object):
    def __init__(self):
        self.a = 1
    def __iter__(self):
        return self
    def __next__(self):
        if self.a > 10:
            raise StopIteration()
        self.a+=2
        return self.a-2

i = it()
for x in i:
    print(x)
1
3
5
7
9
def gen():#也可以接受一些传入值
    a = 1
    while(a<=10):
        yield a
        a+=2

g = gen()
for x in g:
    print(x)
1
3
5
7
9
from collections import Iterator
isinstance(g,Iterator)
True

从上面的三段代码可以看到,generator就是一个特殊的Iterator,他们的本质是一样的。那么为什么要设计一个生成器出来呢?

第一方面是简单,生成器给了你一个快速方便的方法创建迭代器。如果仅是临时需要,写一个函数就好,而不用大张旗鼓的专门设计一个迭代器类。

第二个方面是生成器控制更灵活,迭代器规定了每一次迭代都是调用__next__,而__next__本身是固定的。生成器就不一样,他可以在函数中灵活的进行控制。

如果这么说不明白,我们可以玩点儿花活,比如考虑用生成器写一个递归的二叉树中序遍历看看:

class BinaryTree(object):#定义二叉树
    def __init__(self,value,left=None,right=None):
        self.value = value
        self.left = left
        self.right = right

tree = BinaryTree(
    left=BinaryTree(
        left=BinaryTree(1),
        value=2,
        right=BinaryTree(
            left=BinaryTree(3),
            value=4,
            right=BinaryTree(5)
        ),
    ),
    value=6,
    right=BinaryTree(
        value=7,
        right=BinaryTree(8)
    )
)#建立二叉树


def InorderTraversal(tree):#重头戏,generator进行递归中序遍历
    if tree.left != None:
        for i in InorderTraversal(tree.left):
            yield i
    yield tree.value
    if tree.right != None:
        for i in InorderTraversal(tree.right):
            yield i


#开始遍历这个二叉树~当当当当~
for i in InorderTraversal(tree):
    print(i)
1
2
3
4
5
6
7
8

这个例子完美的解释了生成器对于迭代器的优越性~那就是生成器是在一个函数框架内完成的,也就是说他在整个迭代过程结束之前,会自动进行值的储存。这样就可以完美的配合递归来做事情啦,因为函数尚未运行完毕,再次调用本体,压栈出栈都是自动进行的。

而相反,迭代器只能重复执行__next__(),执行一次就释放一次__next__()里面的所有临时变量,所以你无法直接对它进行递归。你只能完全自己手动设计整个递归过程,包括临时变量的压栈出栈。或者在本例中,你也可以要求一次__next__()就把所有的值遍历算出来。不过那样也就失去了“迭代”的意义了,不是吗?

那要用迭代器实现中序遍历怎么办?那就只能,写一写手动递归(其实就是非递归啦)了:

class NotRecursive_Traversal(object):
    def __init__(self,tree = None):
        self.stack = []
        self.tree = tree
        while self.tree != None:
            self.stack.append(self.tree)
            self.tree = self.tree.left
    def __iter__(self):
        return self
    def __next__(self):
        if len(self.stack)>0:
            self.tree = self.stack.pop()
            temp = self.tree
            self.tree = self.tree.right
            while(self.tree!=None):
                self.stack.append(self.tree)
                self.tree = self.tree.left
            return temp.value
        else:
            raise StopIteration

it = NotRecursive_Traversal(tree)
for i in it:
    print(i)
1
2
3
4
5
6
7
8

当然,生成器比迭代器的代码模式更灵活,所以迭代器能写的非递归中序遍历,生成器当然也可以,而且会更简单。比如我们可以这样写:

def ge(tree):
    stack = []
    while len(stack)>0 or tree!=None:
        while tree!= None:
            stack.append(tree)
            tree = tree.left
        tree = stack.pop()
        yield tree.value
        tree = tree.right

for i in ge(tree):
    print(i)
1
2
3
4
5
6
7
8

作者:__Aster__