Esiste un’implementazione PriorityQueue con capacità fissa e comparatore personalizzato?

Domande correlate:

  • Java PriorityQueue con dimensioni fisse
  • Come utilizzo un PriorityQueue?
  • ottieni indici di n elementi più piccoli in un array
  • Scala: C’è un modo per usare PriorityQueue come farei in Java?

Ho un set di dati molto grande (più di 5 milioni di elementi) e ho bisogno di ottenere N elementi più grandi da esso. Il modo più naturale per farlo è usare la coda heap / prioritaria memorizzando solo i primi N elementi . Esistono diverse buone implementazioni della coda di priorità per JVM (Scala / Java), ovvero:

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

I primi 2 sono belli, ma memorizzano tutti gli elementi, che nel mio caso rappresentano un sovraccarico della memoria critica. Terzo (l’implementazione di Lucene) non ha un tale inconveniente, ma come posso vedere dalla documentazione non supporta anche il comparatore personalizzato, il che lo rende inutile per me.

Quindi, la mia domanda è: Esiste un’implementazione PriorityQueue con capacità fissa e comparatore personalizzato ?

UPD. Finalmente ho creato la mia implementazione, basata sulla risposta di 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; } } } } 

    (dove NaturalComparator è preso da questa domanda)

    È ansible utilizzare un SortedSet ad esempio TreeSet con un comparatore personalizzato e rimuovere il più piccolo quando la dimensione raggiunge N.

    Come puoi dire che Lucene’s non supporta un comparatore personalizzato?

    È astratto e devi implementare il metodo astratto lessThan(T a, T b)

    Anche se una vecchia domanda potrebbe essere utile a qualcun altro. Puoi utilizzare minMaxPriorityQueue della libreria Java di Google guava.

    Non riesco a pensare a uno pronto all’uso, ma puoi verificare la mia implementazione di questa raccolta con requisiti simili.

    La differenza è il comparatore, ma se estendi da PriorityQueue lo avrai. E su ogni aggiunta controlla se non hai raggiunto il limite e, se lo hai, elimina l’ultimo elemento.

    Di seguito è l’implementazione che ho usato prima. Conforms al suggerimento di Pietro.

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

    Apprezzerei qualsiasi feedback btw.

    EDIT: Sembra che l’uso di un TreeSet non sia molto efficiente dopo tutto perché le chiamate a first() sembrano prendere il tempo sublinear. Ho modificato TreeSet su PriorityQueue . Il metodo add() modificato ha il seguente aspetto:

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

    Esattamente quello che stavo cercando. Tuttavia, l’implementazione contiene un bug:

    Vale a dire: se elementiLeft> 0 ed e sono già contenuti in TreeSet. In questo caso, elementsLeft viene diminuito, ma il numero di elementi nel TreeSet rimane lo stesso.

    Suggerirei di sostituire le righe corrispondenti nel metodo add () di

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

    Prova questo codice:

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

    Ecco uno che ho messo insieme se hai guava. Penso che sia abbastanza completo. Fammi sapere se mi sono perso qualcosa.

    È ansible utilizzare la gauva ForwardingBlockingQueue in modo da non dover mappare tutti gli altri metodi.

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

    Crea un valore PriorityQueue che ha un limite di dimensioni. Memorizza i numeri N max.

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