setsize - setlayout java

¿Hay una cola de tamaño fijo que elimina elementos excesivos?

Question

Necesito una cola con un tamaño fijo. Cuando agrego un elemento y la cola está llena, debe eliminar automáticamente el elemento más antiguo.

¿Hay una implementación existente para esto en Java?

Answer 1

Si, dos

De mi propia pregunta duplicada con esta respuesta correcta , aprendí de dos:

• EvictingQueue en Google Guava
• CircularFifoQueue en Apache Commons

Hice un uso productivo de la Guava EvictingQueue , funcionó bien.

Answer 2

Acabo de implementar una cola de tamaño fijo de esta manera:

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 - 1);
        }
        return r;
    }

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

    public K getOldest() {
        return get(0);
    }
}

Answer 3

Creo que la mejor respuesta coincidente es de esta otra pregunta .

Apache commons collections 4 tiene un CircularFifoQueue que es lo que estás buscando. Citando el 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.

Answer 4

Creo que lo que describes es una cola circular. Aquí hay un example y aquí hay uno better

Answer 5

De hecho, puedes escribir tu propia impl basada en LinkedList, es bastante directa, simplemente anula el método add y haz el staff.

Answer 6

En realidad, LinkedHashMap hace exactamente lo que quieres. removeEldestEntry anular el método removeEldestEntry .

Ejemplo para una cola con un máximo de 10 elementos:

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

Si "removeEldestEntry" devuelve verdadero, la entrada más antigua se eliminará del mapa.

Answer 7

Esta clase hace el trabajo usando composición en lugar de herencia (otras respuestas aquí) que elimina la posibilidad de ciertos efectos secundarios (tal como lo cubre Josh Bloch en Essential Java). El recorte de LinkedList subyacente se produce en los métodos add, addAll y 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();
    }
}

Answer 8

Esto es lo que hice con Queue envuelto con LinkedList , es de tamaño fijo, lo que doy aquí es 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");
.....

Answer 9

No está del todo claro qué requisitos tienes que te hayan llevado a hacer esta pregunta. Si necesita una estructura de datos de tamaño fijo, es posible que también desee ver las diferentes políticas de almacenamiento en caché. Sin embargo, como tiene una cola, mi mejor opción es que está buscando algún tipo de funcionalidad de enrutador. En ese caso, iría con un buffer de anillo: un array que tiene un primer y último índice. Cada vez que se agrega un elemento, simplemente se incrementa el índice del último elemento, y cuando se elimina un elemento, se incrementa el índice del primer elemento. En ambos casos, la adición se realiza en función del tamaño de la matriz, y asegúrese de incrementar el otro índice cuando sea necesario, es decir, cuando la cola esté llena o vacía.

Además, si se trata de una aplicación de tipo enrutador, es posible que también desee experimentar con un algoritmo, como Alejamiento anticipado aleatorio (RED), que suelta elementos de la cola al azar incluso antes de que se llene. En algunos casos, se ha encontrado que RED tiene un mejor rendimiento general que el método simple de permitir que la cola se llene antes de caer.

Answer 10

No existe una implementación en Java Language y Runtime. Todas las colas extienden AbstractQueue , y su documento establece claramente que agregar un elemento a una cola completa siempre termina con una excepción. Sería mejor (y bastante simple) incluir una cola en una clase propia para tener la funcionalidad que necesita.

Una vez más, debido a que todas las colas son elementos secundarios de AbstractQueue, simplemente utilícela como su tipo de datos interno y debe tener una implementación flexible que se ejecute en prácticamente ningún momento :-)

ACTUALIZAR:

Como se describe a continuación, hay dos implementaciones abiertas disponibles (esta respuesta es bastante antigua, amigos!), Vea esta respuesta para más detalles.

Answer 11

Suena como una lista ordinaria donde el método de agregar contiene un fragmento adicional que trunca la lista si es demasiado larga.

Si eso es demasiado simple, entonces probablemente necesite editar la descripción de su problema.

Answer 12

También vea esta pregunta SO , o ArrayBlockingQueue (tenga cuidado con el bloqueo, esto puede ser no deseado en su caso).

Answer 13

Una solución simple, a continuación es una cola de "Cadena"

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

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

Tenga en cuenta que esto no mantendrá el orden de los elementos en la cola, pero reemplazará la entrada más antigua.