代码之家 › 专栏 › 技术社区 › Tony Veijalainen

有没有办法将脚本中的答案列表转换为生成的值?

yield generator recursion python

3

Tony Veijalainen · 技术社区 · 15 年前

我有一个长期运行的程序,我想保持快速响应。该算法是递归的,因此有时,即使是运行时间较长的调用中的子任务也可能比整个运行时间较短的任务长。我曾尝试使用yield,但最终得到的结果是,在递归列表结构的不同级别(列表也是多级层次结构,记录调用深度)中,列表中充满了生成器。我最终制作了简单的打印答案版本,但它最终会打印答案。我不能只打印递归调用的结果,打印前还需要对结果进行后期处理。

有没有简单的模式可以使顶层函数调用产生值,但递归调用返回答案?我应该在递归调用结果上使用for循环,还是在递归调用中使用aswer的make list()?我是否应该输入depth参数并返回depth>深度为0时屈服?

不管怎样,有没有简单的方法可以将每行输出调用的一个答案返回给主Python程序?还是应该返回模块调用的完整列表?在Linux系统中,我可以轻松地在单独的解释器中运行带有“bg”的os call版本,不是吗?

这个问题是完全覆盖问题,对我的应用程序很有用的一个例子是,例如,在不使用组合的情况下执行相同的操作,只添加数字,直到它们超过限制,递归返回精确的和:

from __future__ import print_function
def subset(seq, mask):
    """ binary mask of len(seq) bits, return generator for the sequence """
    return (c for ind,c in enumerate(seq) if mask & (1<<ind))

numbers = [1, 5, 3, 9, 4]
print('Numbers: ',numbers)
print('Possible sums',min(numbers),'..',sum(numbers))

for i in range(1,2**len(numbers)):
    sub = list(subset(numbers, i))
    print(sum(sub),'=',' + '.join(str(s) for s in sub))

print()
target = 11
print ('Finding subsequence for sum = %i' % target)

check = None
for check in (subset(numbers, mask)
              for mask in range(1,2**len(numbers))
              if sum(subset(numbers, mask))==target):
    print (' + '.join(str(s) for s in check), ' = ', target)
if not check:
    print('No solutions')

2 回复 | 直到 15 年前

1

David Wolever 15 年前

您对实际要做的事情的细节有点欠缺,但下面是我的最佳猜测(注意:您需要Python 2.6):

def do_stuff(num):
    children = [ _do_stuff(x + 1) for x in range(num) ]
    for child in children:
        child.send(None)

    count = 0
    while children:
        child = children.pop(0)
        try:
            count += child.send(count)
        except StopIteration:
            continue
        children.append(child)

def _do_stuff(num):
    to_add = 0
    for x in range(num):
        from_parent = (yield (to_add + x))
        print "child %s got %s" %(num, from_parent)
        to_add += from_parent

其工作原理如下:

>>> do_stuff(3)
child 1 got 0
child 2 got 0
child 3 got 1
child 2 got 3
child 3 got 3
child 3 got 9

很抱歉,这个例子有点让人困惑,我的大脑现在还不能想出一个更好的例子。

另外,请注意: *这些子对象可以生成另一个生成器,该生成器可以添加到子对象列表中 *这个实现很慢(从列表的开头弹出需要O(n)个时间),请参阅“出列”模块 *那个 child.send(None) 需要“启动”发电机(也就是说,执行到第一个 yield )

2

0

Robert Rossney 15 年前

你的问题不太清楚。也许这会有帮助。

制作递归生成器很简单;函数只需迭代自身,而不是调用自身。例如,如果您想编写一个将树夷为平地的生成器,它可能如下所示:

def descendants(node):
   for child in children(node):
      yield child
      for descendant in descendants(child):
         yield descendant

这种方法是在找到每个子节点时将其返回给调用方。如果出于某种原因 children 函数本身就是一个生成器,需要整整一秒钟才能返回每个节点 descendants 函数将每秒向其调用方返回一次子节点。

这一切都假设这个过程是同步的。如果它是异步的(或可以被设置为异步的),那么您就有一个非常不同的问题,需要一种非常不同的方法。你可以把一个异步进程包装在一个生成器中,当结果变得可用时,它就会产生结果;如果这样做,对生成器的每次调用都将被阻塞,并等待后台线程(或进程)生成下一个可用的结果。这提供了一个简单的门面来隐藏异步代码背后的复杂性;打电话的人只是:

for x in get_things(param):
   print x

还有 get_things() 函数创建线程(或进程),并在线程返回对象时生成它们。

怎么了 得到你想要的东西 这当然是个大问题,完全取决于你的问题到底是什么。