Java PriorityQueue with fixed size

Question

I am calculating a large number of possible resulting combinations of an algortihm. To sort this combinations I rate them with a double value und store them in PriorityQueue. Currently, there are about 200k items in that queue which is pretty much memory intesive. Acutally, I only need lets say the best 1000 or 100 of all items in the list. So I just started to ask myself if there is a way to have a priority queue with a fixed size in Java. I should behave like this: Is the item better than one of the allready stored? If yes, insert it to the according position and throw the element with the least rating away.

Does anyone have an idea? Thanks very much again!

Marco

Answer 1

que.add(d); if (que.size() > YOUR_LIMIT)      que.poll(); 

or did I missunderstand your question?

edit: forgot to mention that for this to work you probably have to invert your comparTo function since it will throw away the one with highest priority each cycle. (if a is "better" b compare (a, b) should return a positvie number.

example to keep the biggest numbers use something like this:

public int compare(Double first, Double second) {             // keep the biggest values             return first > second ? 1 : -1;         } 

Answer 2

MinMaxPriorityQueue, Google Guava

There is indeed a class for maintaining a queue that, when adding an item that would exceed the maximum size of the collection, compares the items to find an item to delete and thereby create room: MinMaxPriorityQueue found in Google Guava as of version 8.

EvictingQueue

By the way, if you merely want deleting the oldest element without doing any comparison of the objects’ values, Google Guava 15 gained the EvictingQueue class.

Answer 3

There is a fixed size priority queue in Apache Lucene: http://lucene.apache.org/java/2_4_1/api/org/apache/lucene/util/PriorityQueue.html

It has excellent performance based on my tests.

Answer 4

Use SortedSet:

SortedSet<Item> items = new TreeSet<Item>(new Comparator<Item>(...));
...
void addItem(Item newItem) {
    if (items.size() > 100) {
         Item lowest = items.first();
         if (newItem.greaterThan(lowest)) {
             items.remove(lowest);
         }
    }

    items.add(newItem);   
}