MostFrequent.java.html

  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  }