Cola de tamaño limitado que contiene los últimos N elementos en Java

197

Una pregunta muy simple y rápida sobre las bibliotecas de Java: ¿hay una clase preparada que implemente una Queuecon un tamaño máximo fijo?

Por supuesto, es trivial implementarlo manualmente:

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

Por lo que veo, no hay una implementación estándar en las stdlibs de Java, pero ¿puede haber una en Apache Commons o algo así?

Gato gris
fuente
1
Relacionados stackoverflow.com/questions/590069/...
andersoj
9
@Kevin: Eres tan bromista.
Mark Peters
55
Personalmente, no presentaría otra biblioteca si este fuera el único uso de esta biblioteca ...
Nicolas Bousquet
2
@Override public boolean add (PropagationTask t) {boolean Added = super.add (t); while (agregado && size ()> limit) {super.remove (); } return añadido; }
Renaud
66
Advertencia: el código en cuestión, aunque aparentemente funciona, podría ser contraproducente. Existen métodos adicionales que pueden agregar más elementos a la cola (como addAll ()) que ignoran esta verificación de tamaño. Para obtener más detalles, consulte Eficaz segunda edición de Java - Artículo 16: favorecer la composición sobre la herencia
Diego

Respuestas:

171

Apache commons collections 4 tiene un CircularFifoQueue <> que es lo que está buscando. Citando al javadoc:

CircularFifoQueue es una cola de primero en entrar, primero en salir con un tamaño fijo que reemplaza su elemento más antiguo si está lleno.

    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 está utilizando una versión anterior de las colecciones comunes de Apache (3.x), puede utilizar el CircularFifoBuffer, que es básicamente lo mismo sin genéricos.

Actualización : respuesta actualizada después del lanzamiento de la versión 4 de colecciones comunes que admite genéricos.

Asaf
fuente
1
Es un buen candidato, pero, por desgracia, no usa genéricos :(
GreyCat
¡Gracias! Parece que esa es la alternativa más viable por ahora :)
GreyCat
3
Vea esta otra respuesta para el enlace EvictingQueueagregado a Google Guava versión 15 alrededor de 2013-10.
Basil Bourque
¿Hay alguna devolución de llamada cuando el elemento se desaloja de la cola debido a la adición a la cola completa?
ed22
una "Cola Circular" es simplemente una implementación que satisface la pregunta. Pero la pregunta no se beneficia directamente de las principales diferencias de una cola circular, es decir, no tener que liberar / reasignar cada depósito en cada adición / eliminación.
simpleuser
90

Guava ahora tiene un EvictingQueue , una cola sin bloqueo que desaloja automáticamente los elementos del encabezado de la cola cuando intenta agregar nuevos elementos a la cola y está llena.

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
fuente
Esto debería ser interesante de usar una vez que salga oficialmente.
Asaf
Aquí está la fuente: code.google.com/p/guava-libraries/source/browse/guava/src/com/… - parece que sería fácil copiar y compilar con las versiones actuales de Guava
Tom Carchrae
1
Actualización: esta clase se lanzó oficialmente con Google Guava en la versión 15 , alrededor de 2013-10.
Basil Bourque
1
@MaciejMiklas La pregunta pide un FIFO, EvictingQueuees un FIFO. En caso de duda, pruebe este programa: Queue<Integer> fifo = EvictingQueue.create(2); fifo.add(1); fifo.add(2); fifo.add(3); System.out.println(fifo); Observe el resultado:[2, 3]
kostmo
2
Esta es ahora la respuesta correcta. No está claro en la documentación, pero EvictingQueue es un FIFO.
Michael Böckling
11

Me gusta la solución @FractalizeR. ¡Pero además mantendría y devolvería el valor 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
fuente
1
Hasta donde puedo ver, FractalizeR no ha proporcionado ninguna solución, solo editó la pregunta. "Solución" dentro de la pregunta no es una solución, porque la pregunta era sobre el uso de alguna clase en la biblioteca estándar o semi-estándar, no en la suya propia.
GreyCat
3
Cabe señalar que esta solución no es segura para subprocesos
Konrad Morawski
77
@KonradMorawski toda la clase LinkedList no es segura para subprocesos de todos modos, por lo que su comentario no tiene sentido en este contexto.
Renaud
La seguridad de los hilos de @RenaudBlue es una preocupación válida (si a menudo se pasa por alto), por lo que no creo que el comentario no tenga sentido. y recordar que LinkedListno es seguro para subprocesos tampoco sería inútil. En el contexto de esta pregunta, el requisito específico de OP hace que sea particularmente importante que la adición de un elemento se realice como una operación atómica. en otras palabras, el riesgo de no garantizar la atomicidad sería mayor que en el caso de una LinkedList regular.
Konrad Morawski
44
Se rompe tan pronto como alguien llama en su add(int,E)lugar. Y si addAllfunciona según lo previsto, depende de detalles de implementación no especificados. Es por eso que debería preferir la delegación sobre la herencia ...
Holger
6

