The stack of iterators pattern.

| |
[ 所属分类 开发（python） | 发布者 店小二05 | 时间 2016 | 作者 红领巾 ] 0人收藏点击收藏
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.

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): pass def 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:

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

1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责；
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性，不作出任何保证或承若；
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。