Existe-t-il une file d'attente de taille fixe qui supprime les éléments excessifs?

127

J'ai besoin d'une file d'attente de taille fixe. Lorsque j'ajoute un élément et que la file d'attente est pleine, elle doit automatiquement supprimer l'élément le plus ancien.

Existe-t-il une implémentation pour cela en Java?

c0d3x
la source
1
que diriez-vous de stackoverflow.com/a/6058025/1392882
Miguel

Réponses:

19

Il n'existe aucune implémentation existante dans le langage Java et le Runtime. Toutes les files d'attente étendent AbstractQueue , et son document indique clairement que l'ajout d'un élément à une file d'attente complète se termine toujours par une exception. Il serait préférable (et assez simple) d'envelopper une file d'attente dans une classe à vous pour avoir les fonctionnalités dont vous avez besoin.

Encore une fois, comme toutes les files d'attente sont des enfants de AbstractQueue, utilisez simplement cela comme type de données interne et vous devriez avoir une implémentation flexible en un rien de temps :-)

METTRE À JOUR:

Comme indiqué ci-dessous, il existe deux implémentations ouvertes disponibles (cette réponse est assez ancienne, les amis!), Voir cette réponse pour plus de détails.

Moritz
la source
4
Utilisez Queue au lieu de AbstractQueue ... il peut y avoir des files d'attente qui implémentent l'interface mais n'étendent pas la classe abstraite.
TofuBeer
1
En Python, vous pouvez utiliser un collection.dequeavec un maxlen.
Jonas Gröger
2
MISE À JOUR Il existe maintenant deux classes de ce type disponibles. Pas besoin d'écrire le vôtre. Voir ma réponse sur cette page.
Basil Bourque
108

En fait, LinkedHashMap fait exactement ce que vous voulez. Vous devez remplacer la removeEldestEntryméthode.

Exemple pour une file d'attente de 10 éléments maximum:

  queue = new LinkedHashMap<Integer, String>()
  {
     @Override
     protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest)
     {
        return this.size() > 10;   
     }
  };

Si "removeEldestEntry" renvoie true, l'entrée la plus ancienne est supprimée de la carte.

Mavrik
la source
7
cela ne fait pas vraiment ce que fait une file d'attente, comment puis-je récupérer le plus récent. objet?
Alex
69

Oui, deux

De ma propre question en double avec cette réponse correcte , j'ai appris deux:


J'ai fait un usage productif de la goyave EvictingQueue, j'ai bien travaillé.

Pour instancier un EvictingQueueappel, la méthode de fabrique statique createet spécifiez votre taille maximale.

EvictingQueue< Person > people = com.google.common.collect.EvictingQueue.create( 100 ) ;  // Set maximum size to 100. 
Basil Bourque
la source
... et si vous ne pouvez pas utiliser Commons Collection 4.0, CircularFifoBuffer semble être similaire à CircularFifoQueue dans la version 3.0.
Sridhar Sarnobat
CircularFifoQueuelien est mort, utilisez plutôt commons.apache.org/proper/commons-collections/apidocs/org/...
user7294900
@ user7294900 Merci, lien corrigé. Pour info, Stack Overflow vous invite à apporter vous-même de telles modifications directement à une réponse. Tout le monde peut modifier, pas seulement l'auteur original. Stack Overflow est destiné à ressembler davantage à Wikipedia à cet égard.
Basil Bourque
@BasilBourque oui, mais de telles modifications peuvent être rejetées même par moi lorsque je change de lien, c'est une zone grise
user7294900
18

Je viens d'implémenter une file d'attente de taille fixe de cette façon:

public class LimitedSizeQueue<K> extends ArrayList<K> {

    private int maxSize;

    public LimitedSizeQueue(int size){
        this.maxSize = size;
    }

    public boolean add(K k){
        boolean r = super.add(k);
        if (size() > maxSize){
            removeRange(0, size() - maxSize);
        }
        return r;
    }

    public K getYoungest() {
        return get(size() - 1);
    }

