CODEWITHSUNDEEP
javaperformancedictionary
Eleonora Ciceri
Eleonora Ciceri

Reputation: 1798

Retrieve N most relevant objects in Java TreeMap

According to this question I have ordered a Java Map, as follows:

ValueComparator bvc =  new ValueComparator(originalMap);
Map<String,Integer> sortedMap = new TreeMap<String,Integer>(bvc);
sortedMap.putAll(originalMap);

Now, I would like to extract the K most relevant values from the map, in top-K fashion. Is there a highly efficient way of doing it without iterating through the map?

P.S., some similar questions (e.g., this) ask for a solution to the top-1 retrieval problem.

Upvotes: 1

Views: 84

Answers (1)

chiastic-security
chiastic-security

Reputation: 20520

No, not if you use a Map. You'd have to iterate over it.

Have you considered using a PriorityQueue? It's Java's implementation of a heap. It has efficient operations for insertion of arbitrary elements and for removal of the "minimum". You might think about doing this here. Instead of a Map, you could put them into a PriorityQueue ordered by relevance, with the most relevant as the root. Then, to extract the K most relevant, you'd just pop K elements from the PriorityQueue.

If you need the map-like property (mapping from String to Integer), then you could write a class that internally keeps everything in both a PriorityQueue and a HashMap. When you insert, you insert into both; when you remove the minimal element, you pop from the PriorityQueue, and that then tells you which element you also need to remove from your HashMap. This will still give you log-time inserts and min-removals.

Upvotes: 4

Related Questions