Java PriorityQueue固定大小

Question

Java PriorityQueue固定大小

53

我正在计算一种算法的大量可能的结果组合。为了对这些组合进行排序，我用双重值对它们进行评分，并将它们存储在PriorityQueue中。目前，该队列中有大约200k个项目，这会消耗很多内存。实际上，我只需要说最好的1000或100个项目中的一个。

所以，我开始想是否有一种方法可以在Java中使用固定大小的优先级队列。它应该像这样表现：

如果项目比已存储的项目更好，就将其插入到相应的位置并且丢弃评分最低的元素。

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

马尔科

- Marco

可能是是否有具有固定容量和自定义比较器的PriorityQueue实现？的重复。 - Raedwald

1

@Raedwald：嗯，这个问题是在你说它是重复的那个问题之前几乎两年就被问过了。你可能把它搞错了。;-) - Amos M. Carpenter

7个回答

17

`MinMaxPriorityQueue`，Google Guava

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

EvictingQueue

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

- Basil Bourque

3

如果只看队列的一个方面，似乎Guava不太鼓励使用MinMaxPriorityQueue。请参阅“性能注释”：https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/MinMaxPriorityQueue.html - Tarrasch

@Tarrasch 我并不是这个话题的专家，但我对那些笔记的阅读显示出 (a) 如果你想要自动清除而非手动操作，并且 (b) 你正在设置一个最大大小，那么这个类是适当的。 - Basil Bourque

5

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

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

- Vladimir Giverts

2

使用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);   
}

- Victor Sorokin

4

一个集合不允许多个“项”具有相同的评分。 - gustafc

取决于您如何定义 Set 的 Comparator -- 它可以考虑 Item 的不仅是评分，而且可能是某些唯一的字段，比如 id。 - Victor Sorokin

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亿个值，您只需要两个对象（Iterable和Iterator）以及一个int。

当然，您可以相对容易地调整我的代码，使其不使用Iterable——我只是使用它作为表示序列的优雅方式（另外，我已经做了太多Python和C#的事情☺）。

- gustafc

这是否假定您已经拥有valueGenerator中的所有项目？ - vahidg

我认为OP的目标之一是避免在第一时间就在Iterable中累积太多的项。此外，如果排名越高，算法越好，那么peek并不是你想要的。 - vahidg

不，你不需要将它们全部准备好。迭代器可以在其 next() 方法中即时生成值。 - gustafc

为什么 peek() 不能解决问题呢？它返回最小的元素，如果当前元素比最小元素更好，我会将最小元素舍弃并添加当前元素。我已经测试了代码，它是有效的。 - gustafc

如果你有疑问，就试一下这段代码——它是有效的。引用JavaDocs中的话：“此队列的头部是相对于指定排序方式的最小元素。[...]队列检索操作poll、remove、peek和element访问队列头部的元素。”正如我在帖子中所说的：我假设用于表示组合的任何内容都以一种将低评级组合视为“小于”更高评级组合的方式实现了Comparable。如果它没有或不能这样做，我将其留给读者来修改我的示例，以便使用自定义比较器。 - gustafc

1

是的，你说得对，头部确实是最小的元素。由于某种原因，我以为它是相反的。 - vahidg

0

一个更好的方法是更严格地审查排队的内容，随着程序的运行而删除和添加它。听起来可以在将项目添加到队列之前排除一些项目。这比重新发明轮子要简单。

- Gordon

-1

每次添加一个新项时，似乎自然而然的做法是只保留前1000个，但是PriorityQueue并没有提供优雅地实现这一点的方式。也许你可以不使用PriorityQueue，而在一个方法中实现类似以下操作：

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

- vahidg

1

同时使用TreeMap，您可以轻松获得最高值，并且如果当前结果大于该值，则完全可以避免插入，否则删除最后一个键并插入新值。 - Lorenzo Boccaccia

1

@Lorenzo，Map不太好，因为它不允许具有相同评分的两个组合。 - gustafc

4

这种方法没有红黑树实现的性能优势，且会影响性能。 - nimcap

这样做的性能非常糟糕，因为每次都要对数组进行排序。使用堆添加元素会更快。 - ThatDataGuy

这样做会严重降低性能，因为我们每次添加元素时都要对列表进行排序。 - Pramod

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- getekha · Accepted Answer

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

或者我误解了你的问题？

编辑：忘记提到为了使其工作，您可能需要反转compareTo函数，因为它每个循环都会丢弃具有最高优先级的函数。（如果a比b“更好”，则比较（a，b）应返回正数。

要保留最大的数字，请使用以下代码示例：

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

Java PriorityQueue固定大小

MinMaxPriorityQueue，Google Guava

EvictingQueue

`MinMaxPriorityQueue`，Google Guava