非常に大きなツリーでDFSを実行する最適な方法は何ですか？

Question

状況：

• アプリケーションの世界は、数十万の状態で構成されています。
• 状態が与えられれば、私は3つまたは4つの他の到達可能状態のセットを試すことができます。単純な再帰は非常に高速になる状態のツリーを構築できます。
• このツリーの特定の深さまでルート状態からDFSを実行して、「最小」状態（ノードの値を計算することは問題とは関係ありません）を含むサブツリーを検索する必要があります。

単一のスレッドを使用してDFSを実行するが、非常に遅い。 15レベルをカバーするには数分かかるかもしれませんが、この凶悪なパフォーマンスを改善する必要があります。あまりに多くのスレッドを作成した各サブツリーにスレッドを割り当てようとしたところ、OutOfMemoryErrorが発生しました。 ThreadPoolExecutorを使ったほうがあまり良くありませんでした。

私の質問：この大きなツリーをトラバースする最も効率的な方法は何ですか？

Answer 1

ツリーのナビゲートはあなたのツリーが約3,600万のノードを持つので難しいと思います。代わりに、各ノードでやっていることは高価です。

import java.util.ArrayList; 
import java.util.List; 
import java.util.concurrent.*; 
import java.util.concurrent.atomic.AtomicLong; 

public class Main { 
    public static final int TOP_LEVELS = 2; 

    enum BuySell {} 

    private static final AtomicLong called = new AtomicLong(); 

    public static void main(String... args) throws InterruptedException { 
     int maxLevels = 15; 
     long start = System.nanoTime(); 
     method(maxLevels); 
     long time = System.nanoTime() - start; 
     System.out.printf("Took %.3f second to navigate %,d levels called %,d times%n", time/1e9, maxLevels, called.longValue()); 
    } 

    public static void method(int maxLevels) throws InterruptedException { 
     ExecutorService service = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors()); 
     try { 
      int result = method(service, 0, maxLevels - 1, new int[maxLevels]).call(); 
     } catch (Exception e) { 
      e.printStackTrace(); 
     } 
     service.shutdown(); 
     service.awaitTermination(10, TimeUnit.MINUTES); 
    } 

    // single threaded process the highest levels of the tree. 
    private static Callable<Integer> method(final ExecutorService service, final int level, final int maxLevel, final int[] options) { 
     int choices = level % 2 == 0 ? 3 : 4; 
     final List<Callable<Integer>> callables = new ArrayList<Callable<Integer>>(choices); 
     for (int i = 0; i < choices; i++) { 
      options[level] = i; 
      Callable<Integer> callable = level < TOP_LEVELS ? 
        method(service, level + 1, maxLevel, options) : 
        method1(service, level + 1, maxLevel, options); 
      callables.add(callable); 
     } 
     return new Callable<Integer>() { 
      @Override 
      public Integer call() throws Exception { 
       Integer min = Integer.MAX_VALUE; 
       for (Callable<Integer> result : callables) { 
        Integer num = result.call(); 
        if (min > num) 
         min = num; 
       } 
       return min; 
      } 
     }; 
    } 

    // at this level, process the branches in separate threads. 
    private static Callable<Integer> method1(final ExecutorService service, final int level, final int maxLevel, final int[] options) { 
     int choices = level % 2 == 0 ? 3 : 4; 
     final List<Future<Integer>> futures = new ArrayList<Future<Integer>>(choices); 
     for (int i = 0; i < choices; i++) { 
      options[level] = i; 
      final int[] optionsCopy = options.clone(); 
      Future<Integer> future = service.submit(new Callable<Integer>() { 
       @Override 
       public Integer call() { 
        return method2(level + 1, maxLevel, optionsCopy); 
       } 
      }); 
      futures.add(future); 
     } 
     return new Callable<Integer>() { 
      @Override 
      public Integer call() throws Exception { 
       Integer min = Integer.MAX_VALUE; 
       for (Future<Integer> result : futures) { 
        Integer num = result.get(); 
        if (min > num) 
         min = num; 
       } 
       return min; 
      } 
     }; 
    } 

    // at these levels each task processes in its own thread. 
    private static int method2(int level, int maxLevel, int[] options) { 
     if (level == maxLevel) { 
      return process(options); 
     } 
     int choices = level % 2 == 0 ? 3 : 4; 
     int min = Integer.MAX_VALUE; 
     for (int i = 0; i < choices; i++) { 
      options[level] = i; 
      int n = method2(level + 1, maxLevel, options); 
      if (min > n) 
       min = n; 
     } 

     return min; 
    } 

    private static int process(final int[] options) { 
     int min = options[0]; 
     for (int i : options) 
      if (min > i) 
       min = i; 
     called.incrementAndGet(); 
     return min; 
    } 
} 

プリント

Took 1.273 second to navigate 15 levels called 35,831,808 times 

---

私はあなたがスレッドの数を制限し、唯一の木の最高レベルのために別のスレッドを使用することをお勧め。いくつのコアがありますか？すべてのコアをビジー状態にするのに十分なスレッドがあれば、オーバーヘッドを追加するだけでスレッドをさらに作成する必要はありません。

Javaにはスレッドセーフな組み込みスタックがありますが、より効率的なArrayListを使用します。

Answer 2

あなたは間違いなく反復メソッドを使用する必要があります。 N（m）は、グラフ内のノードの数（エッジ）を表し、この時の複雑さはO（N + M）である

STACK.push(root) 
while (STACK.nonempty) 
    current = STACK.pop 
    if (current.done) continue 
    // ... do something with node ... 
    current.done = true 
    FOREACH (neighbor n of current) 
     if (! n.done) 
      STACK.push(n) 

：最も簡単な方法は次のように疑似コードでスタックベースのDFSであります。あなたはツリーを持っているので、これはO（n）であり、簡単にn> 1.000.000ですばやく動くはずです...