+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

jspspikeFinished PMerge73bc9bb

master
3.0 KiB109 linesraw
1// UT-EID=jkj858
2// UT-EID=jbr2558
3
4import java.util.*;
5import java.util.concurrent.*;
6
7class Slice {
8    int[] arr;
9    int start;
10    int end;
11
12    public Slice(int[] arr, int start, int end) {
13        this.arr = arr;
14        this.start = start;
15        this.end = end;
16    }
17
18    @Override
19    public String toString() {
20        return Arrays.toString(Arrays.copyOfRange(arr, start, end));
21    }
22}
23
24public class PMerge extends RecursiveTask<int[]> {
25    Slice a;
26    Slice b;
27
28    public PMerge(Slice a, Slice b) {
29        this.a = a;
30        this.b = b;
31    }
32
33    public static void parallelMerge(int[] A, int[] B, int[] C,
34                                     int numThreads) {
35        ForkJoinPool pool = new ForkJoinPool(numThreads);
36        Slice a = new Slice(A, 0, A.length);
37        Slice b = new Slice(B, 0, B.length);
38
39        PMerge p = new PMerge(a, b);
40        int[] sorted = pool.invoke(p);
41
42        for (int i = 0; i < sorted.length; i++) {
43            C[sorted.length - 1 - i] = sorted[i];
44        }
45    }
46
47    @Override
48    protected int[] compute() {
49        int aLength = a.end - a.start;
50        int bLength = b.end - b.start;
51        //System.out.println(aLength + " " + bLength);
52
53        // Base case: if one of the arrays are empty or both arrays are of length 1 swap accordingly
54        if (aLength == 0) {
55            return Arrays.copyOfRange(b.arr, b.start, b.end);
56        } else if (bLength == 0) {
57            return Arrays.copyOfRange(a.arr, a.start, a.end);
58        } else if (aLength == 1 && bLength == 1) {
59            int[] c = new int[2];
60            if (a.arr[a.start] < b.arr[b.start]) {
61                c[0] = a.arr[a.start];
62                c[1] = b.arr[b.start];
63            } else {
64                c[0] = b.arr[b.start];
65                c[1] = a.arr[a.start];
66            }
67
68            return c;
69        }
70
71        // Always have larger array as a
72        if (bLength > aLength) {
73            Slice temp = a;
74            a = b;
75            b = temp;
76        }
77
78        int midIndex = a.start + aLength / 2;
79
80        // Find index for value of middle element in array b
81        int bIndex = Arrays.binarySearch(b.arr, b.start, b.end, a.arr[midIndex]);
82        if (bIndex < 0) bIndex = (bIndex * -1) - 1;
83
84        // Slice arrays into new segments and call next level
85        Slice a1 = new Slice(a.arr, a.start, midIndex);
86        Slice a2 = new Slice(a.arr, midIndex, a.end);
87
88        Slice b1 = new Slice(b.arr, b.start, bIndex);
89        Slice b2 = new Slice(b.arr, bIndex, b.end);
90
91        PMerge p1 = new PMerge(a1, b1);
92        p1.fork();
93        PMerge p2 = new PMerge(a2, b2);
94
95        int[] newB = p2.compute();
96        int[] newA = p1.join();
97
98        //System.out.println("A: " + Arrays.toString(newA));
99        //System.out.println("B: " + Arrays.toString(newB));
100
101        // Merge two sorted arrays
102        int[] c = Arrays.copyOf(newA, newA.length + newB.length);
103        for (int i = 0; i < newB.length; i++) {
104            c[i + newA.length] = newB[i];
105        }
106
107        return c;
108    }
109}