gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-05 07:02:09 24 4
gpt4 key购买 nike

我有一个 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);
}

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

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

最佳答案

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

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

关于java - 是否可以并行运行递归函数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63633968/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com