49

我正在计算大量可能的算法组合。为了对这些组合进行排序，我用双倍值对它们进行评分，并将它们存储在 PriorityQueue 中。目前，该队列中有大约 200k 个项目，这非常占用内存。实际上，我只需要说列表中所有项目中最好的 1000 个或 100 个。所以我刚开始问自己是否有办法在 Java 中拥有一个固定大小的优先级队列。我应该这样做：该项目是否比已存储的项目之一更好？如果是，则将其插入到相应的位置，然后将评分最低的元素扔掉。

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

马可

4

7 回答 7

42 
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;
        }
于 2009-12-04T14:12:22.597 回答
14

MinMaxPriorityQueue, 谷歌番石榴

确实有一个用于维护队列的类，当添加一个超出集合最大大小的项目时，它会比较项目以找到要删除的项目，从而创建空间：从版本 8MinMaxPriorityQueue开始在Google Guava中找到。

驱逐队列

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

于 2014-02-11T10:39:51.963 回答
5

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

根据我的测试，它具有出色的性能。

于 2009-12-04T18:37:14.320 回答
2

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

这假设您有某种组合类，它实现Comparable了比较组合的评级。

编辑：只是为了澄清，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();
            }
        };
    }
};

如您所见，内存消耗非常少 - 对于超过 20 亿个值，您需要两个对象（ theIterable和 the Iterator）加上一个int。

当然，您可以相当轻松地调整我的代码，使其不使用Iterable- 我只是使用它，因为它是表示序列的一种优雅方式（另外，我已经做了太多 Python 和 C# ☺）。

于 2009-12-04T12:25:58.760 回答
2

使用排序集：

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);   
}
于 2009-12-04T12:12:14.050 回答
0

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

于 2009-12-04T11:05:36.757 回答
-1

每次添加项目时只保留前 1000 名似乎很自然，但PriorityQueue并没有提供任何东西来优雅地实现这一目标。也许你可以PriorityQueue在一个方法中做这样的事情，而不是使用 a ：

List<Double> list = new ArrayList<Double>();
...
list.add(newOutput);
Collections.sort(list);
list = list.subList(0, 1000);
于 2009-12-04T11:55:52.053 回答