具有固定大小的Java PriorityQueue

Question

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

有人有想法吗？再次非常感谢！

马可

Answer 1

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;
        }

Answer 2

MinMaxPriorityQueue，Google Guava

Answer 3

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

Answer 4

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

Answer 5

使用SortedSet：

Answer 6

仅当队列中的最小元素小于当前元素（在您的情况下，其评级比当前元素差）时，仅

List<Double> list = new ArrayList<Double>();
...
list.add(newOutput);
Collections.sort(list);
list = list.subList(0, 1000);

。

Answer 7

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