Java并行化组合

Question

我正在尝试并行处理一个组合优化问题。基本上我是想把每个大小为k (n选k)的组合过一遍，看看这个组合是不是最好的。我写了一个可以工作的顺序版本(下面是java代码):

public int bestCombo(int[] al, int[] data, int start, int end, int index, int k) {
    if (index == k) {
        // you have unique combination
        return calculateBestCombination(data);
    } else {
        int best = 0;
        for (int i = start; i <= end && end-i+1 >= k-index; i ++){
            data[index] = al[i];
            int temp = bestCombo(al, data, i+1, end, index+1, k);
            if (best < temp) {
              best = temp
            }
        }
        return best;
    }
}

所以我的代码在递归树的叶子处进行计算，在叶子处，我将有一个唯一的大小k组合，非常简单。现在我将其转换为fork/连接代码，但我没有得到正确的解决方案。这是我在java代码中的fork/连接代码：

public class ParallelizeCombo extends RecursiveTask<MintSolution> {
    private int[] array;
    private int[] data;
    private int start;
    private int end;
    private int index;
    private int k;

    public ParallelizeCombo(int[] arr, int[] data, int start, int end, int index, int k) {
        super();
        this.array = arr;
        this.data = data;
        this.start = start;
        this.end = end;
        this.index = index;
        this.k = k;
    }

    @Override
    protected int compute() {
        // base case, we have reached the end of the combo
        if (this.index == k) {
            return calculateBestCombination(this.data);
        } else {
            List<ParallelizeCombo> subtasks = new ArrayList();
            for (int i = this.start; i <= this.end && this.end-i + 1 >= this.r-this.index; i ++) {
                this.data[this.index] = this.array[i];
                ParallelizeCombo pc = new ParallelizeCombo(this.array, this.data, i+1, this.end, this.index+1, this.k);
                subtasks.add(pc);
            }
            // run subtasks
            for (ParallelizeCombo subtask: subtasks) {
                subtask.fork();
            }
            int best = 0;
            // join the subtasks
            for (ParallelizeCombo subtask: subtasks) {
                int temp = subtask.join();
                if (best < int) {
                    best = int
                }
            }
            return best;
        }
    }
}

我很困惑，因为代码基本相同。唯一的区别是，在fork/join中的for循环中，我在多线程中运行它。然而，我得到的解决方案完全不同，fork/join解决方案非常错误。有人知道为什么吗？

Answer 1

好吧，我想通了。我是个白痴...问题如下：

public ParallelizeCombo(int[] arr, int[] data, int start, int end, int index, int k) {
    super();
    this.array = arr;
    this.data = data;
    this.start = start;
    this.end = end;
    this.index = index;
    this.k = k;
}

在这里，this.data不是创建新数据，而只是指向数据（通过引用）。因此，当您在特定时间对数据计算BestCombination时，它可能不是您认为的组合（其他线程可能已经更改了数据的值）。