Existe-t-il une implémentation PriorityQueue avec une capacité fixe et un comparateur personnalisé?

Questions connexes:

  • Java PriorityQueue à taille fixe
  • Comment utiliser un PriorityQueue?
  • obtenir les index des n plus petits éléments d’un tableau
  • Scala: Est-il possible d’utiliser PriorityQueue comme je le ferais en Java?

J’ai un très grand dataset (plus de 5 millions d’éléments) et je dois en extraire N plus gros éléments. La manière la plus naturelle de le faire est d’utiliser la queue de tas / priorité en ne stockant que les N premiers éléments . Il existe plusieurs bonnes implémentations de queue prioritaire pour JVM (Scala / Java), à savoir:

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

Les 2 premiers sont sympas, mais ils stockent tous les éléments, ce qui dans mon cas donne une surcharge de mémoire critique. La troisième (implémentation Lucene) ne présente pas un tel inconvénient, mais comme je peux le voir dans la documentation, elle ne supporte pas non plus le comparateur personnalisé, ce qui le rend inutile.

Ma question est donc la suivante: existe-t-il une implémentation PriorityQueue avec une capacité fixe et un comparateur personnalisé ?

UPD. Enfin, j’ai créé ma propre implémentation, basée sur la réponse 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; } } } } 

(où NaturalComparator est tiré de cette question)

Vous pouvez utiliser un SortedSet, par exemple TreeSet avec un comparateur personnalisé et supprimer le plus petit lorsque la taille atteint N.

Comment pouvez-vous dire que Lucene ne prend pas en charge un comparateur personnalisé?

Son résumé et vous devez implémenter la méthode abstraite lessThan(T a, T b)

Bien qu’une vieille question, mais cela peut être utile à quelqu’un d’autre. Vous pouvez utiliser minMaxPriorityQueue de la bibliothèque Java de Google.

Je ne peux pas penser à une version prête à l’emploi, mais vous pouvez vérifier mon implémentation de cette collection avec des exigences similaires.

La différence est le comparateur, mais si vous passez de PriorityQueue vous l’aurez. Et à chaque ajout, vérifiez si vous n’avez pas atteint la limite et si vous avez – supprimez le dernier élément.

Ci-dessous la mise en œuvre que j’ai utilisée auparavant. Conforme à la suggestion 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)); } } 

J’apprécierais n’importe quelle rétroaction btw.

EDIT: Il semble que l’utilisation d’un TreeSet ne soit pas très efficace, car les appels à first() semblent prendre un temps sublinear. J’ai changé le TreeSet en PriorityQueue . La méthode add() modifiée ressemble à ceci:

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

Exactement ce que je cherchais. Cependant, l’implémentation contient un bogue:

À savoir: si elementsLeft> 0 et e est déjà contenu dans le TreeSet. Dans ce cas, elementsLeft est diminué, mais le nombre d’éléments dans TreeSet rest le même.

Je suggère de remplacer les lignes correspondantes dans la méthode add () par

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

Essayez ce code:

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

En voici un que je met ensemble si vous avez de la goyave. Je pense que c’est assez complet. Faites-moi savoir si j’ai raté quelque chose.

Vous pouvez utiliser gauva ForwardingBlockingQueue pour ne pas avoir à mapper toutes les autres méthodes.

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

Créez un fichier PriorityQueue avec une taille limite. Il stocke N nombres maximum.

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