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

Как указал Даниэль, используйте параллелизм, разбивая эти огромные задачи на более мелкие.Ниже приведена одна реализация, использующая 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);
    }
}

Answer 3

Это немного зависит от абстрактности вашего курса.

Обычно можно сделать min одновременным безопасным: атомная ссылка может быть против задания.Лучше иметь два результата.

И, конечно, volatile, если переменная является общей.В обоих потоках переменная может быть локальной копией, которая может быть устаревшей.