魔力Python——yield & yield from

起因:在图论中,实现广度搜索两顶点所有路径时,被好用的 yield 和 yield from 惊呆啦~

题外话: 想真正搞明白这两者,先学习两个名词,迭代器生成器

  先说迭代器,对于string、list、dict、tuple等容器对象,用for循环遍历是很方便的,在后台for语句对容器对象调用iter()函数,iter()会返回一个定义了next()方法的迭代器对象,从而在容器中逐个访问容器内元素,直到最后抛出StopIteration异常,for循环结束。

  生成器是创建迭代器的简单而强大的工具,能做到迭代器能做的所有事,自动创建iter()和next()方法,自动抛出StopIteration异常。一个带yield的函数就是一个生成器。

  好,了解了迭代器与生成器,看看yield的用法:

1
2
3
def generator():
for i in range(10):
yield i

  上面的generator()函数就是一个带yield的生成器,执行print(list(generator())),就会输出[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]这样的列表。

  Python3.3版本的PEP 380中添加了yield from语法,允许一个生成器将其部分操作委派给另一个生成器。其产生的动力在于使生成器能够容易分为多个拥有send和throw方法的子生成器。进一步了解可参考Stack Overflow上的经典解释yield from主要有什么用?

  知道了,yield 和 yield from,下面这段代码是我结合这两者,求图中两个顶点之间广度搜索路径:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#def a undirected graph
graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}
#dfs
def dfs_paths(graph,start,goal,path=None):
if path is None:
path = [start]
if start == goal:
yield path
for next in graph[start] - set(path):
yield from dfs_paths_recursion(graph, next, goal, path + [next])
# test
print(list(dfs_paths(graph,'A','F',path=None)))
[['A', 'C', 'F'], ['A', 'B', 'E', 'F']]

  总之,这是一个魔法语句,简洁明了,nice,i love Python!

Talk is cheap. Show me the code.
分享