Find top 20 values in descendent order of a big map

Question

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?

Do you really need to care if you are talking about only 20 elements ? — David Hofmann, Sep 04 '13 at 18:41
@DavidHofmann It looks like he's checking the top 20, but the map itself is much bigger. — Dennis Meng, Sep 04 '13 at 18:43
@DennisMeng yes the map is much bigger. I'm listing 20 entries in the map that have the top 20 values in descending order. — Prasana Venkat Ramesh, Sep 04 '13 at 19:07
@JimGarrison I can't sort it when creating the map. By sort do you mean to create a new map with entries in descending order of values? — Prasana Venkat Ramesh, Sep 04 '13 at 19:09
The map is as big a database. so it is not acceptable that I can do this in theta of n2 time. So please let me know how to go about this in a more efficient way — Prasana Venkat Ramesh, Sep 04 '13 at 19:11
@PrasanaVenkatRamesh No need for a second map, you can use a sorted collection (like TreeSet or whatever) — Dennis Meng, Sep 04 '13 at 19:11
And if you want the biggest 20, you can give a different comparator so that the TreeSet's iterator goes in reverse order. — Dennis Meng, Sep 04 '13 at 19:12

score 3 · Answer 1 · answered Sep 04 '13 at 19:18

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.

Create an array of size 20
Iterate through the map in arbitrary order
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)).

I can not use this as I'm looking at a map containing millions of entries. Creating a new map by copying millions of entries is ..... Not efficient — Prasana Venkat Ramesh, Sep 05 '13 at 01:11
The second algorithm that I sketched does not require creating a second map. — Andrew Eisenberg, Sep 05 '13 at 15:34

score 1 · Accepted Answer · answered Sep 04 '13 at 19:59

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());
}

Extremely instructive reply. +1 – blackbird014 Sep 04 '13 at 20:45 — blackbird014, Sep 04 '13 at 20:45

Find top 20 values in descendent order of a big map

2 Answers2