是否有具有固定容量和自定义比较器的PriorityQueue实现？ [英] Is there a PriorityQueue implementation with fixed capacity and custom comparator?

问题描述

相关问题：

• 具有固定大小的Java PriorityQueue


• 如何使用PriorityQueue？


• 获取数组中n个最小元素的索引


• Scala：有没有办法像在Java中那样使用PriorityQueue？ / a>

• Java PriorityQueue with fixed size
• How do I use a PriorityQueue?
• get indexes of n smallest elements in an array
• Scala: Is there a way to use PriorityQueue like I would in Java?

我有一个非常大的数据集（超过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:

• scala.collection.mutable.PriorityQueue


• < a href =http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html\"rel =noreferrer> java.util.PriorityQueue


• lucene.util.PriorityQueue

• scala.collection.mutable.PriorityQueue
• java.util.PriorityQueue
• lucene.util.PriorityQueue

前两个很好，但它们存储了所有项目，在我的情况下会产生关键的内存开销。第三个（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。最后我创建了自己的实现，根据Peter的回答：

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 取自这个问题）

推荐答案

你可以使用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屋！