0

问候溢出者，

  • 数据结构是任意数量节点的无环树。
  • 较浅的节点依赖于较深节点的结果。
  • 最终结果可以简单地通过递归遍历树来计算。
  • 如果我有无限线程，我会为每个节点分配一个线程甚至更多。
  • 分配给较浅节点的线程将等待较深节点的线程完成。
  • 但是，我只有有限的线程；有时更多，有时少于总节点。

关于如何遍历这些树并最终以有限的线程获得最终结果的任何想法？

问候

4

4 回答 4

3

您想查看有向无环图 (DAG) 的拓扑排序。

如果图中的节点表示“作业”，则 DAG 的拓扑排序为您提供了必须完成的事情的顺序。维基百科页面具有得出订单的算法。

获得订单后，您的工作线程将开始使用此订单中的“作业”（元素）。在开始作业之前，线程需要检查相关作业是否已完成，但它们应该已经完成​​，或者正在由另一个线程进行。

既然你有一个树结构，你可以稍微特殊一下：简单地把子节点放在第一位，然后是他们的父母，等等，依次完成树的每一级。

此外，在问题上抛出“无限”数量的线程会引起人们的注意……除非您的工作通常是 I/O 绑定的，否则（CPU 数量 + 一些常量）线程似乎是合适的。

于 2011-01-02T05:27:03.677 回答
1
  1. 您应该始终考虑使用线程池，而不是无限数量的线程。

  2. 类库提供了灵活的线程池实现以及一些有用的预定义配置。您可以通过调用 Executors 中的静态工厂方法之一来创建线程池。我认为对于您的情况，应使用以下方法：

    newFixedThreadPool - 创建一个固定大小的线程池，在提交任务时创建线程，直到最大池大小，然后尝试保持池大小不变（如果线程因意外异常而死亡，则添加新线程）。

    在创建线程池期间，您可以设置池大小，但您可以向执行程序添加任意数量的线程（例如，每个节点的线程）。不会执行的线程将被排队。

  3. 如果你有一批计算要提交给 Executor，并且你想在结果可用时检索它们，你可以使用完成服务。CompletionService 结合了 Executor 和 BlockingQueue 的功能。您可以将 Callable 任务提交给它以供执行，并使用类似于 take 和 poll 方法的队列来检索已完成的结果，并在它们可用时打包为 Futures。ExecutorCompletionService 实现 CompletionService，将计算委托给 Executor。

    这是在 Concurrency 书中使用 Java 中的 CompletionService 的示例：

    public class Renderer {
    private final ExecutorService executor;



    Renderer(ExecutorService executor) { this.executor = executor; }


void renderPage(CharSequence source) {
    final List<ImageInfo> info = scanForImageInfo(source);
    CompletionService<ImageData> completionService =
        new ExecutorCompletionService<ImageData>(executor);
    for (final ImageInfo imageInfo : info)
        completionService.submit(new Callable<ImageData>() {
             public ImageData call() {
                 return imageInfo.downloadImage();
             }
        });


    renderText(source);


    try {
        for (int t = 0, n =  info.size(); t < n;  t++) {
            Future<ImageData> f = completionService.take();
            ImageData imageData = f.get();
            renderImage(imageData);
        }
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    } catch (ExecutionException e) {
        throw launderThrowable(e.getCause());
    }
}

    

}
于 2011-01-02T05:55:44.243 回答
1

对于 CPU 密集型任务，最佳线程数可能是您拥有的内核数或逻辑线程数。这可能是您机器上的 4、6 或 8。创建与可用物理线程数匹配的线程池的一种简单方法是。

ExecutorService pool = Executors.newFixedThreadPool(
                       Runtime.getRuntime().availableProcessors());

如果您的线程数多于内核数，则您的线程将不得不进行上下文切换，这会增加开销并使它们变慢。

于 2011-01-02T10:08:46.577 回答
1

这看起来很适合为 Java 7 开发的 Fork/Join 框架；它也可用于 Java 6，网址为http://gee.cs.oswego.edu/dl/concurrency-interest/（在 jsr166y 下）。您可以使用RecursiveTask该类来表示您的计算并为数据结构中的子节点派生额外的任务。在http://download.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html有一个简短的教程。

于 2011-01-04T21:00:04.917 回答