Usar composición no se extiende (sí, me refiero a extensiones, como en una referencia a la palabra clave extend en java y sí, esto es herencia). La composición es superior porque protege completamente su implementación, permitiéndole cambiarla sin afectar a los usuarios de su clase.

Recomiendo probar algo como esto (estoy escribiendo directamente en esta ventana, así que el comprador tenga cuidado con los errores de sintaxis):

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

Una mejor opción (basada en la respuesta de Asaf) podría ser envolver el Apache Collections CircularFifoBuffer con una clase genérica. Por ejemplo:

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
fuente
2
1 si se explica por qué composición es una mejor opción (que no sea "prefieren composición sobre la herencia) ... y hay una muy buena razón
kdgregory
1
La composición es una mala elección para mi tarea aquí: significa al menos dos veces la cantidad de objetos => al menos dos veces más a menudo recolección de basura. Utilizo grandes cantidades (decenas de millones) de estas colas de tamaño limitado, por ejemplo: Map <Long, LimitedSizeQueue <String>>.
GreyCat
@GreyCat - Supongo que no has visto cómo LinkedListse implementa, entonces. El objeto adicional creado como un contenedor alrededor de la lista será bastante menor, incluso con "decenas de millones" de instancias.
kdgregory
Iba por "reduce el tamaño de la interfaz", pero "protege la implementación" es más o menos lo mismo. Cualquiera de las dos responde las quejas de Mark Peter sobre el enfoque del OP.
kdgregory
4

Lo único que sé que tiene espacio limitado es la interfaz BlockingQueue (que, por ejemplo, está implementada por la clase ArrayBlockingQueue), pero no eliminan el primer elemento si está lleno, sino que bloquean la operación de colocación hasta que el espacio esté libre (eliminado por otro hilo )

Que yo sepa, su implementación trivial es la forma más fácil de obtener ese comportamiento.

flolo
fuente
Ya he examinado las clases Java stdlib y, lamentablemente, BlockingQueueno es una respuesta. ¿He pensado en otras bibliotecas comunes, como Apache Commons, las bibliotecas de Eclipse, Spring, las adiciones de Google, etc.?
GreyCat
3

Puede usar un MinMaxPriorityQueue de Google Guava , de javadoc:

Se puede configurar una cola de prioridad min-max con un tamaño máximo. Si es así, cada vez que el tamaño de la cola excede ese valor, la cola elimina automáticamente su elemento más grande de acuerdo con su comparador (que podría ser el elemento que se acaba de agregar). Esto es diferente de las colas acotadas convencionales, que bloquean o rechazan nuevos elementos cuando están llenos.

Moritz
fuente
3
¿Entiendes qué es una cola prioritaria y cómo difiere del ejemplo del OP?
kdgregory
2
@ Mark Peters - Simplemente no sé qué decir. Claro, puede hacer que una cola prioritaria se comporte como una cola quince. También podría hacer que un Mapcomportamiento como a List. Pero ambas ideas muestran una completa incomprensión de algoritmos y diseño de software.
kdgregory
2
@Mark Peters: ¿no son todas las preguntas sobre SO sobre una buena manera de hacer algo?
jtahlborn
3
@jtahlborn: Claramente no (código golf), pero incluso si lo fueran, bueno no es un criterio en blanco y negro. Para un determinado proyecto, bueno podría significar "más eficiente", para otro podría significar "más fácil de mantener" y para otro, podría significar "la menor cantidad de código con las bibliotecas existentes". Todo eso es irrelevante ya que nunca dije que era una buena respuesta. Solo dije que puede ser una solución sin demasiado esfuerzo. Convertir MinMaxPriorityQueuea lo que el OP quiere es más trivial que modificar a LinkedList(el código del OP ni siquiera se acerca).
Mark Peters
3
Tal vez ustedes están examinando mi elección de palabras "en la práctica que seguramente será suficiente". No quise decir que esta solución seguramente sería suficiente para el problema del OP o en general. Me refería a la elección de un longtipo de cursor descendente como dentro de mi propia sugerencia, diciendo que sería lo suficientemente amplio en la práctica, aunque en teoría podría agregar más de 2 ^ 64 objetos a esta cola, en cuyo punto la solución se rompería .
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;
    }
}
usuario590444
fuente
3
La pregunta se refería a las clases en las bibliotecas de clases de colección populares, no a las propias: la "solución" minimalista de elaboración casera ya se proporcionaba en cuestión.
GreyCat
2
eso no importa google, encuentre esta página también en otras consultas =)
user590444
1
Esta respuesta apareció en la cola de revisión de baja calidad, presumiblemente porque no proporciona ninguna explicación del código. Si este código responde la pregunta, considere agregar un texto adicional que explique el código en su respuesta. De esta manera, es mucho más probable que obtenga más votos positivos y ayude al interlocutor a aprender algo nuevo.
lmo