java - 是否可以并行运行递归函数？

Question

我有一个 findAllPaths() 函数来查找图中所有可能的路径(存储在 matrix 中):

    public void findAllPaths(final Matrix matrix, final Index s, final Index d, HashMap <Index , Boolean> isVisited, Collection localPathList)
    {
        // Mark the current node
        isVisited.put(s, true);
        if (s.equals(d)) {
            this.pathsList.add(new ArrayList<>(localPathList));
            // if match found no need to traverse more till depth
            isVisited.put(s, false);
            return;
        }

        // Recur for all the vertices neighbors to current index
        for (Index i : matrix.getNeighbors(s)) {
            if (!isVisited.get(i)) {
                // store current node in path[]
                localPathList.add(i);
                findAllPaths(matrix, i, d, isVisited, localPathList);
                // remove current node in path[]
                localPathList.remove(i);
            }
        }

        // Mark the current node
        isVisited.put(s, false);
    }

我正在努力让它尽可能地并行运行。

有没有人知道我如何才能做到这一点？

Answer 1

您可能想使用 java.util.concurrent 包的 RecursiveTask 或 RecursiveAction 并在 ForkjoinPool 中运行它。这些类的一般思想是您在代码中决定哪部分工作应该在一个线程中完成。如果工作大于该部分，则将一部分工作 fork 到新线程。要获得所有线程的结果，请使用 join()。这些类使用工作窃取算法:当一个线程完成时，它可以窃取另一个线程的工作，因此这对于像这样的大量数字运算非常有效。

RecursiveTask 或 RecursiveAction 的一个先决条件是您应该能够将工作分成几部分，并且您知道如何将完成的部分组合成最终结果。一个大数的阶乘是一个可以使用 RecursiveTask 计算的例子:10!可以拆分为 (1 * 2 * 3 * 4 * 5) 和 (6 * 7 * 8 * 9 * 10)。两个子结果可以相乘得到最终结果。