    public K getOldest() {
        return get(0);
    }
}
Roar Skullestad
la source
1
Ça devrait êtreremoveRange(0, size() - maxSize)
Ahmed Hegazy
@AhmedHegazy removeRange (0, size () - maxSize - 1) est correct
Ashish Doneriya
Je suis d'accord avec Amhed ci-dessus. Supprimez le - 1. Sinon, à la capacité maximale, vous vous retrouverez avec un tableau qui est maxSize + 1 puisque nous parlons de 0 basé. Par exemple. Si maxSize = 50, lors de l'ajout d'un nouvel objet, la formule removeRange dans le message d'origine sera 51 - 50 - 1 = 0 (c'est-à-dire rien de supprimé).
Etep
8

C'est ce que j'ai fait avec Queueenveloppé avec LinkedList, il est de taille fixe que je donne ici est 2;

public static Queue<String> pageQueue;

pageQueue = new LinkedList<String>(){
            private static final long serialVersionUID = -6707803882461262867L;

            public boolean add(String object) {
                boolean result;
                if(this.size() < 2)
                    result = super.add(object);
                else
                {
                    super.removeFirst();
                    result = super.add(object);
                }
                return result;
            }
        };


....
TMarket.pageQueue.add("ScreenOne");
....
TMarket.pageQueue.add("ScreenTwo");
.....
Berkay Turanci
la source
4

Je pense que ce que vous décrivez est une file d'attente circulaire. Voici un exemple et voici une meilleure une


la source
4

Cette classe fait le travail en utilisant la composition au lieu de l'héritage (autres réponses ici), ce qui supprime la possibilité de certains effets secondaires (comme couvert par Josh Bloch dans Essential Java). Le rognage de la LinkedList sous-jacente se produit sur les méthodes add, addAll et offer.

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class LimitedQueue<T> implements Queue<T>, Iterable<T> {

    private final int limit;
    private final LinkedList<T> list = new LinkedList<T>();

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

    private boolean trim() {
        boolean changed = list.size() > limit;
        while (list.size() > limit) {
            list.remove();
        }
        return changed;
    }

    @Override
    public boolean add(T o) {
        boolean changed = list.add(o);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        return list.contains(o);
    }

    @Override
    public Iterator<T> iterator() {
        return list.iterator();
    }

    @Override
    public Object[] toArray() {
        return list.toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return list.toArray(a);
    }

    @Override
    public boolean remove(Object o) {
        return list.remove(o);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return list.containsAll(c);
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        boolean changed = list.addAll(c);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return list.removeAll(c);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return list.retainAll(c);
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public boolean offer(T e) {
        boolean changed = list.offer(e);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public T remove() {
        return list.remove();
    }

    @Override
    public T poll() {
        return list.poll();
    }

    @Override
    public T element() {
        return list.element();
    }

    @Override
    public T peek() {
        return list.peek();
    }
}
Dave Moten
la source
3
public class CircularQueue<E> extends LinkedList<E> {
    private int capacity = 10;

    public CircularQueue(int capacity){
        this.capacity = capacity;
    }

    @Override
    public boolean add(E e) {
        if(size() >= capacity)
            removeFirst();
        return super.add(e);
    }
}

Utilisation et résultat du test:

public static void main(String[] args) {
    CircularQueue<String> queue = new CircularQueue<>(3);
    queue.add("a");
    queue.add("b");
    queue.add("c");
    System.out.println(queue.toString());   //[a, b, c]

    String first = queue.pollFirst();       //a
    System.out.println(queue.toString());   //[b,c]

    queue.add("d");
    queue.add("e");
    queue.add("f");
    System.out.println(queue.toString());   //[d, e, f]
}
Léon
la source
0

Sonne comme une liste ordinaire où la méthode add contient un extrait de code supplémentaire qui tronque la liste si elle devient trop longue.

Si cela est trop simple, vous devrez probablement modifier la description de votre problème.

Thorbjørn Ravn Andersen
la source
En fait, il aurait besoin de supprimer le premier élément (c'est-à-dire le plus ancien), la troncature supprimerait le dernier élément. Toujours pratique avec une LinkedList.
MAK
0

Les exigences que vous avez qui vous ont amené à poser cette question ne sont pas très claires. Si vous avez besoin d'une structure de données de taille fixe, vous pouvez également envisager différentes stratégies de mise en cache. Cependant, comme vous avez une file d'attente, ma meilleure supposition est que vous recherchez un type de fonctionnalité de routeur. Dans ce cas, j'irais avec un tampon en anneau: un tableau qui a un premier et un dernier index. Chaque fois qu'un élément est ajouté, vous incrémentez simplement le dernier index d'élément, et lorsqu'un élément est supprimé, incrémentez le premier index d'élément. Dans les deux cas, l'ajout est effectué en fonction de la taille du tableau, et veillez à incrémenter l'autre index si nécessaire, c'est-à-dire lorsque la file d'attente est pleine ou vide.

De plus, s'il s'agit d'une application de type routeur, vous pouvez également essayer un algorithme tel que Random Early Dropping (RED), qui supprime des éléments de la file d'attente de manière aléatoire avant même qu'elle ne se remplisse. Dans certains cas, RED s'est avéré avoir de meilleures performances globales que la méthode simple permettant à la file d'attente de se remplir avant de tomber.

JaakkoK
la source
0

En fait, vous pouvez écrire votre propre impl basé sur LinkedList, c'est assez simple, il suffit de remplacer la méthode add et de faire le personnel.

Mike
la source
0

Je pense que la meilleure réponse correspondante vient de cette autre question .

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.

Diego
la source
0

Une solution simple, ci-dessous est une file d'attente de "String"

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

queue.put(queueKeysCounter++, "My String");
queueKeysCounter %= QUEUE_SIZE;

Notez que cela ne maintiendra pas l'ordre des éléments dans la file d'attente, mais remplacera l'entrée la plus ancienne.

M. Usman Khan
la source
0

Comme indiqué dans les POO, nous devrions préférer la composition à l'héritage

Voici ma solution en gardant cela à l'esprit.

package com.choiceview;

import java.util.ArrayDeque;

class Ideone {
    public static void main(String[] args) {
        LimitedArrayDeque<Integer> q = new LimitedArrayDeque<>(3);
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println(q);

        q.add(4);
        // First entry ie 1 got pushed out
        System.out.println(q);
    }
}

class LimitedArrayDeque<T> {

    private int maxSize;
    private ArrayDeque<T> queue;

    private LimitedArrayDeque() {

    }

    public LimitedArrayDeque(int maxSize) {
        this.maxSize = maxSize;
        queue = new ArrayDeque<T>(maxSize);
    }

    public void add(T t) {
        if (queue.size() == maxSize) {
            queue.removeFirst();
        }
        queue.add(t);
    }

    public boolean remove(T t) {
        return queue.remove(t);
    }

    public boolean contains(T t) {
        return queue.contains(t);
    }

    @Override
    public String toString() {
        return queue.toString();
    }
}
Abhishek
la source