算法找到獨立集合

夥計，我有一個問題。我是一個Python編寫的腳本，它由幾個模塊組成。某些模塊依賴於其他模塊，因此只有在依賴模塊成功運行後才能運行它們。因此，每個模塊都是從一個基類模塊中派生出來的，並覆蓋一個名爲DEPENDENCIES的列表，這個列表是在模塊運行時需要滿足的依賴關係列表。有一個模塊需要在所有其他模塊之前運行。目前我正在做這樣的事情。算法找到獨立集合

modules_to_run.append(a) 
modules_to_run.append(b) 
modules_to_run.append(c) 
..... 
.....  
modules_to_run.append(z) 


# Very simplistically just run the Analysis modules sequentially in 
# an order that respects their dependencies 
foundOne = True 
while foundOne and len(modules_to_run) > 0: 
    foundOne = False 
    for module in modules_to_run: 
     if len(module.DEPENDENCIES) == 0: 
      foundOne = True 
      print_log("Executing module %s..." % module.__name__, log) 
      try: 
       module().execute() 
       modules_to_run.remove(module) 
       for module2 in modules_to_run: 
        try: 
         module2.DEPENDENCIES.remove(module) 
        except: 
         #module may not be in module2's DEPENDENCIES 
         pass 
      except Exception as e: 
       print_log("ERROR: %s did not run to completion" % module.__name__, log) 
       modules_to_run.remove(module) 
       print_log(e, log) 

for module in modules_to_run: 
    name = module.__name__ 
    print_log("ERROR: %s has unmet dependencies and could not be run:" % name, log) 
    print_log(module.DEPENDENCIES, log)

現在我看到一些模塊需要很長時間才能執行並且腳本運行時間過長。所以我想讓它成爲多線程，以便獨立模塊可以同時運行，從而節省時間。所以我想要一個解決方案，在每次迭代之後，我將重新計算'n'個獨立模塊（其中'n'是線程的最大數量，通常以2開始），並行執行並等待它們在下一次迭代之前完成。我對算法知之甚少，所以我被卡住了。你可以幫助我找到一種算法，在每次迭代之後發現最大'n'組獨立模塊，這些模塊彼此之間沒有任何依賴關係。

來源

2010-03-07 kumar

雖然我無法主動回答主要問題，但我可以說python實現線程化的方式可能不會有太多的性能增益（如果有的話），除非使用多個進程，聽起來像是一團糟爲了這。 – 2010-03-07 07:52:49

如果執行時間被文件I/O（或網絡I/O等）膨脹，則線程可能沒有問題。否則，請查看Python 2.6的多處理庫。它們具有與線程模塊類似的API，並且它們非常簡單易用。 – detly 2010-03-07 08:26:05

我最近發佈了topological sorting的描述in a question about make -j。情緣！來自維基百科的文章：

拓撲排序（拓撲順序）的規範應用是在調度一系列作業或任務;拓撲排序算法首先在20世紀60年代早期在項目管理中用於調度的PERT技術（Jarnagin 1960）中進行了研究。作業由頂點表示，如果作業x必須在作業開始之前完成（例如，洗衣服時，洗衣機必須在衣服乾燥之前完成），則從x到y存在邊緣。然後，拓撲排序給出執行作業的順序。

粗線條：

建立依賴關係圖。
查找n沒有相關性的模塊。這些可以現在並行執行。
從圖表中刪除這些模塊。
重複步驟2直到完成。

請閱讀這些鏈接以獲取更詳細的說明。

來源

2010-03-07 07:55:59

從你的設置描述你也可以直接做。

它看起來像每個模塊都知道它的依賴關係。然後在每個模塊中添加謂詞函數，說明它是否可以運行足夠簡單。當且僅當滿足它的所有先決條件依賴性時才能運行模塊。

頂級模塊沒有依賴關係，所以它們可以從頭開始運行。

基本上，這是一個部分拓撲排序的簡單實現（你不必探索所有的依賴關係圖，只是停留在頂層）。

兩個陷阱要注意的：

如果你的依賴包含週期（A取決於取決於A C依賴於B），它可能會永遠循環（這意味着這個問題無解）。你應該檢測到這種情況，並報告和錯誤。

您可以運行的模塊可能少於線程數。這應該不是一個錯誤。然後，當你有n個可用的模塊運行時，或者當你詢問每個模塊是否可以運行時，你都找到了解決方案。

來源

2010-03-07 08:23:23 kriss

你是對的！我可以實現一個can_run（）方法並循環遍歷所有剩餘的模塊以查找至多「n」個模塊，然後啓動工作線程來運行它們。感謝您的建議， – kumar 2010-03-07 11:46:28

算法找到獨立集合

回答

相關問題