具有固定大小的Java PriorityQueue

Question

我正在计算一个algortihm的大量可能的结果组合.要对这些组合进行排序,我使用双倍值对它们进行评级,并将它们存储在PriorityQueue中.目前,该队列中有大约20万个项目,这几乎是内存集成.实际上,我只需要说出列表中所有项目中最好的1000或100.所以我开始问自己是否有办法在Java中拥有一个固定大小的优先级队列.我的行为应该是这样的:物品是否比已存储的物品更好？如果是,请将其插入相应的位置并抛出最小等级的元素.

有没有人有想法？再次感谢!

马尔科

Answer 1

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

还是我错过了解你的问题？

编辑:忘了提到为了这个工作你可能必须反转你的comparTo函数,因为它将丢弃每个周期具有最高优先级的那个.(如果a是"更好"b比较(a,b)应该返回一个正数.

保持最大数字的例子使用这样的东西:

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

Answer 2

MinMaxPriorityQueue,谷歌番石榴

确实存在一个用于维护队列的类,当添加超过集合最大大小的项时,比较项以查找要删除的项,从而创建空间:从版本8开始MinMaxPriorityQueue在Google Guava中找到.

EvictingQueue

顺便说一句,如果您只想删除最旧的元素而不对对象的值进行任何比较,那么Google Guava 15就获得了EvictingQueue该类.

Answer 3

Apache Lucene中有一个固定大小的优先级队列:http://lucene.apache.org/java/2_4_1/api/org/apache/lucene/util/PriorityQueue.html

它基于我的测试具有出色的性能.

Answer 4

更好的方法是更严格地调整队列中的内容，在程序运行时删除和追加队列。听起来在将某些项目添加到队列中之前会有一些空间来排除它们。可以说，这比重新发明轮子更简单。