算法找到独立集合

伙计，我有一个问题。我是一个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

算法找到独立集合

回答

相关问题