Остановите генератор из блока в Python
У меня есть генератор, который приводит к узлам от Направленного графа без петель (DAG), глубина сначала:
def depth_first_search(self):
yield self, 0 # root
for child in self.get_child_nodes():
for node, depth in child.depth_first_search():
yield node, depth+1
Я могу выполнить итерации по узлам как это
for node, depth in graph.depth_first_search():
# do something
Я хотел бы смочь сказать генератор, от для цикла, мешать идти глубже в графике, если некоторое условие соблюдают.
Я предложил следующее решение, то использование внешняя функция.
def depth_first_search(self, stop_crit=lambda n,d: False):
yield self, 0 # root
for child in self.get_child_nodes():
for node, depth in child.depth_first_search():
yield node, depth+1
if stop_crit(node, depth): break
Это решение вынуждает меня объявить переменные, в которых я нуждаюсь, прежде чем stop_crit определяется так, к ним можно получить доступ от него.
В Ruby урожай возвращает последнее выражение из блока, таким образом, это могло удобно использоваться, чтобы сказать генератору продолжаться или останавливаться.
Что лучший способ состоит в том, чтобы достигнуть этой функциональности в Python?
3 ответа
Наивное решение:
def depth_first_search(self):
yield self, 0 # root
for child in self.get_child_nodes():
for node, depth in child.depth_first_search():
if(yield node, depth+1):
yield None # for .send
return
Вы можете называть это как обычно, но вам нужно сохранить итерацию для прерывания:
it = graph.depth_first_search()
for node, depth in it: #this is why there should be pronouns for loop iterables
stuff(node,depth)
if quit: it.send(1)
# it.next() should raise StopIteration on the next for iteration
Я думаю, что это работает прямо сейчас.
Обычно вы не говорите своему итеративному объекту для проверки условий, вы делаете это в теле цикла:
for node, depth in graph.depth_first_search():
if node meets condition:
# do something with node
break
# do something with node, its still referencing what you breaked on
Этот код имеет то преимущество, что не вызывает удивления и запутать кого угодно.
Корутины (bassfriend упоминал о них) сложны для непосвященных, поэтому вот одна из них. Я добавил немного тестового кода, чтобы вы могли увидеть, как это на самом деле работает.
class Node(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
# the producing coroutine, it sends data to the consumer
def depth_first_search(self, consumer, depth=0):
""" `consumer` is a started coroutine that yields True to continue a branch """
if consumer.send((self, depth)): # continue this branch?
for child in self.get_child_nodes():
child.depth_first_search(consumer, depth+1)
def get_child_nodes(self):
for node in (self.left, self.right):
if node is not None:
yield node
def __repr__(self):
return "Node(val=%d)" % self.val
def coroutine(func):
""" decorator that declares `func` as a coroutine and starts it """
def starter(*args, **kwargs):
co = func(*args, **kwargs)
next(co) # corotines need to be started/advanced to the first yield
return co
return starter
# the consumer takes data and yields if it wants to continue
@coroutine
def consumer( continue_branch=lambda n,d:True ):
node, depth = (yield True) # first node
while True:
print node, depth # do stuff
node, depth = (yield continue_branch(node, depth))
# testing
tree = Node(5, Node(2, Node(3), Node(4)), Node(6, Node(7), Node(8))) #
cons = consumer()
tree.depth_first_search(cons)# yields all
print
stopper = consumer(lambda n,d: n.val > 2) # skips the children of Node 2
tree.depth_first_search(stopper)
Фокус в том, что если вы сохраните роли ваших функций, где depth_first_search выдает узлы, то в итоге получится ужасный беспорядок... вместо этого узлы производятся и отправляются потребителю.
Поддержка короутинов в Python немного неудобна (@coroutine на помощь). Существует довольно хороший учебник по Python и множество ресурсов для языков, которые зависят от корутинов, таких как Lua. В любом случае, это очень крутая концепция, которую стоит изучить :-)