File d'attente à taille limitée contenant les derniers N éléments en Java

197

Une question très simple et rapide sur les bibliothèques Java: existe-t-il une classe prête à l'emploi qui implémente un Queueavec une taille maximale fixe - c'est-à-dire qu'elle permet toujours l'ajout d'éléments, mais elle supprimera silencieusement les éléments head pour accueillir l'espace pour les éléments nouvellement ajoutés.

Bien sûr, il est trivial de l'implémenter manuellement:

import java.util.LinkedList;

public class LimitedQueue<E> extends LinkedList<E> {
    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        super.add(o);
        while (size() > limit) { super.remove(); }
        return true;
    }
}

Pour autant que je vois, il n'y a pas d'implémentation standard dans stdlibs Java, mais peut-être qu'il y en a une dans Apache Commons ou quelque chose comme ça?

GreyCat
la source
9
@Kevin: Tu es vraiment une allumeuse.
Mark Peters
5
Personnellement je n'introduirais pas une autre bibliothèque si c'était la seule utilisation de cette bibliothèque ...
Nicolas Bousquet
2
@Override public boolean add (PropagationTask t) {boolean added = super.add (t); while (ajout de && size ()> limite) {super.remove (); } retour ajouté; }
Renaud
6
Attention: le code en question, bien qu'il apparemment fonctionne, il pourrait se retourner. Il existe des méthodes supplémentaires qui peuvent ajouter plus d'éléments à la file d'attente (telles que addAll ()) qui ignorent cette vérification de taille. Pour plus de détails, voir Effective Java 2nd Edition - Item 16: Favoriser la composition plutôt que l'héritage
Diego

Réponses:

171

Apache commons collections 4 a un CircularFifoQueue <> qui est ce que vous recherchez. Citant le javadoc:

CircularFifoQueue est une file d'attente premier entré, premier sorti avec une taille fixe qui remplace son élément le plus ancien s'il est plein.

    import java.util.Queue;
    import org.apache.commons.collections4.queue.CircularFifoQueue;

    Queue<Integer> fifo = new CircularFifoQueue<Integer>(2);
    fifo.add(1);
    fifo.add(2);
    fifo.add(3);
    System.out.println(fifo);

    // Observe the result: 
    // [2, 3]

Si vous utilisez une ancienne version des collections communes Apache (3.x), vous pouvez utiliser CircularFifoBuffer qui est fondamentalement la même chose sans génériques.

Mise à jour : réponse mise à jour après la publication de la version 4 des collections communes qui prend en charge les génériques.

