是否有具有固定容量和自定义比较器的 PriorityQueue 实现? [英] Is there a PriorityQueue implementation with fixed capacity and custom comparator?
问题描述
相关问题:
我有一个非常大的数据集(超过 500 万个项目)，我需要从中获取 N 个最大 的项目.最自然的方法是使用堆/优先级队列仅存储前 N 个项目.JVM(Scala/Java)优先级队列有几个很好的实现，分别是:
I have a very large data set (more than 5 millions items) and I need to get N largest items from it. The most natural way to do it is to use heap/priority queue storing only top N items. There are several good implementations of priority queue for JVM (Scala/Java), namely:
前 2 个不错，但它们存储所有项目，在我的情况下，这会产生关键的内存开销.第三(Lucene 实现)没有这样的缺点，但正如我从文档中看到的那样，它也不支持自定义比较器，这对我来说毫无用处.
First 2 are nice, but they store all the items, which in my case gives critical memory overhead. Third (Lucene implementation) doesn't have such a drawback, but as I can see from documentation it also doesn't support custom comparator, which makes it useless for me.
那么，我的问题是:是否有具有固定容量和自定义比较器的PriorityQueue实现?
So, my question is: Is there a PriorityQueue implementation with fixed capacity and custom comparator?
UPD.最后，我根据彼得的回答创建了自己的实现:
UPD. Finally I've created my own implementation, based on Peter's answer:
public class FixedSizePriorityQueue<E> extends TreeSet<E> {
private int elementsLeft;
public FixedSizePriorityQueue(int maxSize) {
super(new NaturalComparator());
this.elementsLeft = maxSize;
}
public FixedSizePriorityQueue(int maxSize, Comparator<E> comparator) {
super(comparator);
this.elementsLeft = maxSize;
}
/**
* @return true if element was added, false otherwise
* */
@Override
public boolean add(E e) {
if (elementsLeft == 0 && size() == 0) {
// max size was initiated to zero => just return false
return false;
} else if (elementsLeft > 0) {
// queue isn't full => add element and decrement elementsLeft
boolean added = super.add(e);
if (added) {
elementsLeft--;
}
return added;
} else {
// there is already 1 or more elements => compare to the least
int compared = super.comparator().compare(e, this.first());
if (compared == 1) {
// new element is larger than the least in queue => pull the least and add new one to queue
pollFirst();
super.add(e);
return true;
} else {
// new element is less than the least in queue => return false
return false;
}
}
}
}
(其中 NaturalComparator 取自 这个问题)
(where NaturalComparator is taken from this question)
推荐答案
您可以使用 SortedSet，例如带有自定义比较器的 TreeSet 并在大小达到 N 时移除最小的.
You could use a SortedSet e.g. TreeSet with a custom comparator and remove the smallest when the size reachs N.
这篇关于是否有具有固定容量和自定义比较器的 PriorityQueue 实现?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
