Java PriorityQueue с фиксированным размером

Question

Я вычисляю большое количество возможных результирующих комбинаций алгоритма. Чтобы отсортировать эти комбинации, я оцениваю их по двойному значению и сохраняю в PriorityQueue. В настоящее время в этой очереди около 200 тыс. Элементов, что в значительной степени занимает память. На самом деле, мне нужно только сказать, скажем, 1000 или 100 лучших из всех предметов в списке. Поэтому я только начал задавать себе вопрос, есть ли способ иметь приоритетную очередь с фиксированным размером в Java. Я должен вести себя так: Является ли товар лучше, чем один из уже сохраненных? Если да, вставьте его в соответствующую позицию и выбросьте элемент с наименьшим рейтингом.

У кого-нибудь есть идея? Еще раз большое спасибо!

Marco

Answer 1

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

или я не понял вашего вопроса?

edit: забыл упомянуть, что для того, чтобы это работало, вам, вероятно, придется инвертировать вашу функцию сравнения, поскольку она будет отбрасывать ту, которая имеет самый высокий приоритет в каждом цикле. (если 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 найдено в Google Guava начиная с версии 8.

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:

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

Кажется естественным просто сохранять топ-1000 каждый раз, когда вы добавляете элемент, но PriorityQueue не предлагает ничего, чтобы изящно этого добиться. Возможно, вы можете вместо PriorityQueue сделать что-то подобное в методе:

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

Answer 6

Просто 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();
            }
        };
    }
};

Как видите, потребление памяти очень скромное - для более чем 2 миллиардов значений вам нужно два объекта (Iterable и Iterator) плюс один int.

Конечно, вы можете довольно легко адаптировать мой код, чтобы он не использовал Iterable - я просто использовал его, потому что это элегантный способ представления последовательности (также я слишком много делал на Python и C # ☺ ).

Answer 7

Лучшим подходом было бы более жесткое модерирование того, что идет в очереди, удаление и добавление к нему при запуске программы. Похоже, что есть место для исключения некоторых элементов, прежде чем вы добавите их в очередь. Это было бы проще, чем, так сказать, изобретать велосипед.