首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >使用线程执行TopSorted列表

问使用线程执行TopSorted列表
EN

Stack Overflow用户
提问于 2013-09-26 08:13:44
回答 1查看 91关注 0票数 0

我有一个需要按特定顺序执行的任务列表,例如Task2 -> Task1,所以必须先执行Task1,然后才能运行任务Task2。我已经构建了一个任务图,并应用了拓扑排序来获得任务执行的顺序,但现在我想使用线程来执行这些任务,这就是我被困的地方。这是我到目前为止一直在做的事情

代码语言:javascript
复制
//S = Hashset that contains tasks that has no input edges in graph
public HashSet<Task> S = new HashSet<Task> ();
for(Task n : AllTasks){ //AllTasks is an arraylist of tasks in graph
if(n.inEdges.size() == 0){
 S.add(n);}

}

//包含已排序元素的空列表ArrayList outList = new ArrayList();

代码语言:javascript
复制
//while S is non-empty do
while(!G.S.isEmpty()){
  //remove a node n from S
    Task n = G.S.iterator().next();
  G.S.remove(n);
  //insert n into L
  outList.add(n);

  n.start(); //Starts the thread

  //for each node m with an edge e from n to m do
  for(Iterator<Edge> it = n.outEdges.iterator();it.hasNext();){
    //remove edge e from the graph
    Edge e = it.next();
    Task m = e.to;
    it.remove();//Remove edge from n
    m.inEdges.remove(e);//Remove edge from m

    //if m has no other incoming edges then insert m into S
    if(m.inEdges.isEmpty()){
    G.S.add(m);
    }//if
  }//for

} //while

Task类扩展了Thread类,每个任务都有一个inEdges和outEdges的HashSet。我该怎么处理呢?

EN

回答 1

Stack Overflow用户

发布于 2013-09-26 13:29:39

你预计会有多少个任务?有几种方法可以解决这个问题。我会选择在总处理时间内优化代码的可读性和可维护性,因此我建议使用以下方法。

让Task扩展线程可能不是一个好办法。如果你有足够的任务,你会发现自己无法产生足够的线程。您的任务类应该反映您的问题域(例如,作业依赖关系)。已经有一组类可以很好地处理并发问题域( Executor框架)。通过以这种方式构造类,您可以轻松地从多线程实现切换到多进程实现。这就是我构建解决方案的方式。

  1. 创建了一种算法,该算法接受一组任务,并将它们汇总为相互独立的任务。例如,如果你有任务A,B,C,其中A依赖于B,但没有其他依赖关系,那么你的算法应该返回两个“汇总”的任务。一个用于"B,然后是A“,另一个用于C。另外,如果A依赖于C,而B依赖于C,那么它们将被汇总到同一个任务中(这是性能不是最优的)。
  2. 现在您有了一组可以相互独立运行的汇总任务。使用任意数量的线程启动ThreadPoolExecutor。
  3. 为每个汇总的任务创建一个Runnable,它将以适当的顺序运行子任务。将每个任务提交给执行者。
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/19017244

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档