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.
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.
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());
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With