技术控

    今日:9| 主题:49347
收藏本版 (1)
最新软件应用技术尽在掌握

[其他] The stack of iterators pattern.

[复制链接]
此生赐情 发表于 2016-10-17 20:14:54
139 3

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
The stack of iterators pattern

   Gareth Rees , 2016-09-28
    Depth-first search  is a straightforward algorithm for visiting the nodes of a tree or tree-like data structure.
   
The stack of iterators pattern.-1 (recursion,structure,function,children,problems)

  Here’s how you might implement it in Python:
  [code]def search(node):
    for child in children(node):
        search(child)[/code]  This works well in many cases, but it has a few problems:
  
       
  •   It descends the tree using a function call search(child) , and function calls are quite slow in Python.
       
  •   It descends the tree by recursing, and so it uses as many levels of stack as the depth of the deepest node in the tree. But Python’s call stack is limited in size (see  sys.getrecursionlimit  ) and so deep enough trees will run out of call stack and fail with “RuntimeError: maximum recursion depth exceeded.”
       
  • If you’d like to be able to stop the search part way through and return a result (for example returning a target node as soon as you find it), then this requires a slightly awkward change to the code. You could add logic for exiting the recursion:
    [code]def search(node):
        if target(node):
            return node
        for child in children(node):
            result = search(child)
            if result is not None:
                return result[/code] or you could return the result non-locally using an exception:
    [code]class Found(Exception):
        pass

    def search(node):
        if target(node):
            raise Found(node)
        for child in children(node):
            search(child)[/code] or you could rewrite the search to use generators:
    [code]def search(node):
        if target(node):
            yield node
        for child in children(node):
            yield from search(child)[/code]  and then the caller can call next(search(root)) .
      
   These problems can all be avoided using the stack of iterators design pattern.
  [code]def search(root):
    stack = [iter([root])]
    while stack:
        for node in stack[-1]:
            stack.append(iter(children(node)))
            break
        else:
            stack.pop()[/code]  This avoids the three problems above:
  
       
  • Pushing and popping a list is faster than calling a function in Python.
       
  • Lists can grow without limit, unlike the function call stack.
       
  • Since there’s no recursion, you can just return when you have a result:
    [code]def search(root):
        stack = [iter([root])]
        while stack:
            for node in stack[-1]:
                if target(node):
                    return node
                stack.append(iter(children(node)))
                break
            else:
                stack.pop()[/code]  
   The control flow here might seem a bit tricky if you’re not used to the way that Python’s for ... else construct interacts with break . The pattern works by maintaining a stack of iterators that remember the position reached in the iteration over the children of the node at each level of the search. After pushing a new iterator on the stack, the break exits the for loop, bypasses the else: clause, and goes round the while loop again, so that it picks up the new iterator from stack[-1] . When there are no more children in the current iteration, the for loop exits via the else: clause and pops the stack. Then the next iteration of the while loop picks up the iteration at the previous level from where it left off.
  ✴
  Two examples. First, finding a key in a possibly nested dictionary:
  [code]def search(d, key, default=None):
    """Return a value corresponding to the specified key in the (possibly
    nested) dictionary d. If there is no item with that key, return
    default.

    """
    stack = [iter(d.items())]
    while stack:
        for k, v in stack[-1]:
            if isinstance(v, dict):
                stack.append(iter(v.items()))
                break
            elif k == key:
                return v
        else:
            stack.pop()
    return default[/code]   Second, finding a simple path visiting a set of positions on a grid:

The stack of iterators pattern.-2 (recursion,structure,function,children,problems)

  [code]def hamilton_path(start, positions, directions=((0, 1), (1, 0), (0, -1), (-1, 0))):
    """Find a simple path that visits all positions.

    start: tuple(int, int)
        Starting position for the path.
    positions: iterable of tuple(int, int)
        Iterable of positions to be visited by the path.
    directions: iterable of tuple(int, int)
        Iterable of directions to take at each step.

    Return the path as a list of tuple(int, int) giving the order in
    which the positions are visited. Raise ValueError if there are no
    paths visiting all positions.

    """
    positions = set(positions)
    directions = list(directions)
    path = [start]
    stack = [iter(directions)]
    while path:
        x, y = path[-1]
        for dx, dy in stack[-1]:
            pos = x + dx, y + dy
            if pos in positions:
                path.append(pos)
                positions.remove(pos)
                stack.append(iter(directions))
                if not positions:
                    return path
                break
        else:
            positions.add(path.pop())
            stack.pop()
    raise ValueError("no path")[/code]  
       
  •   This requires Python 3.3 or later in order to be able to use the  yield from  statement.
       
  •   In software, a  design pattern  is a technique for working around a defect or omission in a particular programming language. For example, the well-known singleton pattern is a work-around for the lack of global variables in the Java language.
       
  •   Example adapted from this answer on Code Review.
       
  •   Example adapted from this answer on Code Review.
      

友荐云推荐




上一篇:第 7 单元:字符串和运算符
下一篇:Open Source is not dead: On the recent demise of RethinkDB
酷辣虫提示酷辣虫禁止发表任何与中华人民共和国法律有抵触的内容!所有内容由用户发布,并不代表酷辣虫的观点,酷辣虫无法对用户发布内容真实性提供任何的保证,请自行验证并承担风险与后果。如您有版权、违规等问题,请通过"联系我们"或"违规举报"告知我们处理。

刘星 发表于 2016-10-23 15:27:12
矿难在检讨中继续,楼价在控制中上升。
回复 支持 反对

使用道具 举报

雅霜 发表于 2016-11-1 23:21:02
爱情就像两个拉着橡皮筋的人,受伤的总是不愿意放手的那一个!
回复 支持 反对

使用道具 举报

小迷茫3 发表于 2016-11-12 19:31:56
楼主,笑一个,萌萌哒!
回复 支持 反对

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读

扫码访问 @iTTTTT瑞翔 的微博
回页顶回复上一篇下一篇回列表手机版
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )|网站地图 酷辣虫

© 2001-2016 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表