0

巨大なバイナリ ツリー (各ノードには合格ノードと不合格ノードがあります) があり、DFS を使用してすべての可能なパスを取得するために、このツリーをトラバースしたいと考えています。ツリーが巨大なため、単一のスレッドを使用して DFS にかかる時間は非常に長くなります。そのため、この問題を解決するために、並列 DFS を実行することを検討しています。基本的な考え方は以下です。

  • 単一のスレッドから開始し、通常の DFS を実行します。これがノードに到達すると、失敗したノードを開始ノードとして開始する新しいスレッドを生成し、これまで移動したノードをその呼び出しに渡します。
  • 初期スレッドはパスのパスで継続します
  • 最後に、すべてのスレッドは移動したノードのリストを返します。そのため、複数のスレッドでツリー全体をトラバースします。いわゆる親スレッドが移動したノードの情報を子スレッドに渡すため、各スレッドはいわゆる自給自足です

これを実装するために、私はこれを行うことを考えています

  • newCachedThreadPool を使用します。
  • メインでは、プールを作成し、呼び出し可能な DFS クラスへの最初の呼び出しを開始します。DFS クラスのコンストラクターも ExecutorService を受け取るため、新しく生成された Thread は、上記で説明したルールを使用して新しい Thread を生成することもできます。

DFS のコード実装

    public class DFS implements Callable<List<List<TestNode>>> {
        private Node node = null;
        private List<TestNode> testNodeList = new ArrayList<TestNode>();
        private List<List<TestNode>> returnNodeList = new ArrayList<List<TestNode>>();
        private ExecutorService service = null;

        public DFS(ExecutorService service, Node node, List<TestNode> initList) {
           this.node = node;
           this.service = service;
           if (initList != null && initList.size() > 0) {
              testNodeList.addAll(initList);
        }
    }

    public List<List<TestNode>> call() throws Exception {
         performDFS(this.node);
         returnNodeList.add(testNodeList);
         return returnNodeList;
    }

    private void performDFS(Node node) {
         TestNode testNode = new TestNode();
         testNode.setName(node.getName());
         Thread t = Thread.currentThread();
         testNode.setThreadName(t.getName());
         testNodeList.add(testNode);

         if (node.getPass() != null) {
            performDFS(node.getPass());
         }
         if (node.getFail() != null) {
             Callable<List<List<TestNode>>> task = new DFS(service, node.getFail(),         
             this.testNodeList);
             Future<List<List<TestNode>>> returnList = service.submit(task);
             try {
                 returnNodeList.addAll(returnList.get());
             }
             catch (InterruptedException e) {
             }
             catch (ExecutionException e) {
             }
       }
    }

}

メインクラス

    public static void main(String[] args) {
          Main main = new Main();
          Node root = main.createTree();
          ExecutorService service = Executors.newCachedThreadPool();
          Callable<List<List<TestNode>>> task = new DFS(service, root, null);

          Future<List<List<TestNode>>> returnList = null;
          try {
             returnList = service.submit(task);
         }
         catch (Exception e) {
         }
         try {
            main.displayTestNode(returnList.get());
            service.shutdown();
         }
         catch (InterruptedException e) {
        }
        catch (ExecutionException e) {
      }
   }

質問

  • これは理にかなっていますか？これは可能ですか？
  • 同じスレッドが何度も表示されるため、実装に問題があります
4

2 に答える 2

1

はい、並列 DFS を作成することは可能です。スレッドプールを使用することも可能かもしれませんが、fork/joinスタイルのアルゴリズムの方が「自然」だと思います。fork 操作は、ノードのすべての子を並行してトラバースしますが、join 操作は、返されたパスのリストを単純に連結します。

于 2012-04-21T10:49:03.243 に答える
-1

これに関する最大の問題は、何も並行して実行することがないため、マルチスレッドが役に立たないことだと思います。スレッドを 1 つ生成してすぐに待機するため、一度に計算できるスレッドは 1 つだけです。

尋ねるべきもう 1 つの質問は、すべてのパスのリストが必要な理由 (および必要な場合) です。ツリーでは、ルートからのパスはエンドポイントによって一意に識別されます (「アップ」リンクをたどることでそこから再構築できます)。さらに、すべてのパスのリストはより大きなメモリの複雑さを持っています (Nノードを持つ完全にバランスの取れたバイナリ ツリーでは、ツリーのメモリの複雑さはO(N)であるのに対し、すべてのパスのリストのメモリの複雑さO(N*log(N))は作成も）。「アップ」リンクがツリーで提供されていない場合でも、それらを再構築することができます (おそらくとしてIdentitiyHashMap<Node, Node>)O(N)これにより、すべてのパスのリストを作成するよりも時間 (およびメモリ) が少なくなります。大きなツリーを無駄な表現に変換することから処理を開始する必要はないと思います。

于 2012-04-21T11:00:50.183 に答える