Created
March 10, 2024 17:42
-
-
Save camilajenny/daf6c66152df54fa6d30088bb0464079 to your computer and use it in GitHub Desktop.
Divide and conquer summing of an array using Java fork/join
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.concurrent.RecursiveTask; | |
public class ArraySumCalculator extends RecursiveTask<Long> { | |
private static final int THRESHOLD = 1000; // Threshold for splitting the array | |
private final int[] array; | |
private final int start; | |
private final int end; | |
public ArraySumCalculator(int[] array, int start, int end) { | |
this.array = array; | |
this.start = start; | |
this.end = end; | |
} | |
@Override | |
protected Long compute() { | |
int length = end - start + 1; | |
if (length <= THRESHOLD) { | |
// If the array size is smaller than the threshold, compute the sum sequentially | |
long sum = 0; | |
for (int i = start; i <= end; i++) { | |
sum += array[i]; | |
} | |
return sum; | |
} else { | |
// Split the array into two halves | |
int mid = start + (end - start) / 2; | |
ArraySumCalculator leftTask = new ArraySumCalculator(array, start, mid); | |
ArraySumCalculator rightTask = new ArraySumCalculator(array, mid + 1, end); | |
// Fork the tasks to execute concurrently | |
leftTask.fork(); | |
long rightResult = rightTask.compute(); // Compute the right subarray sum synchronously | |
long leftResult = leftTask.join(); // Wait for the left subarray sum | |
// Combine the results | |
return leftResult + rightResult; | |
} | |
} | |
public static void main(String[] args) { | |
int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; | |
ArraySumCalculator calculator = new ArraySumCalculator(array, 0, array.length - 1); | |
long result = calculator.compute(); | |
System.out.println("Sum of elements: " + result); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment