Java并行查找数组的最小值

Question

在修改即将到来的考试时，我的解决方案是使用2个线程查找数组的最小值。

我必须为int创建一个包装器，以通过引用传递最小值。

你们有什么感想？

public class FindMin {

    public static void main(String[] args) {

        int[] data = {99,9,14,5,7,33,6,8,21,29,33,44,55,66,77,88,2, 3, 1};
        IntObj min = new IntObj(data[0]);

        Proc p1 = new Proc(0, (data.length/2)-1, data, min);
        Proc p2 = new Proc(data.length/2, data.length, data, min);

        p1.start();
        p2.start();

        try {
            p1.join();
            p2.join();
        }
        catch (InterruptedException e) {}
        System.out.println("Min value: "+min.value);
    }

}

class Proc extends Thread {
    int ub, lb;
    int[] data;
    IntObj min;

    public Proc(int lb, int ub, int[] data, IntObj _min) {
        this.ub = ub;
        this.lb = lb;
        this.data = data;
        min = _min;
    }
    public void run() {
        for(int i = lb; i < ub; i++) {
            compareSet(data[i]);
        }
    }
    public void compareSet(int val) {
        synchronized(min) {
            if(val < min.value) {
                min.value = val;
            }
        }
    }
}
class IntObj {
    int value;
    public IntObj(int _value) {
        value = _value;
    }
}

Answer 1

如果必须为每次比较进行同步，则使用两个线程的任何潜在收益都会因同步开销而得到补偿。让每个线程在其一半中找到最小值并将结果写入它们自己的输出变量。然后比较主线程中的两个结果。

如果最小值位于data[data.length/2-1]，您的代码将给出错误的结果。

Answer 2

这取决于你的课程的抽象性。

通常会使min并发安全：原子引用可能违反赋值。最好有两个结果。

如果变量是共享的话肯定是volatile。在两个线程中，变量可能是本地副本，可能是陈旧的。

Answer 3

正如丹尼尔指出的那样，通过将这些巨大的任务分解为更小的任务来利用并行性。下面是使用ForkJoinPool的一个实现。礼貌：Martin Mois

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class FindMin extends RecursiveTask<Integer> {
    private static final long serialVersionUID = 1L;
    private int[] numbers;
    private int startIndex;
    private int endIndex;
    public FindMin(int[] numbers, int startIndex, int endIndex) {
        this.numbers = numbers;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }
    @Override
    protected Integer compute() {
        int sliceLength = (endIndex - startIndex) + 1;
        if (sliceLength > 2) {
            FindMin lowerFindMin = new FindMin(numbers, startIndex, startIndex+ (sliceLength / 2) - 1);
            lowerFindMin.fork();
            FindMin upperFindMin = new FindMin(numbers, startIndex + (sliceLength / 2), endIndex);
            upperFindMin.fork();
            return Math.min(lowerFindMin.join(), upperFindMin.join());
        } else {
            return Math.min(numbers[startIndex], numbers[endIndex]);
        }
    }
    public static void main(String[] args) {
        int[] numbers = new int[100];
        Random random = new Random(System.currentTimeMillis());
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = random.nextInt(100);
        }

        ForkJoinPool pool = new ForkJoinPool(Runtime.getRuntime(). availableProcessors());
        Integer min = pool.invoke(new FindMin(numbers, 0, numbers.length - 1));
        System.out.println(min);
    }
}