Parallel Average
123456789101112131415161718192021222324252627282930313233343536373839404142
import java.util.Arrays;
class Main {
public static double reduce (int[] N) {
if (N.length == 2) {
return (double)(N[0] + N[1]) / 2;
} else if (N.length == 3) {
return (double)(N[0] + N[1] + N[2]) / 3;
}
int[] p1 = Arrays.copyOfRange(N, 0, N.length / 2);
int[] p2 = Arrays.copyOfRange(N, N.length / 2, N.length);
return (double)(reduce(p1) + reduce(p2)) / 2;
}
public static void main(String[] args) {
int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8};
System.out.println(reduce(a));
}
}
/*
so if you have a list like this:
[1, 2, 3, 4, 5, 6, 7, 8]
it goes
1. reduce([1, 2, 3, 4, 5, 6, 7, 8])
2. = reduce([1, 2, 3, 4]) + reduce([5, 6, 7, 8])
3. = (reduce([1, 2]) + reduce([3, 4])) + (reduce([5, 6]) + reduce([7, 8]))
so reduce() is called n - 1 times, but there are three steps
if each step could be computed in parallel, then this would run in O(logN) time
*/
Java
INFO