具有固定大小的 Java PriorityQueue

Question

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

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

马可

Answer 1

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

或者我误解了你的问题？

编辑：忘记提及，要使其工作，您可能必须反转您的 comparTo 函数，因为它会丢弃每个周期中优先级最高的函数。 （如果 a “更好”b 比较 (a, b) 应该返回一个正数。

保持最大数字的示例使用如下所示：

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

Answer 2

MinMaxPriorityQueue，Google Guava

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

EvictingQueue

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

Answer 3

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

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

Answer 4

使用排序集：

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

Answer 5

如果队列的最小元素小于当前元素（在您的情况下，评级更差），则只需 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 将为您提供 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# ☺)。

Answer 6

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

Answer 7

我的优先级队列的大多数用例都需要大小限制。目前尚不清楚为什么 Java 设计没有从具有强制大小限制的 ArrayBlockingQueue 扩展 PriorityBlockingQueue。

在没有从上面的答案中查看第三方类的情况下，您需要同步限制控制。

import java.util.Comparator;
import java.util.concurrent.PriorityBlockingQueue;

/**
 * Limited Priority Queue with put/offer/take
 * 
 * @implNote poll(), offer(time) not implemented
 */
public class LimitedPriorityBlockingQueue<E> extends PriorityBlockingQueue<E>
{
    /**
     * 
     * @param maxDim     initial and maximum size
     * @param comparator priority relation
     */
    public LimitedPriorityBlockingQueue(final int maxDim, final Comparator<E> comparator)
    {
        super(maxDim, comparator);
        this.maxDim = maxDim;
        this.putSync = new Object();
    }

    @Override
    public boolean offer(final E s)
    {
        synchronized (putSync)
        {
            if (size() >= maxDim)
            {
                // avoid growth
                return false;
            }
            else
            {
                return super.offer(s);
            }
        }
    }

    @Override
    public void put(final E s)
    {
        synchronized (putSync)
        {
            if (size() >= maxDim)
            {
                try
                {
                    putSync.wait();
                }
                catch (final InterruptedException e)
                {
                    // deal with empty inherited throw list
                    throw new RuntimeException(e.getMessage());
                }
            }
            super.put(s);
        }
    }

    @Override
    public synchronized E take() throws InterruptedException
    {
        final E res = super.take();
        synchronized (putSync)
        {
            putSync.notify();
        }
        return res;
    }

    protected int maxDim;
    protected final Object putSync;

    private static final long serialVersionUID = 1484945675769120529L;
}

Answer 8

每次添加项目时只保留前 1000 个项目似乎很自然，但是 PriorityQueue 没有提供任何东西来优雅地实现这一点。也许您可以在方法中执行类似以下操作，而不是使用 PriorityQueue：

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