0

あいさつOverflowers、

  • データ構造は、任意の数のノードの非巡回ツリーです。
  • 浅いノードは、深いノードの結果に依存します。
  • 最終的な結果は、ツリーを再帰的にトラバースすることで簡単に計算できます。
  • 無制限のスレッドがある場合は、各ノードに1つ以上のスレッドを割り当てます。
  • 浅いノードに割り当てられたスレッドは、深いノードのスレッドが終了するのを待ちます。
  • ただし、スレッドは限られています。場合によってはノードの総数より多く、場合によっては少なくなります。

そのような木を横断し、最終的に限られたスレッドで最終結果を得る方法について何か考えはありますか？

よろしく

4

4 に答える 4

3

有向非巡回グラフ (DAG) のトポロジー順序付けを見たいとします。

DAG のトポロジー順序は、グラフ内のノードが「ジョブ」を表す場合に実行する必要がある順序を示します。ウィキペディアのページには、注文に到達するためのアルゴリズムがあります。

順序を取得すると、ワーカー スレッドはこの順序から「ジョブ」(要素) を消費し始めます。ジョブを開始する前に、スレッドは依存ジョブが終了しているかどうかを確認する必要がありますが、それらは終了しているか、別のスレッドによって進行中である必要があります。

ツリー構造を持っているので、これを少し特殊なケースにすることができます: 単純に子ノードを最初に配置し、次にその親ノードを配置し、ツリーの各レベルを次々と実行します。

また、問題に「無制限」の数のスレッドを投入すると眉をひそめます...ジョブが通常 I/O バウンドでない限り、(CPU の数 + 定数) スレッドが適切であるように思われます。

于 2011-01-02T05:27:03.677 に答える
1
  1. 常にスレッド プールの使用を検討する必要がありますが、無制限の数のスレッドではありません。

  2. クラス ライブラリは、いくつかの便利な事前定義された構成と共に、柔軟なスレッド プールの実装を提供します。Executor で静的ファクトリ メソッドの 1 つを呼び出すことにより、スレッド プールを作成できます。あなたの場合、次の方法を使用する必要があると思います。

    newFixedThreadPool - 固定サイズのスレッド プールを作成します。タスクが送信されると最大プール サイズまでスレッドが作成され、プール サイズを一定に保とうとします (予期しない例外によりスレッドが終了した場合は、新しいスレッドを追加します)。

    スレッド プールの作成中にプール サイズを設定しますが、必要な数のスレッドをエグゼキュータに追加できます (たとえば、ノードごとのスレッド)。実行されないスレッドはキューに入れられます。

  3. Executor に送信する計算のバッチがあり、それらの結果が利用可能になったときに取得したい場合は、完了サービスを使用できます。CompletionService は、Executor と BlockingQueue の機能を組み合わせたものです。Callable タスクを実行のために送信し、メソッド take や poll のようなキューを使用して、使用可能になったときに Future としてパッケージ化された完了した結果を取得できます。ExecutorCompletionService は CompletionService を実装し、計算を Executor に委譲します。

    以下は、Concurrency book で 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 フレームワークに適しているようです。また、 http ://gee.cs.oswego.edu/dl/concurrency-interest/ (jsr166y の下)で Java 6 にも使用できます。クラスを使用しRecursiveTaskて計算を表し、データ構造内の子ノードの追加タスクをフォークできます。http://download.oracle.com/javase/tutorial/essential/concurrency/forkjoin.htmlに短いチュートリアルがあります。

于 2011-01-04T21:00:04.917 に答える