相关问题:
我有一个非常大的数据集(超过500万件),我需要从中获得N个最大的项目.最自然的方法是使用堆/优先级队列,只存储前N个项目.JVM(Scala/Java)的优先级队列有几个很好的实现,即:
前2个很好,但它们存储了所有项目,在我的情况下会产生关键的内存开销.第三个(Lucene实现)没有这样的缺点,但正如我从文档中看到的那样,它也不支持自定义比较器,这对我来说没用.
所以,我的问题是:是否有PriorityQueue实现与固定容量和自定义比较？
UPD.最后,根据Peter的回答,我创建了自己的实现:
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 && …我需要在大量数据中找到N个最大元素.
我有:
迭代这些项并找到具有最大值的项的作业
Item largest = null;
// Page through big data
List<Item> items = getNextPage(pageSize);
while (items.size() > 0) {
// Update largest item based on values from current page
for (Item current : items) {
if (largest == null || largest.getValue() < current.getValue()) {
largest = current;
}
}
// Move to next page
items = getNextPage(pageSize);
}
我需要:
我的方法:
我正在考虑像固定大小的优先级队列
class PQsort implements Comparator<Item> {
public int compare(Item one, Item two) {
return two.getValue() - …