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

Question

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

Глубокое копирование может только быть сделано с согласием каждого класса. Если Вы управляете иерархией классов тогда, можно реализовать клонируемый интерфейс и реализовать метод Клона. Иначе выполнение глубокой копии невозможно сделать безопасно, потому что объект может также совместно использовать неинформационные ресурсы (например, соединения с базой данных). В целом однако глубокое копирование считают плохой практикой в среде Java и нужно избежать через соответствующие методы дизайна.

34

java list size priority-queue

задан Marco 4 December 2009 в 10:54

6 ответов

Другие вопросы по тегам:

java list size priority-queue

Похожие вопросы:

score 28 · Answer 1

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

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

edit: забыл упомянуть, что чтобы это сработало, вам, вероятно, придется инвертировать функцию compareTo, поскольку она отбрасывает функцию с наивысшим приоритетом в каждом цикле. (если a "лучше", b compare (a, b) должен возвращать число positvie.

пример сохранения наибольших чисел, используйте что-то вроде этого:

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

score 5 · Answer 2

В Apache Lucene есть очередь с приоритетом фиксированного размера: http://lucene.apache.org/java/2_4_1/api/org/apache/lucene/util/PriorityQueue.html

По результатам моих тестов он имеет отличную производительность.

score 2 · Answer 3

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

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

score 2 · 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);   
}

score 2 · Answer 5

Просто опросить () очередь, если ее наименьший элемент меньше (в вашем случае имеет худший рейтинг, чем) текущий элемент.

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 , который сравнивает комбинации по их рейтингу.

Edit: Просто чтобы уточнить, 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();
            }
        };
    }
};

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

Конечно, вы можете довольно легко адаптировать мой код, чтобы он не

score 0 · Answer 6

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