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 - 在樹結構中映射作業依賴關係

回答

相關問題