Arranging the elements of a list(with repeating elements) according to the frequency of occurrence

Question

What would be a good way to arrange the elements of a list(with repeating elements) according to the frequency of their occurrence in the list.

I need to use the top 5 frequently occurring items in the list.

I am thinking of using HashMap to count the elements' frequencies by incrementing the corresponding counter each time an element occurs & then doing HashMap iteration 5 times to find the highest freq. element over each iteration.

Answer 1

How about this approach ?

maintain a map in that holds count

public static Map  <Foo,Integer>;

---

class Foo implements Comparator<Foo>{  
      private Bar element;


      public int compare(Foo f1, Foo f2){
       return SomeClass.map.get(f1) - SomeClass.map.get(f2);
      }

    }

just update map with update in list.

Wrap the access to List forcefully with the addFooToList() , removeFooFromList() and encapsulate the map updation logic there.

Answer 2

You can use a Guava Multiset and order it by frequency

---

And about performance. Of course it depends on how many distinct values you have, but this test code took about a second on my machine. And I'd say that's reasonable enough for 10 M items:

Multiset<Integer> set = HashMultiset.create();
int amount = 10000000;
Random random = new Random();
for (int i = 0; i < amount; i++) {
    set.add(Integer.valueOf(random.nextInt(255)));
}
TreeSet<Entry<Integer>> sortedEntries = Sets.newTreeSet(
        new Comparator<Entry<Integer>>() {
    public int compare(Entry<Integer> a, Entry<Integer> b) {
        return Ints.compare(a.getCount(), b.getCount());
    }
});
Iterables.addAll(sortedEntries, set.entrySet());
for (Entry<Integer> entry : Iterables.limit(sortedEntries, 5)) {
    System.out.println(entry.getElement());
}