Java中如何用ForkJoinPool比较两个数组？递归实现相关疑问

一、修改现有代码为查找目标数组元素的位置 #

你原来的代码存在两个核心问题：找到第一个匹配项就直接返回，无法收集所有匹配索引；lista是方法局部变量，每次递归都会重新创建，根本无法保存结果。下面是优化后的版本，能收集data数组中所有存在于target数组里的元素索引：

递归版本 #

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class ArraySearch {
    // 把target转成Set，提升单次元素查找效率
    private static Set<Byte> targetSet;

    public static ArrayList<Integer> findAllMatches(byte[] data, byte[] target) {
        targetSet = new HashSet<>();
        for (byte b : target) {
            targetSet.add(b);
        }
        ArrayList<Integer> result = new ArrayList<>();
        recursiveSearch(data, 0, result);
        return result;
    }

    private static void recursiveSearch(byte[] data, int start, ArrayList<Integer> result) {
        // 递归终止：遍历完整个data数组
        if (start == data.length) {
            return;
        }
        // 当前元素在目标数组中存在，记录索引
        if (targetSet.contains(data[start])) {
            result.add(start);
        }
        // 递归查找下一个位置
        recursiveSearch(data, start + 1, result);
    }
}

说明：将target转为HashSet是为了把单次元素查找的时间复杂度从O(n)降到O(1)，避免每次递归都遍历整个target数组。

非递归版本（如果不想用递归） #

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class ArraySearch {
    public static ArrayList<Integer> findAllMatches(byte[] data, byte[] target) {
        Set<Byte> targetSet = new HashSet<>();
        for (byte b : target) {
            targetSet.add(b);
        }
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < data.length; i++) {
            if (targetSet.contains(data[i])) {
                result.add(i);
            }
        }
        return result;
    }
}

二、递归实现两个数组相同元素的位置 #

如果你的需求是找到两个数组中值相同的元素各自的索引对（比如data[i] == target[j]时，记录(i,j)），递归实现可以这样写：

import java.util.ArrayList;
import java.util.List;

public class CommonElementPositions {
    public static List<int[]> findCommonPositions(byte[] data, byte[] target) {
        List<int[]> result = new ArrayList<>();
        recursiveMatch(data, target, 0, 0, result);
        return result;
    }

    private static void recursiveMatch(byte[] data, byte[] target, int dataIndex, int targetIndex, List<int[]> result) {
        // 递归终止条件：任一数组遍历完成
        if (dataIndex >= data.length || targetIndex >= target.length) {
            return;
        }
        // 当前元素匹配，记录索引对
        if (data[dataIndex] == target[targetIndex]) {
            result.add(new int[]{dataIndex, targetIndex});
            // 继续查找两个数组的下一个元素
            recursiveMatch(data, target, dataIndex + 1, targetIndex + 1, result);
        } else {
            // 不匹配时，分两种情况递归：移动data的索引，或者移动target的索引
            recursiveMatch(data, target, dataIndex + 1, targetIndex, result);
            recursiveMatch(data, target, dataIndex, targetIndex + 1, result);
        }
    }
}

注意：这种递归方式的时间复杂度是O(m*n)（m、n分别为两个数组的长度），如果数组很大，可能触发栈溢出，建议用非递归或分治优化。

三、非递归方式使用ForkJoinPool实现并行查找 #

ForkJoinPool适合处理可拆分的分治任务，我们可以把data数组拆分成多个子区间，并行查找每个子区间内匹配target数组的元素索引，最后合并结果：

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.HashSet;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class ParallelArraySearch {
    private static class SearchTask extends RecursiveTask<ArrayList<Integer>> {
        private final byte[] data;
        private final Set<Byte> targetSet;
        private final int start;
        private final int end;

        public SearchTask(byte[] data, Set<Byte> targetSet, int start, int end) {
            this.data = data;
            this.targetSet = targetSet;
            this.start = start;
            this.end = end;
        }

        @Override
        protected ArrayList<Integer> compute() {
            // 任务足够小时，直接遍历查找
            if (end - start <= 1000) {
                ArrayList<Integer> result = new ArrayList<>();
                for (int i = start; i < end; i++) {
                    if (targetSet.contains(data[i])) {
                        result.add(i);
                    }
                }
                return result;
            } else {
                // 拆分任务为左右两个子任务
                int mid = (start + end) / 2;
                SearchTask leftTask = new SearchTask(data, targetSet, start, mid);
                SearchTask rightTask = new SearchTask(data, targetSet, mid, end);
                // 并行执行子任务
                leftTask.fork();
                ArrayList<Integer> rightResult = rightTask.compute();
                ArrayList<Integer> leftResult = leftTask.join();
                // 合并结果
                rightResult.addAll(leftResult);
                return rightResult;
            }
        }
    }

    public static List<Integer> parallelFindMatches(byte[] data, byte[] target) {
        Set<Byte> targetSet = new HashSet<>();
        for (byte b : target) {
            targetSet.add(b);
        }
        ForkJoinPool pool = new ForkJoinPool();
        return pool.invoke(new SearchTask(data, targetSet, 0, data.length));
    }
}

说明：这里设置的拆分阈值是1000，你可以根据数组大小调整；ForkJoinPool会自动利用多线程并行处理子任务，更适合超大数组的查找场景。

内容的提问来源于stack exchange，提问作者Ignasi Ferres