CODEWITHSUNDEEP
java
Prasana Venkat Ramesh
Prasana Venkat Ramesh

Reputation: 67

Find top 20 values in descendent order of a big map

here's m code

Integer max = Collections.max(map.values());
int count = 20;
while(count>0)
{
    for (Map.Entry<String, Integer> e : map.entrySet())
        if(e.getValue() == max)
        {
            System.out.println(e.getKey() + "occurs" + e.getValue() + "times");
            count--;
        }
        max--;
}

This program runs in theta of n square time complexity. Is there a better way to display entries in the max which have top 20 maximum values in descending order?

Upvotes: 2

Views: 260

Answers (2)

Louis Wasserman
Louis Wasserman

Reputation: 198211

Efficient, O(n log 20), correct in all cases, and doesn't use anything outside the JDK:

PriorityQueue<Map.Entry<String, Integer>> pq = 
  new PriorityQueue<Map.Entry<String, Integer>>(
    20, new Comparator<Map.Entry<String, Integer>() {
      @Override public int compare(
          Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) {
        return e2.getValue().compareTo(e1.getValue());
        // not the other way around, since we want the maximum values
      }
    });
for (Map.Entry<String, Integer> entry : map.entrySet()) {
  pq.add(entry);
  if (pq.size() > 20) {
    pq.remove();
  }
}
while (!pq.isEmpty()) {
  Map.Entry<String, Integer> entry = pq.remove();
  System.out.println("Key: " + entry.getKey() + " Value: " + entry.getValue());
}

Upvotes: 1

Andrew Eisenberg
Andrew Eisenberg

Reputation: 28757

In general, I would do the simplest thing possible unless you have evidence that the performance is bad. So, as a first go, I would simply sort the entire map, and then iterate through the first 20 elements, something like this:

Map<?,?> mySortedMap = new TreeMap<?,?>(map);
Iterator<Entry<?,?>> entries = mySortedMap.entrySet().iterator();
for (int i = 0; i<20; i++) {
  System.out.println(entries.next());
}

Don't prematurely optimize. Now, if you do have a performance problem, then things get interesting. I'll sketch the algorithm that I'd use.

  1. Create an array of size 20
  2. Iterate through the map in arbitrary order
  3. If the next value of the map is in the top 20 seen so far, then do an insertion into the array at the appropriate location.

This algorithm has a much better worst and best case running time (theta(n)).

Upvotes: 3

Related Questions