Python - 在树结构中映射作业依赖关系

我有具有依赖关系和存在状态的作业列表。我想要完成每项工作，并将依赖关系映射为一棵树。当父项依赖关系都处于完成状态时，树的末尾将为。那么就没有必要走了。我不确定是否应该使用递归，或者如果这是唯一的可能性。有本地映射工具或数据结构可以帮助我吗？我将会重复可能接近10K的工作。Python - 在树结构中映射作业依赖关系

的伪代码

def map_depends(job_depends): 
    for job in job_depends: 
     if job.status = done: 
      job_tree_map.append(job.name) 
     else: 
      map_depends(job.get('dependencies')) 

def main():  
    for job in batch: 
       if job.get('dependencies'): 
        map_depends(job.get('dependencies'))

什么我谈论的视觉描述。

  -> job_depends1.status = done 
main_job            -> job_depends3 = running -> job_depends6 = done 
     -> job_depends2 = running......job_depends2 -> jon_depends4 = done 
                 -> job_depends5 = done

来源

2014-10-05 user3590149

你的代码看起来有点不一致：'job'和'jobs'，'job.get（depends）'和'job.get（'dependencies'）'。 – firegurafiku 2014-10-05 01:27:22

谢谢。进行更正。 – user3590149 2014-10-05 01:51:19

如果树很深，使用递归算法可能会导致堆栈溢出，因为默认情况下，CPython的限制为1000个嵌套调用。您可以使用sys.setrecursionlimit来设置自己的极限值，但通常不推荐。所以，在你的情况下，以迭代方式重写树遍历可能会更好。

例如，你可以写这样一个函数什么树过滤和遍历（不是伪代码）：

def walkjob(job): 
    if job is None: 
     return [] 

    result = [job, ] 
    cursor = 0 

    while cursor < len(result): 
     job = result[cursor] 
     result.extend(list(
      filter(lambda j: j.done, 
      job.children))) 
     cursor += 1 

    return result

这里它的使用在REPL：

>>> from bunch import Bunch 
>>> job = Bunch(value=1, done=True, children=[ 
...   Bunch(value=2, done=True, children=[]), 
...   Bunch(value=3, done=True, children=[ 
...    Bunch(value=4, done=False, children=[]), 
...    Bunch(value=5, done=True, children=[])])]) 
... 
>>> map(lambda j: (j.value, j.done), walkjob(job)) 
[(1, True), (2, True), (3, True), (5, True)]

可能相关的问题：

来源

2014-10-05 02:19:44 firegurafiku

如果我的脚本导致堆栈溢出，会发生什么情况？它会取下服务器吗？这可以包含吗？ – user3590149 2014-10-05 03:46:31

在堆栈溢出的情况下，您的代码将抛出'RuntimeError：超过最大递归深度'的错误。和任何其他异常一样，除非被捕获，否则它会将应用程序关闭（此异常在Python中可捕获）。 – firegurafiku 2014-10-05 17:52:19

树木是自然递归的数据结构，但是，可以递归使用明确的堆栈被写入可以反复做任何事。

很遗憾，对于你来说，在CPython 3之前你不会得到“收益”[34]，这使得递归生成器在早期版本中变得不切实际。所以如果你仍然瞄准2.7，你可能应该先递归地写东西，让它们以这种方式工作，然后以非递归方式做你的生成器。

对于一个堆栈，很多Python开发人员将使用append和pop或者acollections.deque。为了抽象起见，我可能使用http://stromberg.dnsalias.org/~strombrg/linked-list/，尽管CPython通常很慢。

来源

2014-10-05 02:21:09 user1277476

Python - 在树结构中映射作业依赖关系

回答

相关问题