求和问题的并行实现返回意想不到的结果

Question

我想尝试一种不同的方法，所以我混合了合并排序算法的并行实现，这是一种分治方法，与典型的数字相加方法。

代码如下：

class SequentialSum {
    public static long sum(int[] numbers, int low, int high) {
        long total = 0;
        for (int i = low; i <= high; i++) total += numbers[i];
        return total;
    }
}

class ParallelSum {

    private static final AtomicLong finalSum = new AtomicLong(0);

    public static void parallelSum(int[] numbers, int low, int high, int threads) {

        if (threads <= 1) finalSum.addAndGet(SequentialSum.sum(numbers, low, high));

        int middle = (low + high) / 2;
        Thread left = new Thread(() -> parallelSum(numbers, low, middle, threads / 2));
        Thread right = new Thread(() -> parallelSum(numbers, middle + 1, high, threads / 2));

        left.start();
        right.start();
    }

    public static long getOutput() {
        return finalSum.get();
    }
}

public class _3_ParallelSummation {

    private static final int NUM_OF_THREADS = Runtime.getRuntime().availableProcessors();
    private static final Random random = new Random();
    private static final int ARRAY_LENGTH = 100_000_000;

    public static void main(String[] args) throws InterruptedException {

        int[] numbers = new int[ARRAY_LENGTH];
        for (int i = 0; i < ARRAY_LENGTH; i++) numbers[i] = random.nextInt(10);


        long t1 = System.currentTimeMillis();
        long sum = SequentialSum.sum(numbers, 0, ARRAY_LENGTH - 1);
        long t2 = System.currentTimeMillis();
        System.out.printf("Sum is: %d, completed in %d ms\n", sum, t2 - t1);

        t1 = System.currentTimeMillis();
        ParallelSum.parallelSum(numbers, 0, ARRAY_LENGTH - 1, NUM_OF_THREADS);
        t2 = System.currentTimeMillis();
        Thread.sleep(1000);
        System.out.printf("Sum is: %d, completed in %d ms\n", ParallelSum.getOutput(), t2 - t1);
    }
}

我得到了意想不到的结果：

Sum is: 449963052, completed in 56 ms
Sum is: 3950670566, completed in 3 ms
[28.597s][warning][os,thread] Failed to start thread - _beginthreadex failed (EACCES) for attributes: stacksize: default, flags: CREATE_SUSPENDED STACK_SIZE_PARAM_IS.
[28.598s][warning][os,thread] Failed to start thread - _beginthreadex failed (EACCES) for attributes: stacksize: default, flags: CREATE_SUSPENDED STACK_SIZE_PARAM_IS.
[28.598s][warning][os,thread] Failed to start thread - _beginthreadex failed (EACCES) for attributes: stacksize: default, flags: CREATE_SUSPENDED STACK_SIZE_PARAM_IS.
[28.601s][warning][os,thread] Failed to start thread - _beginthreadex failed (EACCES) for attributes: stacksize: default, flags: CREATE_SUSPENDED STACK_SIZE_PARAM_IS.

我在代码中犯了什么错误？还是我的思维方式不对？

Answer 1

合并排序中缺少else块

if (threads <= 1) { 
            finalSum.addAndGet(SequentialSum.sum(numbers, low, high));
        }else {
        int middle = (low + high) / 2;
        Thread left = new Thread(() -> parallelSum(numbers, low, middle, threads / 2));
        Thread right = new Thread(() -> parallelSum(numbers, middle + 1, high, threads / 2));
        left.start();
        right.start();
}

添加else块将修复代码。

您还可以使用join()删除固定的睡眠时间

left.join();
right.join();