萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Java 多執行緒遞歸併行模式:ExecutorService 與 ForkJoinPool 實戰

問題背景

樹狀結構(如檔案目錄、組織架構、AST)的遞歸遍歷若每個節點獨立運算且耗時,適合並行化。傳統遞歸單執行緒無法發揮多核效能。

方案一:ExecutorService + 遞歸提交任務

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;
}

方案二:ForkJoinPool (JDK 7+) 專為分治遞歸設計

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)

關鍵優化建議

  1. 任務粒度控制:節點計算太輕(< 1ms)時,併行開銷大於收益。建議閾值:將小任務合併為批次提交。
  2. 避免共享可變狀態:各任務操作獨立資料,結果用執行緒安全容器收集。
  3. 異常處理:Future.get() 或 join() 會重拋子任務異常,統一捕獲處理。
  4. 資源關閉:自建 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 分治專用引擎,針對遞歸問題選擇合適工具、控制任務粒度、妥善處理異常與取消,即能將多核效能最大化。

copyright © 萬盛學電腦網 all rights reserved