Existe uma fila de tamanho fixo que remove elementos excessivos?

127

Eu preciso de uma fila com um tamanho fixo. Quando adiciono um elemento e a fila está cheia, ele deve remover automaticamente o elemento mais antigo.

Existe uma implementação existente para isso em Java?

c0d3x
fonte

Respostas:

19

Não há implementação existente no Java Language and Runtime. Todas as filas estendem o AbstractQueue e seu documento afirma claramente que a adição de um elemento a uma fila completa sempre termina com uma exceção. Seria melhor (e bastante simples) agrupar uma Fila em uma classe própria para ter a funcionalidade necessária.

Mais uma vez, como todas as filas são filhos do AbstractQueue, basta usá-lo como seu tipo de dados interno e você deverá ter uma implementação flexível em execução praticamente em nenhum momento :-)

ATUALIZAR:

Conforme descrito abaixo, existem duas implementações abertas disponíveis (essa resposta é bastante antiga, pessoal!), Consulte esta resposta para obter detalhes.

Moritz
fonte
4
Use Fila em vez de AbstractQueue ... pode haver filas que implementam a interface, mas não estendem a classe abstrata.
TofuBeer
1
No Python, você pode usar a collection.dequecom um especificado maxlen.
Jonas Gröger 10/02
2
ATUALIZAÇÃO Agora existem duas dessas classes disponíveis. Não há necessidade de escrever o seu próprio. Veja minha resposta nesta página.
Basil Bourque
107

Na verdade, o LinkedHashMap faz exatamente o que você deseja. Você precisa substituir o removeEldestEntrymétodo

Exemplo para uma fila com no máximo 10 elementos:

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

Se "removeEldestEntry" retornar true, a entrada mais antiga será removida do mapa.

Mavrik
fonte
7
na verdade, isso não faz o que uma fila faz, como posso recuperar o mais novo. objeto?
Alex
69

Sim dois

Da minha própria pergunta duplicada com esta resposta correta , aprendi de duas:


Fiz uso produtivo da goiaba EvictingQueue, funcionou bem.

Para instanciar uma EvictingQueuechamada, o método estático de fábrica createe especifique seu tamanho máximo.

EvictingQueue< Person > people = com.google.common.collect.EvictingQueue.create( 100 ) ;  // Set maximum size to 100. 
Basil Bourque
fonte
... e se você não pode usar o Commons Collection 4.0, o CircularFifoBuffer parece ser semelhante ao CircularFifoQueue na v 3.0.
Sridhar Sarnobat
CircularFifoQueueo link está inoperante, use commons.apache.org/proper/commons-collections/apidocs/org/…
user7294900
@ user7294900 Obrigado, link corrigido. Para sua informação, o Stack Overflow convida você para fazer essas edições diretamente em uma resposta. Qualquer pessoa pode editar, não apenas o autor original. O Stack Overflow destina-se mais à Wikipedia a esse respeito.
Basil Bourque 22/10
@BasilBourque sim, mas essas edições podem ser rejeitadas, mesmo por mim, ao alterar os links, é uma área cinza #
user7294900
18

Acabei de implementar uma fila de tamanho fixo desta maneira:

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
fonte
1
Deve serremoveRange(0, size() - maxSize)
Ahmed Hegazy
@AhmedHegazy removeRange (0, size () - maxSize - 1) está correto #
Ashish Doneriya
Eu concordo com Amhed acima. Remova o - 1. Caso contrário, na capacidade máxima, você terminará com uma matriz que é maxSize + 1, pois estamos falando de 0 com base. Por exemplo. Se maxSize = 50, ao adicionar um novo objeto, a fórmula removeRange na postagem original será 51 - 50 - 1 = 0 (ou seja, nada foi removido).
Etep
8

Isto é o que eu fiz com Queueembrulhado LinkedList, é de tamanho fixo que eu cito aqui é 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 Turancı
fonte
4

Eu acho que o que você está descrevendo é uma fila circular. Aqui está um exemplo e aqui é um melhor um


fonte
4

Essa classe faz o trabalho usando composição em vez de herança (outras respostas aqui), o que remove a possibilidade de certos efeitos colaterais (conforme coberto por Josh Bloch no Essential Java). O corte do LinkedList subjacente ocorre nos métodos add, addAll e 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
fonte
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);
    }
}

Uso e resultado do teste:

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]
}
Leon
fonte
0

Soa como uma lista comum, em que o método add contém um trecho extra que trunca a lista se ela for muito longa.

Se isso for muito simples, você provavelmente precisará editar a descrição do seu problema.

Thorbjørn Ravn Andersen
fonte
Na verdade, ele precisaria excluir o primeiro elemento (ou seja, o mais antigo), o truncamento removeria o último elemento. Ainda prático com um LinkedList.
MAK
0

Não está claro quais requisitos você o levou a fazer essa pergunta. Se você precisar de uma estrutura de dados de tamanho fixo, também poderá procurar políticas de armazenamento em cache diferentes. No entanto, como você tem uma fila, meu melhor palpite é que você está procurando algum tipo de funcionalidade do roteador. Nesse caso, eu usaria um buffer de anel: uma matriz que possui um primeiro e último índice. Sempre que um elemento é adicionado, você apenas incrementa o índice do último elemento e, quando um elemento é removido, incrementa o índice do primeiro elemento. Nos dois casos, a adição é realizada modulando o tamanho da matriz e certifique-se de incrementar o outro índice quando necessário, ou seja, quando a fila estiver cheia ou vazia.

Além disso, se for um aplicativo do tipo roteador, convém experimentar um algoritmo como o Random Early Dropping (RED), que remove elementos da fila aleatoriamente antes mesmo de ser preenchido. Em alguns casos, verificou-se que o RED possui um desempenho geral melhor do que o método simples de permitir que a fila se encha antes de cair.

JaakkoK
fonte
0

Na verdade, você pode escrever seu próprio impl com base no LinkedList, é bastante direto, basta substituir o método add e fazer a equipe.

Mike
fonte
0

Eu acho que a melhor resposta correspondente é dessa outra pergunta .

O Apache commons collections 4 possui um CircularFifoQueue, que é o que você está procurando. Citando o javadoc:

CircularFifoQueue é uma fila primeiro a entrar, primeiro a sair, com um tamanho fixo que substitui o elemento mais antigo se estiver cheio.

Diego
fonte
0

Uma solução simples, abaixo, é uma fila de "String"

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

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

Observe que isso não manterá a ordem dos itens na fila, mas substituirá a entrada mais antiga.

M. Usman Khan
fonte
0

Como é recomendado nas OOPs, devemos preferir Composição ao invés de Herança

Aqui está minha solução tendo isso em mente.

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
fonte