美文网首页
yield大法好

yield大法好

作者: 小生境 | 来源:发表于2016-02-20 21:36 被阅读385次

    虽然不知道是谁最早发明yield来表达协程的,不过最近终于解锁这一技能了,让我感受到了上帝般的快感。
    比方说我们要后序遍历二叉树,好啦我知道ACMer闭着眼睛都能默写出来非递归版本,让我们看看递归版本先:

    class Node(object):
        def __init__(self, val, left, right):
            self.val = val
            self.left = left
            self.right = right
    
    def visit_post(node):
        if node.left:
            yield from visit_post(node.left)
        if node.right:
            yield from visit_post(node.right)
        yield node.val
    
    if __name__ == '__main__':
        node = Node(-1, None, None)
        for val in range(100):
            node = Node(val, None, node)
        print(list(visit_post(node)))
    

    就是这么简单,yield from这么棒为什么你还在用Python2.x?
    但是我们知道写成递归动不动就爆栈了,非递归才是正义。不过不要怕,理解yield协程之后我们再也不必手动维护什么栈了,装逼变得异常简单。

    def visit_post(node):
        if node.left:
            yield node.left
        if node.right:
            yield node.right
        yield node.val
    
    def visit(node, visit_method):
        stack = [visit_method(node)]
        while stack:
            last = stack[-1]
            try:
                yielded = next(last)
            except StopIteration:
                stack.pop()
            else:
                if isinstance(yielded, Node):
                    stack.append(visit_method(yielded))
                elif isinstance(yielded, int):
                    yield yielded
    
    if __name__ == '__main__':
        node = Node(-1, None, None)
        for val in range(100):
            node = Node(val, None, node)
        visit_generator = visit(node, visit_method=visit_post) 
        print(list(visit_generator))
    

    excellent!关键是很好理解对不对,我以前一直认为我不把LeetCode刷7遍是不可能完成递归转非递归的白板编程的,现在根本不是问题嘛。
    话说简书的代码高亮能不能专业点,__builtins__高亮很难?这根本就是态度问题。


    或者我们有递归搜索二叉树最大值什么的:

    def visit_maxvalue(node):
        if node.left and node.right:
            return max(node.val, visit_maxvalue(node.left), visit_maxvalue(node.right))
        elif node.left:
            return max(node.val, visit_maxvalue(node.left))
        elif node.right:
            return max(node.val, visit_maxvalue(node.right))
        else:
            return node.val
    

    非递归版本也是非常平易近人:

    def visit_max_maxvalue(node):
        if node.left and node.right:
            yield max(node.val, (yield node.left), (yield node.right))
        elif node.left:
            yield max(node.val, (yield node.left))
        elif node.right:
            yield max(node.val, (yield node.right))
        else:
            yield node.val
    
    def visit(node, visit_method):
        stack = [visit_method(node)]
        current = None
        while stack:
            last = stack[-1]
            try:
                yielded = last.send(current)
            except StopIteration:
                stack.pop()
            else:
                if isinstance(yielded, Node):
                    stack.append(visit_method(yielded))
                    current = None
                elif isinstance(yielded, int):
                    current = yielded
        return current
    

    逼格饱满有木有!
    BTW,著名的Tornado就是用yield协程来实现异步,大爱!

    相关文章

      网友评论

          本文标题:yield大法好

          本文链接:https://www.haomeiwen.com/subject/orohkttx.html