下面递归任务的实现是否正确？

Question

我开始了解递归任务和递归操作的实现。根据我的理解和一些 java 文档，我想出了下面的代码来将数组中的所有数字相加。

我需要帮助来纠正这个问题，请帮我指出我哪里做错了。

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

public class ForkJoinPoolTest {

public static void main(String[] args) {

    ForkJoinPool pool = new ForkJoinPool(4);
    long[] numbers = {1,2,3,4,5,6,7,8,9};
    AdditionTask newTask = new AdditionTask(numbers, 0, numbers.length -1 );
    ForkJoinTask<Long> submit = pool.submit(newTask);
    System.out.println(submit.join());
    
}
}

class AdditionTask extends RecursiveTask<Long> {

long[] numbers;
int start;
int end;

public AdditionTask(long[] numbers, int start, int end) {
    this.numbers = numbers;
    this.start = start;
    this.end = end;
}

@Override
protected Long compute() {

    if ((end - start) > 2) {

        int length = numbers.length;
        int mid = (length % 2 == 0) ? length / 2 : (length - 1) / 2;
        AdditionTask leftSide = new AdditionTask(numbers, 0, mid);

        leftSide.fork();

        AdditionTask rightSide = new AdditionTask(numbers, mid+1, length-1);
        return rightSide.compute() + leftSide.join();

    } else {
        return numbers[0] + numbers[1];
    }


}
}

新代码[已修复] 这是我修复的代码，似乎只适用于小数组。在下面的示例中，数组大小为 10000，总和是错误的。为什么会算错？

import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

public class ForkJoinPoolTest {

    public static void main(String[] args) {

        Random r = new Random();
        int low = 10000;
        int high = 100000;

        int size = 100000;

        long[] numbers = new long[size];
        int sum = 0;
        for (int i = 0; i < size; i++) {
            int n = r.nextInt(high - low) + low;
            numbers[i] = n;
            sum += numbers[i];
        }

        long s = System.currentTimeMillis();
        ForkJoinPool pool = new ForkJoinPool(1);
        AdditionTask newTask = new AdditionTask(numbers, 0, numbers.length-1);
        ForkJoinTask<Long> submit = pool.submit(newTask);
        System.out.println("Expected Answer: " + sum + ", Actual: " + submit.join());
        long e = System.currentTimeMillis();
        System.out.println("Total time taken: " + (e - s) + " ms in parallel Operation");




        long s2 = System.currentTimeMillis();
        System.out.println("Started: " + s2);

        int manualSum = 0;
        for (long number : numbers) {
            manualSum += number;
        }

        System.out.println("Expected Answer: " + sum + ", Actual: " + manualSum);
        long e2 = System.currentTimeMillis();
        System.out.println("Ended: " + e2);
        System.out.println("Total time taken: " + (e2 - s2) + " ms in sequential Operation");
    }
}

class AdditionTask extends RecursiveTask<Long> {

    long[] numbers;
    int start;
    int end;

    public AdditionTask(long[] numbers, int start, int end) {
        this.numbers = numbers;
        this.start = start;
        this.end = end;
    }

    @Override
    protected Long compute() {


        int length = (start == 0) ? end +1 : (end - (start - 1));

        if (length > 2) {

            int mid = (length % 2 == 0) ? length / 2 : (length - 1) / 2;
            
            AdditionTask leftSide = new AdditionTask(numbers, start, (start+mid));
            leftSide.fork();
            
            AdditionTask rightSide = new AdditionTask(numbers, (start+mid)+1, end);

            Long rightSideLong = rightSide.compute();

            Long leftSideLong = leftSide.join();
            Long total = rightSideLong + leftSideLong;
            
            return total;

        } else {

            if (start == end) {
                return numbers[start];
            }
            return numbers[start] + numbers[end];

        }

    }
}

Answer 1

你的并行计算的第二个版本是正确的。但是代码中的两个 non-parallel 计算都被破坏了，因为它们使用 int 作为它们的总和，这将溢出大型数组。当您修复它们时，也使用 long，它们将产生与您的并行计算相同的结果。

不过，还有一些地方需要改进。首先，你应该摆脱那些条件：

int length = (start == 0) ? end +1 : (end - (start - 1));

和

int mid = (length % 2 == 0) ? length / 2 : (length - 1) / 2;

与更简单的

相比，它们没有任何优势

int length = end - (start - 1); // or end - start + 1

和

int mid = length / 2;

那么，一个高效的并行处理应该不是尽可能的分解，而是结合实际可实现的并行度。您可以使用 getSurplusQueuedTaskCount() 作为

@Override
protected Long compute() {
    int length = end - (start - 1);
    // only split when benefit from parallel processing is likely
    if (length > 2 && getSurplusQueuedTaskCount() < 2) {
        int mid = length / 2;

        AdditionTask leftSide = new AdditionTask(numbers, start, (start+mid));
        leftSide.fork();

        AdditionTask rightSide = new AdditionTask(numbers, (start+mid)+1, end);

        Long rightSideLong = rightSide.compute();

        // do in this thread if no worker thread has picked it up yet
        Long leftSideLong = leftSide.tryUnfork()? leftSide.compute(): leftSide.join();
        Long total = rightSideLong + leftSideLong;

        return total;
    } else { // do sequential
        long sum = 0;
        for(int ix = start; ix <= end; ix++) sum += numbers[ix];
        return sum;
    }
}

下面递归任务的实现是否正确？

is the implementation of the Recursive Task below correct?

java

concurrency

divide-and-conquer

forkjoinpool

recursivetask