1 import java.util.ArrayList;
2 import java.util.Arrays;
3 import java.util.Collections;
4
5 /**
6 This program shows how a more efficient algorithm can greatly speed up
7 the task of finding the most frequent element in an array.
8 */
9 public class MostFrequent
10 {
11 public static void main(String[] args)
12 {
13 ArrayList<Integer> values = new ArrayList<Integer>();
14 int k = 300;
15 // Adds one times 1, two times 2, three times 3, ... , k times k
16 for (int i = 1; i <= k; i++)
17 {
18 for (int j = 1; j <= i; j++)
19 {
20 values.add(i);
21 }
22 }
23 // This method shuffles the array list randomly
24 Collections.shuffle(values);
25
26 StopWatch timer = new StopWatch();
27 int[] a = new int[values.size()];
28
29 // Copies the values into an array and runs the first version
30 // of the algorithm
31 for (int i = 0; i < a.length; i++) { a[i] = values.get(i); }
32 timer.start();
33 int result = mostFrequent1(a);
34 timer.stop();
35 System.out.println(result);
36 System.out.println("Expected: " + k);
37 System.out.println("Elapsed time: "
38 + timer.getElapsedTime() + " milliseconds");
39
40 // Copies the same values and runs the second version
41 for (int i = 0; i < a.length; i++) { a[i] = values.get(i); }
42 timer.reset();
43 timer.start();
44 result = mostFrequent2(a);
45 timer.stop();
46 System.out.println(result);
47 System.out.println("Expected: " + k);
48 System.out.println("Elapsed time: "
49 + timer.getElapsedTime() + " milliseconds");
50 }
51
52 /**
53 Returns the most frequently occurring value in an array.
54 @param a an array
55 @return the most frequently occuring value in a
56 */
57 public static int mostFrequent1(int[] a)
58 {
59 int[] counts = new int[a.length];
60 for (int i = 0; i < a.length; i++) // O(n*n)
61 {
62 counts[i] = count(a, a[i]); // O(n) in each iteration
63 }
64
65 int highestFrequency = max(counts); // O(n)
66 int highestFrequencyIndex = search(counts, highestFrequency); // O(n)
67 return a[highestFrequencyIndex];
68 }
69
70 /**
71 Returns the most frequently occurring value in an array.
72 @param a an array
73 @return the most frequently occuring value in a
74 */
75 public static int mostFrequent2(int[] a)
76 {
77 Arrays.sort(a); // O(n log(n))
78 int[] counts = new int[a.length];
79
80 int count = 0;
81 for (int i = 0; i < a.length; i++) // O(n)
82 {
83 count++;
84 if (i == a.length - 1 || a[i] != a[i + 1])
85 {
86 counts[i] = count;
87 count = 0;
88 }
89 }
90
91 int highestFrequency = max(counts); // O(n)
92 int highestFrequencyIndex = search(counts, highestFrequency); // O(n)
93 return a[highestFrequencyIndex];
94 }
95
96 /**
97 Counts how often a value occurs in an array.
98 @param a the array
99 @param value the value to count
100 @return the number of occurrences of value in a
101 */
102 public static int count(int[] a, int value)
103 {
104 int count = 0;
105 for (int i = 0; i < a.length; i++)
106 {
107 if (a[i] == value) { count++; }
108 }
109 return count;
110 }
111
112 /**
113 Computes the largest value of an array.
114 @param a the array
115 @return the largest value in a
116 */
117 public static int max(int[] values)
118 {
119 int largest = values[0];
120 for (int i = 1; i < values.length; i++)
121 {
122 if (values[i] > largest)
123 {
124 largest = values[i];
125 }
126 }
127 return largest;
128 }
129
130 /**
131 Finds a value in an array, using the linear search
132 algorithm.
133 @param a the array to search
134 @param value the value to find
135 @return the index at which the value occurs, or -1
136 if it does not occur in the array
137 */
138 public static int search(int[] a, int value)
139 {
140 for (int i = 0; i < a.length; i++)
141 {
142 if (a[i] == value) { return i; }
143 }
144 return -1;
145 }
146 }