数组中的可分搜索

Question

如标题所示，如何将 table 中的搜索拆分为多个线程（例如 4），以便每个线程在数组的不同部分查找 min 和 max。

Answer 1

正如@andreas 所告知的那样，您应该首先瞄准使用内置的 stream().parallel()。为此，初始化一个具有随机值的空数组以用于测试目的。然后使用 IntStream 这是我试过的方法。

    public int min() {
        return IntStream.of(intData)
                .parallel()
                .min()
                .orElseThrow(() -> new RuntimeException("Empty Stream while calculating min value"));
    }

类似地查找最大元素使用max()

要使用多线程，基于分区创建固定线程池，然后对实际数据进行分区，然后将分区传递给每个线程。这是我的做法。

public void findMinMaxUsingFutures() throws InterruptedException, ExecutionException {
        final ExecutorService executorService = Executors.newFixedThreadPool(totalPartitions);
        final List<Future<MinMax>> futures = new ArrayList<>();
        final Collection<List<Integer>> partitions = partitionedData();
        for (List<Integer> items : partitions) {
            futures.add(executorService.submit(new MinMaxCalculator(items)));
        }

        final List<MinMax> minMaxes = new ArrayList<>();
        for (Future<MinMax> minMaxFuture : futures) {
            final MinMax minMax = minMaxFuture.get();
            minMaxes.add(minMax);
        }
        futures.clear();
        final List<Integer> allMins = minMaxes.stream().map(minMax -> minMax.min).collect(Collectors.toList());
        final List<Integer> allMax = minMaxes.stream().map(minMax -> minMax.max).collect(Collectors.toList());
        allMax.addAll(allMins);
        final List<Integer> leftOvers = new ArrayList<>();
        leftOvers.addAll(allMax);
        leftOvers.addAll(allMax);
        Future<MinMax> minMaxFuture = executorService.submit(new MinMaxCalculator(leftOvers));
        System.out.println(minMaxFuture.get());
    }

source code

Answer 2

这是一种只使用普通 Thread.

的方法

代码已通过 Java 7 和 Java 15 测试。

// Create array to be searched, filled with random numbers 0-999
final int[] arrayToSearch = new int[20];
Random rnd = new Random();
for (int i = 0; i < arrayToSearch.length; i++)
    arrayToSearch[i] = rnd.nextInt(1000);
System.out.println(Arrays.toString(arrayToSearch));

// Prepare threads and intermediate result collectors
final int PARTITIONS = 4;
Thread[] threads = new Thread[PARTITIONS];
final int[] partitionMin = new int[PARTITIONS];
final int[] partitionMax = new int[PARTITIONS];
for (int i = 0; i < PARTITIONS; i++) {
    final int partition = i;
    threads[i] = new Thread(new Runnable() {
        @Override
        public void run() {
            // Find min/max values in sub-array
            int from = arrayToSearch.length * partition / PARTITIONS;
            int to = arrayToSearch.length * (partition + 1) / PARTITIONS;
            int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            for (int j = from; j < to; j++) {
                min = Math.min(min, arrayToSearch[j]);
                max = Math.max(max, arrayToSearch[j]);
            }
            partitionMin[partition] = min;
            partitionMax[partition] = max;
            System.out.println("partition " + partition +
                               ": from=" + from + ", to=" + to +
                               ", min=" + min + ", max=" + max);
        }
    });
}

// Start threads and wait for them to complete
for (int i = 0; i < PARTITIONS; i++) {
    threads[i].start();
}
for (int i = 0; i < PARTITIONS; i++) {
    try {
        threads[i].join();
    } catch (@SuppressWarnings("unused") InterruptedException ignored) {
        // Ignore
    }
}
System.out.println("partitionMin=" + Arrays.toString(partitionMin) +
                 ", partitionMax=" + Arrays.toString(partitionMax));

// Process partition intermediate results
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int i = 0; i < PARTITIONS; i++) {
    min = Math.min(min, partitionMin[i]);
    max = Math.max(max, partitionMax[i]);
}
System.out.println("Result: min=" + min + ", max=" + max);

示例输出

[599, 65, 712, 912, 940, 372, 922, 957, 534, 362, 76, 453, 362, 993, 449, 515, 690, 730, 96, 355]
partition 0: from=0, to=5, min=65, max=940
partition 2: from=10, to=15, min=76, max=993
partition 3: from=15, to=20, min=96, max=730
partition 1: from=5, to=10, min=362, max=957
partitionMin=[65, 362, 76, 96], partitionMax=[940, 957, 993, 730]
Result: min=65, max=993

数组中的可分搜索

divisible searches in the array

arrays

stream