-
Notifications
You must be signed in to change notification settings - Fork 0
/
KLargest.java
366 lines (311 loc) · 9.2 KB
/
KLargest.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
package rsn170330.sp11;
import java.util.PriorityQueue;
import java.util.Random;
/**
* CS 5V81.001: Implementation of Data Structures and Algorithms
* Short Project SP11: Select Algorithm for K Largest Elements
* Team: SP11 33
* @author Rahul Nalawade (rsn170330)
* @author Pooja Srinivasan (pxs176230)
*
* Date: Nov 18, 2018
*/
public class KLargest {
public static Random random = new Random();
// larger the numTrials, better the average. But,
public static int numTrials = 3; // longer the run, and more the memory
public final static int T = 75;
// ------------------------------- MAIN ----------------------------------
public static void main(String[] args) {
int Million = 1000000;
int n = 1 * Million;
int choice = 1 + random.nextInt(2);
choice = 1;
if (args.length > 0) {
n = Integer.parseInt(args[0]);
}
if (args.length > 1) {
choice = Integer.parseInt(args[1]);
}
int k = n / 2;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i;
}
Timer timer = new Timer();
switch (choice) {
// K largest using Select Algorithm
case 1:
for (int i = 0; i < numTrials; i++) {
Shuffle.shuffle(arr);
quickSelect(arr, k);
}
break;
// K Largest using Min-Heap Algorithm
case 2:
for (int i = 0; i < numTrials; i++) {
Shuffle.shuffle(arr);
findKLargestPQ(arr, k);
}
break;
}
timer.end();
timer.scale(numTrials);
System.out.println("n: " + n);
if (choice == 1) {
System.out.println("Choice: " + choice +
": K Largest using Select");
}
else {
System.out.println("Choice: " + choice +
": K Largest using Min-Heap");
}
System.out.println(timer);
}
// ------------------------- Select Algorithm ----------------------------
/**
* Rearranges k largest elements in an array to the last.
* @param arr the input array
* @param k the 'k' elements.
*/
public static void quickSelect(int[] arr, int k) {
select(arr, 0, arr.length - 1, k);
// UNCOMMENT TO VERIFY OUTPUTS*
// int[] result = new int[k];
// int i = 0; while (i < k)
// { result[i] = arr[arr.length - 1 - i]; i++; }
// Arrays.sort(result);
// System.out.println(Arrays.toString(result));
}
/**
* Recursive method to rearrange k elements in the input[low..high]
* @param input the input array
* @param low the starting index
* @param high the last index
* @param k the 'k' elements to be rearranged
* @return index from which to last contains the k largest element
*/
private static int select(int[] input, int low, int high, int k) {
// total number of elements in array from index low to high
int n = high - low + 1;
if (n < T) {
// for n less than threshold, performs insertionSort
insertionSort(input, low, high) ;
}
// NOTE: the snapshot of the array at some point:
// [elements <= X] [X] [X < elements]
// left: no of elements which are <= X
// X: input[pivotIndex]
// right: no of elements which are > X + pivot*
// Runs randomized partition algorithm and returns index of pivot
// around which array is to be partitioned
int pivotIndex = randomizedPartition(input, low, high);
int right = high - pivotIndex + 1; // NOTE: + 1*
// When pivotIndex partitioned exact k elements,
if (right == k) { // same as right + 1 == k from notes
return pivotIndex;
}
// When right < k, find (k - right) elements in left
else if (right < k) {
// by changing high pointer and updated k value
return select(input, low, pivotIndex - 1, k - right);
}
// When k < right
else { // same as right >= k from notes
// update low <- (pivotIndex + 1) and call select in right side
return select(input, pivotIndex + 1, high, k);
}
}
/**
* Selects an index (pivot) uniformly in [low..high].
* @param arr the input array
* @param low indicates startIndex of array for the search
* @param high indicates startIndex of array for the search
* @return index of element around which array is partitioned
*/
private static int randomizedPartition(int[] arr, int low, int high) {
int n = high - low + 1; // total elements
// picks random index between [0 to n-1] and adds to low
int randomIndex = low + random.nextInt(n);
swap(arr, randomIndex, high); // swaps with high
// partition array with high value as pivot
int partitionIndex = partition(arr, low, high);
// returns its correct index in partitioned array
return partitionIndex;
}
private static void swap(int[] arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
/**
* Partitions a part of an array arr[low...high]
* around the pivot = arr[high]
*
* @param arr the input array
* @param low the start index
* @param high the end index
* @return pivot index around which array is partitioned
*/
private static int partition(int[] arr, int low, int high) {
int marker = low - 1;
int pivot = arr[high];
int currPtr = low;
// LI: arr[low...marker] ≤ pivot,
// arr[(marker + 1)...(currPtr − 1)] > pivot,
// arr[currPtr...(high - 1)] is unprocessed, arr[high] = x.
while (currPtr < high) {
if (arr[currPtr] <= pivot) {
marker++;
swap(arr, marker, currPtr);
}
currPtr++;
}
// Bringing pivot back to the middle
swap(arr, marker, high);
// arr[low...marker] ≤ pivot, arr[marker + 1] = pivot,
// arr[marker + 2...high] > pivot
return marker + 1;
}
// from class notes:
public static void insertionSort(int[] arr) {
insertionSort(arr, 0, arr.length - 1);
}
// Helper Insertion Sort: sorts an array arr[p...r]
private static void insertionSort(int[] arr, int p, int r) {
for (int i = p + 1; i <= r; i++) {
int key = arr[i];
int j = i - 1;
// Find place for arr[i] in sorted subarray arr[p...i-1].
while (j >= p && key < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// ----------------------------- Min Heap --------------------------------
/**
* Rearranges an array to place K largest elements in the end.
* @param arr the input array
* @param k the 'k' elements
*/
public static void findKLargestPQ(int[] arr, int k) {
// pq: minHeap to keep track of k largest elements
PriorityQueue<Integer> pq = new PriorityQueue<>();
int i = 0;
// adding first k elements in our minHeap
while (i < k) {
pq.add(arr[i++]);
}
i = k;
// Now, for each new element X = arr[i]:
while (i < arr.length) {
int x = arr[i++];
// when X > the smallest element in our priority queue
if (pq.peek().compareTo(x) < 0) {
pq.remove(); // remove the smallest element
pq.add(x); // add x
}
}
// UNCOMMENT TO VERIFY RESULTS*
// int[] result = new int[k];
// i = 0; while (i < k) { result[i++] = pq.poll(); }
// System.out.println(Arrays.toString(result));
}
/**
* Timer class for roughly calculating running time of programs
* @author rbk
* Usage: Timer timer = new Timer(); timer.start(); timer.end();
* System.out.println(timer); // output statistics
*/
public static class Timer {
long startTime, endTime, elapsedTime, memAvailable, memUsed;
boolean ready;
public Timer() {
startTime = System.currentTimeMillis();
ready = false;
}
public void start() {
startTime = System.currentTimeMillis();
ready = false;
}
public Timer end() {
endTime = System.currentTimeMillis();
elapsedTime = endTime - startTime;
memAvailable = Runtime.getRuntime().totalMemory();
memUsed = memAvailable - Runtime.getRuntime().freeMemory();
ready = true;
return this;
}
public long duration() {
if (!ready) {
end();
}
return elapsedTime;
}
public long memory() {
if (!ready) {
end();
}
return memUsed;
}
public void scale(int num) {
elapsedTime /= num;
}
public String toString() {
if (!ready) {
end();
}
return "Time: " + elapsedTime + " msec.\n" + "Memory: " +
(memUsed / 1048576)+ " MB / " + (memAvailable / 1048576) + " MB.";
}
}
/**
* Shuffle the elements of an array arr[from..to] randomly
* @author rbk : based on algorithm described in a book
*/
public static class Shuffle {
public static void shuffle(int[] arr) {
shuffle(arr, 0, arr.length - 1);
}
public static <T> void shuffle(T[] arr) {
shuffle(arr, 0, arr.length - 1);
}
public static void shuffle(int[] arr, int from, int to) {
int n = to - from + 1;
for (int i = 1; i < n; i++) {
int j = random.nextInt(i);
swap(arr, i + from, j + from);
}
}
public static <T> void shuffle(T[] arr, int from, int to) {
int n = to - from + 1;
Random random = new Random();
for (int i = 1; i < n; i++) {
int j = random.nextInt(i);
swap(arr, i + from, j + from);
}
}
static void swap(int[] arr, int x, int y) {
int tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
static <T> void swap(T[] arr, int x, int y) {
T tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
public static <T> void printArray(T[] arr, String message) {
printArray(arr, 0, arr.length - 1, message);
}
public static <T> void printArray(T[] arr, int from, int to, String message) {
System.out.print(message);
for (int i = from; i <= to; i++) {
System.out.print(" " + arr[i]);
}
System.out.println();
}
}
}