¿Hay una implementación de PriorityQueue con capacidad fija y un comparador personalizado?

Preguntas relacionadas:

  • Prioridad de JavaQueue con tamaño fijo
  • ¿Cómo uso un PriorityQueue?
  • obtener índices de n elementos más pequeños en una matriz
  • Scala: ¿Hay alguna forma de usar PriorityQueue como lo haría en Java?

Tengo un conjunto de datos muy grande (más de 5 millones de elementos) y necesito obtener N elementos más grandes de él. La forma más natural de hacerlo es usar la cola de prioridad / montón almacenando solo los N elementos principales . Hay varias buenas implementaciones de cola de prioridad para JVM (Scala / Java), a saber:

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

Los primeros 2 son agradables, pero almacenan todos los elementos, lo que en mi caso da sobrecarga de memoria crítica. Tercero (implementación de Lucene) no tiene tal inconveniente, pero como puedo ver en la documentación, tampoco es compatible con el comparador personalizado, lo cual lo hace inútil para mí.

Entonces, mi pregunta es: ¿hay una implementación de PriorityQueue con capacidad fija y un comparador personalizado ?

UPD. Finalmente, he creado mi propia implementación, basada en la respuesta de Peter:

 public class FixedSizePriorityQueue extends TreeSet { private int elementsLeft; public FixedSizePriorityQueue(int maxSize) { super(new NaturalComparator()); this.elementsLeft = maxSize; } public FixedSizePriorityQueue(int maxSize, Comparator 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; } } } } 

(donde NaturalComparator está tomado de esta pregunta)

Puede usar un SortedSet, por ejemplo, TreeSet con un comparador personalizado y eliminar el más pequeño cuando el tamaño scope N.

¿Cómo se puede decir que Lucene no es compatible con un comparador personalizado?

Es abstracto y debe implementar el método abstracto lessThan(T a, T b)

Aunque es una vieja pregunta, pero puede ser útil para otra persona. Puede usar minMaxPriorityQueue de la biblioteca Java de Google guayaba.

No puedo pensar en uno listo para usar, pero puede verificar mi implementación de esta colección con requisitos similares.

La diferencia es el comparador, pero si se extiende desde PriorityQueue lo tendrá. Y en cada verificación adicional, si no ha llegado al límite, y si lo tiene, suelte el último elemento.

Debajo está la implementación que utilicé antes. Cumple con la sugerencia de Peter.

  public @interface NonThreadSafe { } /** * A priority queue implementation with a fixed size based on a {@link TreeMap}. * The number of elements in the queue will be at most {@code maxSize}. * Once the number of elements in the queue reaches {@code maxSize}, trying to add a new element * will remove the greatest element in the queue if the new element is less than or equal to * the current greatest element. The queue will not be modified otherwise. */ @NonThreadSafe public static class FixedSizePriorityQueue { private final TreeSet treeSet; /* backing data structure */ private final Comparator comparator; private final int maxSize; /** * Constructs a {@link FixedSizePriorityQueue} with the specified {@code maxSize} * and {@code comparator}. * * @param maxSize - The maximum size the queue can reach, must be a positive integer. * @param comparator - The comparator to be used to compare the elements in the queue, must be non-null. */ public FixedSizePriorityQueue(final int maxSize, final Comparator comparator) { super(); if (maxSize <= 0) { throw new IllegalArgumentException("maxSize = " + maxSize + "; expected a positive integer."); } if (comparator == null) { throw new NullPointerException("Comparator is null."); } this.treeSet = new TreeSet(comparator); this.comparator = treeSet.comparator(); this.maxSize = maxSize; } /** * Adds an element to the queue. If the queue contains {@code maxSize} elements, {@code e} will * be compared to the greatest element in the queue using {@code comparator}. * If {@code e} is less than or equal to the greatest element, that element will be removed and * {@code e} will be added instead. Otherwise, the queue will not be modified * and {@code e} will not be added. * * @param e - Element to be added, must be non-null. */ public void add(final E e) { if (e == null) { throw new NullPointerException("e is null."); } if (maxSize <= treeSet.size()) { final E firstElm = treeSet.first(); if (comparator.compare(e, firstElm) < 1) { return; } else { treeSet.pollFirst(); } } treeSet.add(e); } /** * @return Returns a sorted view of the queue as a {@link Collections#unmodifiableList(java.util.List)} * unmodifiableList. */ public List asList() { return Collections.unmodifiableList(new ArrayList(treeSet)); } } 