Asaf
la source
1
C'est un bon candidat, mais, hélas, il n'utilise pas de génériques :(
GreyCat
Merci! On dirait que c'est l'alternative la plus viable pour l'instant :)
GreyCat
3
Voir cette autre réponse pour le lien à EvictingQueueajouter à la version 15 de Google Guava vers 2013-10.
Basil Bourque
Y a-t-il un rappel appelé lorsque l'élément est expulsé de la file d'attente en raison de l'ajout à la file d'attente complète?
ed22
une "file d'attente circulaire" n'est qu'une implémentation qui répond à la question. Mais la question ne bénéficie pas directement des principales différences d'une file d'attente circulaire, c'est-à-dire de ne pas avoir à libérer / réallouer chaque compartiment à chaque ajout / suppression.
simpleuser
90

La goyave a désormais une EvictingQueue , une file d'attente non bloquante qui expulse automatiquement les éléments de la tête de la file d'attente lors de la tentative d'ajouter de nouveaux éléments dans la file d'attente et elle est pleine.

import java.util.Queue;
import com.google.common.collect.EvictingQueue;

Queue<Integer> fifo = EvictingQueue.create(2); 
fifo.add(1); 
fifo.add(2); 
fifo.add(3); 
System.out.println(fifo); 

// Observe the result: 
// [2, 3]
Miguel
la source
Cela devrait être intéressant à utiliser une fois qu'il sortira officiellement.
Asaf
Voici la source: code.google.com/p/guava-libraries/source/browse/guava/src/com/… - il semble qu'il serait facile de copier et de compiler avec les versions actuelles de Guava
Tom Carchrae
1
Mise à jour: Cette classe a été officiellement publiée avec Google Guava dans la version 15 , vers 2013-10.
Basil Bourque
1
@MaciejMiklas La question demande un FIFO, EvictingQueueest un FIFO. En cas de doute, essayez ce programme: Queue<Integer> fifo = EvictingQueue.create(2); fifo.add(1); fifo.add(2); fifo.add(3); System.out.println(fifo); Observez le résultat:[2, 3]
kostmo
2
C'est maintenant la bonne réponse. Ce n'est pas clair dans la documentation, mais EvictingQueue est un FIFO.
Michael Böckling
11

J'aime la solution @FractalizeR. Mais je voudrais en plus garder et retourner la valeur de super.add (o)!

public class LimitedQueue<E> extends LinkedList<E> {

    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
           super.remove();
        }
        return added;
    }
}
Renaud
la source
1
Pour autant que je puisse voir, FractalizeR n'a fourni aucune solution, seulement édité la question. La «solution» dans la question n'est pas une solution, car la question portait sur l'utilisation d'une classe dans une bibliothèque standard ou semi-standard, et non sur la vôtre.
GreyCat
3
Il convient de souligner que cette solution n'est pas thread-safe
Konrad Morawski
7
@KonradMorawski toute la classe LinkedList n'est pas thread-safe de toute façon, donc votre commentaire est inutile dans ce contexte!
Renaud du
La sécurité des threads @RenaudBlue est une préoccupation valable (si souvent négligée), donc je ne pense pas que le commentaire soit inutile. et rappeler que ce LinkedListn'est pas sûr pour les threads ne serait pas inutile non plus. dans le contexte de cette question, l'exigence spécifique de l'OP rend particulièrement important que l'ajout d'un article soit effectué comme une opération atomique. en d'autres termes, le risque de ne pas garantir l'atomicité serait plus important que dans le cas d'une LinkedList régulière.
Konrad Morawski du
4
Se casse dès que quelqu'un appelle à la add(int,E)place. Et si cela addAllfonctionne comme prévu, dépend de détails d'implémentation non spécifiés. C'est pourquoi vous devriez préférer la délégation à l'héritage…
Holger
6

Utilisez la composition et non les étendues (oui, je veux dire les étendues, comme dans une référence au mot clé extend en java et oui, c'est l'héritage) La composition est supérieure car elle protège complètement votre implémentation, vous permettant de modifier l'implémentation sans impact sur les utilisateurs de votre classe.

Je recommande d'essayer quelque chose comme ça (je tape directement dans cette fenêtre, donc l'acheteur se méfie des erreurs de syntaxe):

