algorithm – 如何找到并行树中的哪些作业可以并行运行？

概述目前,我使用图形来存储依赖项,然后运行没有任何依赖项的所有顶点.这有效,但感觉很糟糕.我应该使用更好的算法或数据结构吗？ #!/usr/bin/perluse strict;use warnings;use Graph;#FIXME: naive implementation, there may be a much better way to do thissub run_in_ 目前,我使用图形来存储依赖项,然后运行没有任何依赖项的所有顶点.这有效,但感觉很糟糕.我应该使用更好的算法或数据结构吗？

#!/usr/bin/perluse strict;use warnings;use Graph;#FIXME: naive implementation,there may be a much better way to do thissub run_in_parallel {       my $g = shift->copy;       while (my @v = $g->vertices) {               my @run = grep { $g->is_successorless_vertex($_) } @v;               print "running ",join(",",@run)," in parallel\n";               for my $compenent (@run) {                       $g->delete_vertex($compenent);               };       }}my $g = Graph->new;while (<DATA>) {       my ($component,@dependencIEs) = split;       unless ($g->has_vertex($component)) {               $g->add_vertex($component);       }       for my $dependency (@dependencIEs) {               unless ($g->has_vertex($dependency)) {                       $g->add_vertex($dependency);               }               $g->add_edge($component,$dependency);       }}run_in_parallel($g);#component  dependency List__DATA__a           b c db           ec           f gdefg

解决方法 另一个想法是到 use a Petri net.
图中的节点是它的位置,动作是它的过渡.
每个地方都应该只有一个启用转换,即使它没有依赖关系.
这样你甚至不需要放置任何初始令牌.

这也包含了Karl BIElefeldt的建议.

总结

以上是内存溢出为你收集整理的algorithm – 如何找到并行树中的哪些作业可以并行运行？全部内容，希望文章能够帮你解决algorithm – 如何找到并行树中的哪些作业可以并行运行？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。