樹狀結構(如檔案目錄、組織架構、AST)的遞歸遍歷若每個節點獨立運算且耗時,適合並行化。傳統遞歸單執行緒無法發揮多核效能。
public <T> void parallelRecursive(Executor exec,
List<Node<T>> nodes,
Queue<T> results) {
for (Node<T> n : nodes) {
exec.execute(() -> {
results.add(n.compute()); // 計算當前節點
parallelRecursive(exec, n.getChildren(), results); // 遞歸提交子節點
});
}
}
public <T> Collection<T> getParallelResults(List<Node<T>> nodes)
throws InterruptedException {
ExecutorService exec = Executors.newCachedThreadPool();
Queue<T> resultQueue = new ConcurrentLinkedQueue<>();
parallelRecursive(exec, nodes, resultQueue);
exec.shutdown();
exec.awaitTermination(Long.MAX_VALUE, TimeUnit.SECONDS);
return resultQueue;
}
class ComputeTask<T> extends RecursiveTask<List<T>> {
private final Node<T> node;
ComputeTask(Node<T> node) { this.node = node; }
@Override protected List<T> compute() {
List<T> results = new ArrayList<>();
results.add(node.compute()); // 當前節點計算
List<ComputeTask<T>> subtasks = new ArrayList<>();
for (Node<T> child : node.getChildren()) {
ComputeTask<T> t = new ComputeTask<>(child);
t.fork(); // 非同步提交子任務
subtasks.add(t);
}
for (ComputeTask<T> t : subtasks)
results.addAll(t.join()); // 等待並合併結果
return results;
}
}
// 使用方式
ForkJoinPool pool = ForkJoinPool.commonPool();
List<T> allResults = pool.invoke(new ComputeTask<>(rootNode));
| 維度 | ExecutorService + 遞歸 | ForkJoinPool |
|---|---|---|
| 適用場景 | 任務粒度較大、非嚴格分治 | 標準分治遞歸、任務可拆分為同類子任務 |
| 工作竊取 | 無 | 內建 work-stealing,負載均衡極佳 |
| 堆疊溢位風險 | 深度遞歸易爆堆疊 | 同樣需注意,可改用迭代或 ManagedBlocker |
| 結果收集 | 自行管理 Concurrent Queue | 自然回傳值合併 |
| API 複雜度 | 低 | 中(需繼承 RecursiveTask/Action) |
Future.get() 或 join() 會重拋子任務異常,統一捕獲處理。ExecutorService 必須 shutdown(),ForkJoinPool.commonPool() 由 JVM 管理。若遞歸問題無解(如約束滿足搜尋),需引入取消機制:
// 共享原子旗標
AtomicBoolean found = new AtomicBoolean(false);
void search(Node n) {
if (found.get()) return; // 其它執行緒已找到解
if (n.isSolution()) {
if (found.compareAndSet(false, true)) {
solutionRef.set(n); // 發布解
}
return;
}
// 並行搜尋子節點...
}
Java 提供 ExecutorService 通用併行框架與 ForkJoinPool 分治專用引擎,針對遞歸問題選擇合適工具、控制任務粒度、妥善處理異常與取消,即能將多核效能最大化。