public LimitedSizeQueue implements Queue
{
  private int maxSize;
  private LinkedList storageArea;

  public LimitedSizeQueue(final int maxSize)
  {
    this.maxSize = maxSize;
    storageArea = new LinkedList();
  }

  public boolean offer(ElementType element)
  {
    if (storageArea.size() < maxSize)
    {
      storageArea.addFirst(element);
    }
    else
    {
      ... remove last element;
      storageArea.addFirst(element);
    }
  }

  ... the rest of this class

Une meilleure option (basée sur la réponse d'Asaf) pourrait être d'encapsuler Apache Collections CircularFifoBuffer avec une classe générique. Par exemple:

public LimitedSizeQueue<ElementType> implements Queue<ElementType>
{
    private int maxSize;
    private CircularFifoBuffer storageArea;

    public LimitedSizeQueue(final int maxSize)
    {
        if (maxSize > 0)
        {
            this.maxSize = maxSize;
            storateArea = new CircularFifoBuffer(maxSize);
        }
        else
        {
            throw new IllegalArgumentException("blah blah blah");
        }
    }

    ... implement the Queue interface using the CircularFifoBuffer class
}
DwB
la source
2
+1 si vous expliquez pourquoi la composition est un meilleur choix (autre que "préférez la composition à l'héritage) ... et il y a une très bonne raison
kdgregory
1
La composition est un mauvais choix pour ma tâche ici: cela signifie au moins deux fois le nombre d'objets => au moins deux fois plus souvent la collecte des ordures. J'utilise de grandes quantités (des dizaines de millions) de ces files d'attente de taille limitée, comme cela: Map <Long, LimitedSizeQueue <String>>.
GreyCat
@GreyCat - Je suppose que vous n'avez pas regardé comment LinkedListest implémenté, alors. L'objet supplémentaire créé comme enveloppe autour de la liste sera assez mineur, même avec "des dizaines de millions" d'instances.
kdgregory
J'allais pour «réduit la taille de l'interface», mais «protège la mise en œuvre» est à peu près la même chose. L'une ou l'autre répond aux plaintes de Mark Peter concernant l'approche du PO.
kdgregory
4

La seule chose que je sais qui a un espace limité est l'interface BlockingQueue (qui est par exemple implémentée par la classe ArrayBlockingQueue) - mais ils ne suppriment pas le premier élément s'il est rempli, mais bloquent plutôt l'opération put jusqu'à ce que l'espace soit libre (supprimé par un autre thread) ).

À ma connaissance, votre implémentation triviale est le moyen le plus simple d'obtenir un tel comportement.

flolo
la source
J'ai déjà parcouru les classes Java stdlib et, malheureusement, ce BlockingQueuen'est pas une réponse. J'ai pensé à d'autres bibliothèques courantes, comme Apache Commons, les bibliothèques d'Eclipse, Spring, les ajouts de Google, etc.?
GreyCat
3

Vous pouvez utiliser une MinMaxPriorityQueue de Google Guava , à partir du javadoc:

Une file d'attente prioritaire min-max peut être configurée avec une taille maximale. Si c'est le cas, chaque fois que la taille de la file d'attente dépasse cette valeur, la file d'attente supprime automatiquement son plus grand élément en fonction de son comparateur (qui pourrait être l'élément qui vient d'être ajouté). Ceci est différent des files d'attente limitées conventionnelles, qui bloquent ou rejettent les nouveaux éléments lorsqu'ils sont pleins.

moritz
la source
3
Comprenez-vous ce qu'est une file d'attente prioritaire et en quoi elle diffère de l'exemple du PO?
kdgregory
2
@Mark Peters - Je ne sais tout simplement pas quoi dire. Bien sûr, vous pouvez faire en sorte qu'une file d'attente prioritaire se comporte comme une file d'attente fifo. Vous pouvez également vous Mapcomporter comme un List. Mais les deux idées montrent une incompréhension complète des algorithmes et de la conception de logiciels.
kdgregory
2
@Mark Peters - toutes les questions sur SO ne sont-elles pas une bonne façon de faire quelque chose?
jtahlborn
3
@jtahlborn: Clairement non (code golf), mais même s'ils l'étaient, bon n'est pas un critère noir et blanc. Pour un certain projet, bon peut signifier "plus efficace", pour un autre, il peut signifier "plus facile à maintenir" et pour un autre encore, il peut signifier "moins de code avec les bibliothèques existantes". Tout cela n'est pas pertinent car je n'ai jamais dit que c'était une bonne réponse. Je viens de dire que cela peut être une solution sans trop d'efforts. Transformer un MinMaxPriorityQueueen ce que veut l'OP est plus trivial que de modifier un LinkedList(le code de l'OP ne s'en approche même pas).
Mark Peters
3
Peut-être que vous examinez mon choix de mots "dans la pratique, cela sera certainement certainement suffisant". Je ne voulais pas dire que cette solution serait presque certainement suffisante pour le problème du PO ou en général. Je faisais référence au choix d'un longtype de curseur descendant dans ma propre suggestion, disant qu'il serait suffisamment large dans la pratique, même si théoriquement vous pouvez ajouter plus de 2 ^ 64 objets à cette file d'attente, point auquel la solution se décomposerait .
Mark Peters
-2
    public class ArrayLimitedQueue<E> extends ArrayDeque<E> {

    private int limit;

    public ArrayLimitedQueue(int limit) {
        super(limit + 1);
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
            super.remove();
        }
        return added;
    }

    @Override
    public void addLast(E e) {
        super.addLast(e);
        while (size() > limit) {
            super.removeLast();
        }
    }

    @Override
    public boolean offerLast(E e) {
        boolean added = super.offerLast(e);
        while (added && size() > limit) {
            super.pollLast();
        }
        return added;
    }
}
user590444
la source
3
La question portait sur les classes dans les bibliothèques de classes de collections populaires, et non sur les siennes - une "solution" homebrew minimaliste était déjà fournie en question.
GreyCat
2
cela n'a pas d'importance google trouver cette page également sur une autre requête =)
user590444
1
Cette réponse est apparue dans la file d'attente d'examen de faible qualité, probablement parce que vous ne fournissez aucune explication du code. Si ce code répond à la question, envisagez d'ajouter un texte expliquant le code dans votre réponse. De cette façon, vous êtes beaucoup plus susceptible d'obtenir plus de votes positifs - et d'aider le questionneur à apprendre quelque chose de nouveau.
lmo