example - Prioridad de JavaQueue con tamaño fijo

priority queue python

Question

Estoy calculando una gran cantidad de posibles combinaciones resultantes de algortihm. Para ordenar estas combinaciones, las califico con un valor doble y las almaceno en PriorityQueue. Actualmente, hay cerca de 200k elementos en esa cola, que es prácticamente una memoria intesiva. En realidad, solo necesito, digamos, los mejores 1000 o 100 de todos los elementos de la lista. Entonces comencé a preguntarme si hay una manera de tener una cola de prioridad con un tamaño fijo en Java. Debería comportarme así: ¿el artículo es mejor que uno de los ya almacenados? En caso afirmativo, insértelo en la posición correspondiente y arroje el elemento con la menor calificación.

¿Alguien tiene alguna idea? Muchas gracias de nuevo!

Marco

Answer 1

MinMaxPriorityQueue , Google Guava

De hecho, existe una clase para mantener una cola que, al agregar un elemento que excede el tamaño máximo de la colección, compara los elementos para encontrar un elemento para eliminar y, por lo tanto, crear espacio: MinMaxPriorityQueue encontrado en Google Guava a partir de la versión 8.

EvictingQueue

Por cierto, si simplemente quiere eliminar el elemento más antiguo sin hacer ninguna comparación de los valores de los objetos, Google Guava 15 ganó la clase EvictingQueue .

Answer 2

Hay una cola de prioridad de tamaño fijo en Apache Lucene: http://lucene.apache.org/java/2_4_1/api/org/apache/lucene/util/PriorityQueue.html

Tiene un excelente rendimiento basado en mis pruebas.

Answer 3

Parece natural simplemente mantener los primeros 1000 cada vez que agregue un elemento, pero PriorityQueue no ofrece nada para lograrlo con elegancia. Tal vez puedas, en lugar de utilizar PriorityQueue , hacer algo como esto en un método:

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

Answer 4

Solo poll() la cola si su elemento menos es menor que (en su caso, tiene una clasificación peor que) el elemento actual.

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

Esto supone que tiene algún tipo de combinación de clase que implementa Comparable que compara combinaciones en su calificación.

Editar: solo para aclarar, el Iterable en mi ejemplo no necesita ser rellenado previamente. Por ejemplo, aquí hay un Iterable<Integer> que le dará todos los números naturales que un int puede representar:

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

El consumo de memoria es muy modesto, como puede ver, para más de 2 mil millones de valores, necesita dos objetos (el Iterable y el Iterator ) más uno int .

Por supuesto, puedes adaptar mi código con bastante facilidad para que no use un Iterable ; simplemente lo usé porque es una forma elegante de representar una secuencia (también, he estado haciendo demasiado Python y C # ☺).

Answer 5

Un mejor enfoque sería moderar más estrechamente lo que pasa en la cola, eliminarlo y anexarlo a medida que se ejecuta el programa. Parece que habría espacio para excluir algunos elementos antes de agregarlos a la cola. Sería más simple que reinventar la rueda, por así decirlo.

Answer 6

Utilice 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 7

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

¿O entendí mal tu pregunta?

editar: se olvidó de mencionar que para que esto funcione probablemente tengas que invertir tu función comparTo ya que tirará la que tiene la más alta prioridad en cada ciclo. (si a es "mejor" b compare (a, b) debe devolver un número positivo.

ejemplo para mantener los números más grandes usan algo como esto:

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