Agradecería cualquier comentario por cierto.

EDITAR: Parece que usar un TreeSet no es muy eficiente después de todo porque las llamadas a first() parecen tomar un tiempo sublineal. Cambié el TreeSet a PriorityQueue . El método add() modificado se ve así:

  /** * Adds an element to the queue. If the queue contains {@code maxSize} elements, {@code e} will * be compared to the lowest element in the queue using {@code comparator}. * If {@code e} is greater than or equal to the lowest element, that element will be removed and * {@code e} will be added instead. Otherwise, the queue will not be modified * and {@code e} will not be added. * * @param e - Element to be added, must be non-null. */ public void add(final E e) { if (e == null) { throw new NullPointerException("e is null."); } if (maxSize <= priorityQueue.size()) { final E firstElm = priorityQueue.peek(); if (comparator.compare(e, firstElm) < 1) { return; } else { priorityQueue.poll(); } } priorityQueue.add(e); } 

Exactamente lo que estaba buscando. Sin embargo, la implementación contiene un error:

A saber: if elementsLeft> 0 y e ya está contenido en el TreeSet. En este caso, elementsLeft se reduce, pero la cantidad de elementos en TreeSet permanece igual.

Sugeriría reemplazar las líneas correspondientes en el método add () por

  } else if (elementsLeft > 0) { // queue isn't full => add element and decrement elementsLeft boolean added = super.add(e); if (added) { elementsLeft--; } return added; 

Prueba este código:

 public class BoundedPQueue> { /** * Lock used for all public operations */ private final ReentrantLock lock; PriorityBlockingQueue queue ; int size = 0; public BoundedPQueue(int capacity){ queue = new PriorityBlockingQueue(capacity, new CustomComparator()); size = capacity; this.lock = new ReentrantLock(); } public boolean offer(E e) { final ReentrantLock lock = this.lock; lock.lock(); E vl = null; if(queue.size()>= size) { vl= queue.poll(); if(vl.compareTo(e)<0) e=vl; } try { return queue.offer(e); } finally { lock.unlock(); } } public E poll() { return queue.poll(); } public static class CustomComparator> implements Comparator { @Override public int compare(E o1, E o2) { //give me a max heap return o1.compareTo(o2) *-1; } } } 

Aquí hay uno que preparo si tienes guayaba. Creo que es bastante completo. Avísame si me perdí algo.

Puedes usar el gauva ForwardingBlockingQueue para que no tengas que mapear todos los otros métodos.

 import com.google.common.util.concurrent.ForwardingBlockingQueue; public class PriorityBlockingQueueDecorator extends ForwardingBlockingQueue { public static final class QueueFullException extends IllegalStateException { private static final long serialVersionUID = -9218216017510478441L; } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private int maxSize; private PriorityBlockingQueue delegate; public PriorityBlockingQueueDecorator(PriorityBlockingQueue delegate) { this(MAX_ARRAY_SIZE, delegate); } public PriorityBlockingQueueDecorator(int maxSize, PriorityBlockingQueue delegate) { this.maxSize = maxSize; this.delegate = delegate; } @Override protected BlockingQueue delegate() { return delegate; } @Override public boolean add(E element) { return offer(element); } @Override public boolean addAll(Collection collection) { boolean modified = false; for (E e : collection) if (add(e)) modified = true; return modified; } @Override public boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException { return offer(e); } @Override public boolean offer(E o) { if (maxSize > size()) { throw new QueueFullException(); } return super.offer(o); } } 

Cree una prioridad que tenga un límite de tamaño. Almacena N números máximos.

 import java.util.*; class Demo { public static > PriorityQueue getPq(final int n, Comparator comparator) { return new PriorityQueue(comparator) { boolean full() { return size() >= n; } @Override public boolean add(E e) { if (!full()) { return super.add(e); } else if (peek().compareTo(e) < 0) { poll(); return super.add(e); } return false; } @Override public boolean offer(E e) { if (!full()) { return super.offer(e); } else if (peek().compareTo(e) < 0) { poll(); return super.offer(e); } return false; } }; } public static void printq(PriorityQueue pq) { Object o = null; while ((o = pq.poll()) != null) { System.out.println(o); } } public static void main (String[] args) { PriorityQueue pq = getPq(2, new Comparator(){ @Override public int compare(Integer i1, Integer i2) { return i1.compareTo(i2); } }); pq.add(4); pq.add(1); pq.add(5); pq.add(2); printq(pq); } } 
    Intereting Posts