具有固定大小的Java PriorityQueue

问题描述 投票:34回答:7

我正在计算大量可能的算法组合。为了对这些组合进行排序,我使用双值对它们进行评分,然后将其存储在PriorityQueue中。当前,该队列中大约有20万个项目,这在内存方面非常重要。因此,我只需要说列表中所有项目中最好的1000或100。因此,我刚刚开始问自己,是否有办法在Java中使用固定大小的优先级队列。我应该表现得像这样:该物品是否比已经存储的物品中的一件更好?如果是,则将其插入相应的位置,然后将额定值最小的元素扔掉。

有人有想法吗?再次非常感谢!

马可

java list size priority-queue
7个回答
29
投票
que.add(d);
if (que.size() > YOUR_LIMIT)
     que.poll();

或者我是否误解了您的问题?

编辑:忘了提及,要实现此目的,您可能必须反转您的comparTo函数,因为它会丢弃每个循环中具有最高优先级的函数。 (如果a是“更好”,则b compare(a,b)应该返回一个正数。)

保持最大数字的示例使用如下所示:

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

12
投票

MinMaxPriorityQueue,Google Guava


5
投票

Apache Lucene中有一个固定大小的优先级队列:EvictingQueue


2
投票

每次添加项目时都保持前1000名看起来很自然,但是EvictingQueue并没有提供任何功能来优雅地实现这一目标。也许您可以在方法中执行以下操作,而不是使用http://lucene.apache.org/java/2_4_1/api/org/apache/lucene/util/PriorityQueue.html


2
投票

使用SortedSet:


2
投票

仅当队列中的最小元素小于当前元素(在您的情况下,其评级比当前元素差)时,仅List<Double> list = new ArrayList<Double>(); ... list.add(newOutput); Collections.sort(list); list = list.subList(0, 1000);


0
投票

更好的方法是更加严格地管理队列中的内容,并在程序运行时将其删除并附加到队列中。听起来好像有一定的空间可以排除某些项目,然后再将它们添加到队列中。可以说,这比重新发明轮子要简单。

© www.soinside.com 2019 - 2024. All rights reserved.