具有固定大小的 Java PriorityQueue
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1846225/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java PriorityQueue with fixed size
提问by Marco
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.
我正在计算大量可能的算法组合。为了对这些组合进行排序，我用双倍值对它们进行评分并将它们存储在 PriorityQueue 中。目前，该队列中大约有 20 万个项目，这对内存来说非常重要。实际上，我只需要说列表中所有项目中最好的 1000 或 100。所以我刚开始问自己是否有办法在 Java 中拥有一个固定大小的优先级队列。我应该这样做：该项目是否比已存储的项目更好？如果是，将其插入相应的位置，然后将评分最低的元素扔掉。
Does anyone have an idea? Thanks very much again!
有没有人有想法？再次非常感谢！
Marco
马可
回答by Gordon
A better approach would be to more tightly moderate what goes on the queue, removing and appending to it as the program runs. It sounds like there would be some room to exclude some the items before you add them on the queue. It would be simpler than reinventing the wheel so to speak.
更好的方法是更严格地调节队列中的内容，在程序运行时删除并附加到队列中。听起来在将某些项目添加到队列之前会有一些空间来排除它们。可以这么说，这比重新发明轮子更简单。
回答by vahidg
It seems natural to just keep the top 1000 each time you add an item, but the PriorityQueuedoesn't offer anything to achieve that gracefully. Maybe you can, instead of using a PriorityQueue, do something like this in a method:
每次添加项目时只保持前 1000 名似乎很自然，但是这PriorityQueue并没有提供任何东西来优雅地实现这一目标。也许你可以，而不是使用 a PriorityQueue，在一个方法中做这样的事情：
List<Double> list = new ArrayList<Double>();
...
list.add(newOutput);
Collections.sort(list);
list = list.subList(0, 1000);
回答by Victor Sorokin
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);
}
回答by gustafc
Just poll()the queue if its least element is less than (in your case, has worse rating than) the current element.
只是poll()如果队列的最小元素小于（在你的情况，有更坏的评价比）当前元素。
static <V extends Comparable<? super V>>
PriorityQueue<V> nbest(int n, Iterable<V> valueGenerator) {
PriorityQueue<V> values = new PriorityQueue<V>();
for (V value : valueGenerator) {
if (values.size() == n && value.compareTo(values.peek()) > 0)
values.poll(); // remove least element, current is better
if (values.size() < n) // we removed one or haven't filled up, so add
values.add(value);
}
return values;
}
This assumes that you have some sort of combination class that implements Comparablethat compares combinations on their rating.
这假设您有某种组合类可以实现Comparable对组合的评级进行比较。
Edit:Just to clarify, the Iterablein my example doesn't need to be pre-populated. For example, here's an Iterable<Integer>that will give you all natural numbers an intcan represent:
编辑：只是为了澄清，Iterable在我的例子中不需要预先填充。例如，这里有Iterable<Integer>一个int可以表示所有自然数的函数：
Iterable<Integer> naturals = new Iterable<Integer>() {
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
int current = 0;
@Override
public boolean hasNext() {
return current >= 0;
}
@Override
public Integer next() {
return current++;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
};
Memory consumption is very modest, as you can see - for over 2 billion values, you need two objects (the Iterableand the Iterator) plus one int.
正如您所见，内存消耗非常适中 - 对于超过 20 亿个值，您需要两个对象（theIterable和 the Iterator）加上一个int。
You can of course rather easily adapt my code so it doesn't use an Iterable- I just used it because it's an elegant way to represent a sequence (also, I've been doing too much Python and C# ?).
你当然可以很容易地调整我的代码，所以它不使用Iterable- 我只是使用它，因为它是一种表示序列的优雅方式（另外，我一直在做太多的 Python 和 C# ？）。
回答by getekha
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.
编辑：忘记提及要使其工作，您可能必须反转您的 comparTo 函数，因为它会在每个周期丢弃具有最高优先级的函数。（如果 a 是“更好的” b compare (a, b) 应该返回一个正数。
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;
}
回答by Vladimir Giverts
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
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.
根据我的测试，它具有出色的性能。
回答by Basil Bourque
MinMaxPriorityQueue, Google Guava
MinMaxPriorityQueue, 谷歌番石榴
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: MinMaxPriorityQueuefound in Google Guavaas of version 8.
确实有一个用于维护队列的类，当添加一个超过集合最大大小的项目时，比较这些项目以找到要删除的项目，从而创建空间：MinMaxPriorityQueue在Google Guava版本 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 EvictingQueueclass.
顺便说一句，如果您只想删除最旧的元素而不对对象的值进行任何比较，Google Guava 15 获得了EvictingQueue该类。
