在一棵非常大的树上执行DFS的最佳方法是什么？ [英] What's the best way to perform DFS on a very large tree?

问题描述

以下是这种情况：

• 应用程序世界由数十万个州组成。


• 给定状态，我可以计算出一组3或4个其他可达状态。一个简单的递归可以构建一个非常快速的非常大的状态树。


• 我需要从根状态执行此树中特定深度的DFS，以搜索包含最小状态的子树（计算节点的值是无关紧要的）问题）。

使用单个线程执行DFS工作，但速度很慢。覆盖15级可能需要几分钟，我需要改善这种糟糕的表现。尝试为每个子树分配一个线程，创建了太多线程并导致 OutOfMemoryError 。使用 ThreadPoolExecutor 并没有好多少。

Using a single thread to perform the DFS works, but is very slow. Covering 15 levels down can take a few good minutes, and I need to improve this atrocious performance. Trying to assign a thread to each subtree created too many threads and caused an OutOfMemoryError. Using a ThreadPoolExecutor wasn't much better.

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

My question: What's the most efficient way to traverse this large tree?

推荐答案

我不认为导航树是你的问题，因为你的树大概有36棵树百万个节点。相反，你在每个节点上做的事情更有可能是昂贵的。

I don't believe navigating the tree is your problem as your tree has about 36 million nodes. Instead is it more likely what you are doing with each node is expensive.

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

---

我建议你限制线程数量，并且只为树的最高级别使用单独的线程。你有几个核心？一旦你有足够的线程来保持每个核心繁忙，你就不需要创建更多的线程，因为这只会增加开销。

---

I suggest you limit the number of threads and only use separate threads for the highest levels of the tree. How many cores do you have? Once you have enough threads to keep every core busy, you don't need to create more threads as this just adds overhead.

Java有一个内置的堆栈，线程安全，但是我会使用更高效的ArrayList。

Java has a built in Stack which thread safe, however I would just use ArrayList which is more efficient.

这篇关于在一棵非常大的树上执行DFS的最佳方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！