### 技术控

今日:19| 主题:57957

# [其他] The stack of iterators pattern.

206 3
 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.   Here’s how you might implement it in Python: def search(node):    for child in children(node):        search(child)复制代码 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: def search(node):    if target(node):        return node    for child in children(node):        result = search(child)        if result is not None:            return result复制代码or you could return the result non-locally using an exception: class Found(Exception):    passdef search(node):    if target(node):        raise Found(node)    for child in children(node):        search(child)复制代码or you could rewrite the search to use generators: def search(node):    if target(node):        yield node    for child in children(node):        yield from search(child)复制代码 and then the caller can call next(search(root)) .       These problems can all be avoided using the stack of iterators design pattern. def search(root):    stack = [iter([root])]    while stack:        for node in stack[-1]:            stack.append(iter(children(node)))            break        else:            stack.pop()复制代码 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: 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()复制代码    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: 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复制代码  Second, finding a simple path visiting a set of positions on a grid: The stack of iterators pattern. 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")复制代码       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.

 矿难在检讨中继续，楼价在控制中上升。

 爱情就像两个拉着橡皮筋的人,受伤的总是不愿意放手的那一个!

 楼主，笑一个，萌萌哒！

• ## 甘肃成县县委：电商近在咫尺的几条“泥路”

【亿邦动力网讯】5月27日消息，在 2017中国电子 [...]

• ## 柯洁对战阿尔法狗直播 柯洁暂落后

5月27日，中国围棋峰会人机大战三番棋第三局继续 [...]

• ## 你最适合哪种穿搭风格？看完这篇你就知道了

微信号 VintageLond [...]

• ## 潜水表买了不会玩？那就白买了

微信号 wbiaoww 看 [...]

• ## 机器学习在电商领域的应用

以下内容精选自 2017全球机器学习技术大会系 [...]

• ## 果壳科普实验：远看头发光滑柔顺，放大个几

微信号 lengxhboss [...]

• ## 金立刘立荣：下半年推出四摄像头与全面屏结

微信号 sunshine-Me [...]

• ## 入股联华超市，阿里巴巴百联新零售合作“一

微信号 txws_txws [...]

• ## 这国曾敲诈中国十几亿美元，如今为讨好中国

微信号 fuxingcom [...]

• ## 福特可能会在自动驾驶汽车上路前推出打车服

BI中文站 5月27日报道 福特执行副总裁兼北 [...]