在非常大的树上执行 DFS 的最佳方法是什么？

Question

情况是这样的：

• 应用程序世界由数十万个状态组成。
• 给定一个状态，我可以计算出一组 3 或 4 个其他可到达的状态。一个简单的递归可以构建一棵状态树，它会变得非常大、非常快。
• 我需要从根状态到该树中的特定深度执行 DFS，以搜索包含“最小”状态的子树（计算节点的值与问题无关）。

使用单线程执行 DFS 可以工作，但速度非常慢。向下覆盖 15 个关卡可能需要几分钟的时间，我需要改进这种糟糕的表现。尝试为每个子树分配一个线程会创建太多线程并导致 OutOfMemoryError。使用 ThreadPoolExecutor 也好不了多少。

我的问题：遍历这棵大树最有效的方法是什么？

Answer 1

我不认为导航树是您的问题，因为您的树有大约 3600 万个节点。相反，您对每个节点所做的事情更有可能是昂贵的。

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 有一个内置的 Stack，它是线程安全的，但是我会使用 ArrayList，它更有效。

Answer 2

您肯定必须使用迭代方法。最简单的方法是基于堆栈的 DFS，其伪代码与此类似：

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)

其时间复杂度为 O(n+m)，其中 n (m) 表示图中的节点（边）数量。由于你有一棵树，这是 O(n) 并且应该可以轻松快速地实现 n>1.000.000...