Kolejka o ograniczonym rozmiarze, która przechowuje ostatnie N elementów w Javie


197

Bardzo proste i szybkie pytanie o biblioteki Java: czy istnieje gotowa klasa, która implementuje a Queueo ustalonym maksymalnym rozmiarze - tzn. Zawsze pozwala na dodawanie elementów, ale po cichu usunie elementy główne, aby pomieścić miejsce dla nowo dodanych elementów.

Oczywiście wdrożenie go ręcznie jest trywialne:

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

O ile mi wiadomo, nie ma standardowej implementacji w stdlibs Java, ale może jest taka w Apache Commons czy coś takiego?



9
@Kevin: Jesteś taki złośliwy.
Mark Peters

5
Osobiście nie wprowadziłbym innej biblioteki, gdyby to jedyne zastosowanie tej biblioteki ...
Nicolas Bousquet

2
@Override public boolean add (PropagationTask t) {boolean added = super.add (t); while (dodano && size ()> limit) {super.remove (); } powrót dodano; }
Renaud

6
Ostrzeżenie: kod, o którym mowa, chociaż najwyraźniej działa, może się nie udać. Istnieją dodatkowe metody, które mogą dodać więcej elementów do kolejki (takie jak addAll ()), które ignorują to sprawdzenie rozmiaru. Aby uzyskać więcej informacji, zobacz Effective Java 2nd Edition - Pozycja 16: Preferuj kompozycję nad dziedziczeniem
Diego

Odpowiedzi:


171

Kolekcje Apache commons 4 mają CircularFifoQueue <>, czego szukasz. Cytując javadoc:

CircularFifoQueue to kolejka „pierwsze weszło pierwsze wyszło” o stałym rozmiarze, która zastępuje najstarszy element, jeśli jest pełny.

    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]

Jeśli używasz starszej wersji wspólnych kolekcji Apache (3.x), możesz użyć CircularFifoBuffer, który jest zasadniczo taki sam bez generycznych.

Aktualizacja : zaktualizowano odpowiedź po wydaniu wspólnej kolekcji w wersji 4, która obsługuje generyczne.


1
To jest dobrym kandydatem, ale, niestety, nie używa rodzajowych :(
GreyCat

Dzięki! Wygląda na to, że jest to obecnie najbardziej realna alternatywa :)
GreyCat

3
Zobacz tę inną odpowiedź, aby uzyskać link EvictingQueuedo Google Guava w wersji 15 około 2013-10.
Basil Bourque

Czy istnieje wywołanie zwrotne, gdy element jest usuwany z kolejki z powodu dodania do pełnej kolejki?
ed22

„kolejka cykliczna” to tylko jedna implementacja, która spełnia pytanie. Ale pytanie nie korzysta bezpośrednio z głównych różnic w kolejce kołowej, tj. Nie ma potrzeby zwalniania / ponownego przydzielania każdego segmentu przy każdym dodawaniu / usuwaniu.
simpleuser

90

Guava ma teraz EvictingQueue , kolejkę nieblokującą, która automatycznie eksmituje elementy z głowy kolejki podczas próby dodania nowych elementów do kolejki i jest pełna.

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]

Powinno to być interesujące w użyciu, gdy wyjdzie oficjalnie.
Asaf

Oto źródło: code.google.com/p/guava-libraries/source/browse/guava/src/com/… - wygląda na to, że łatwo byłoby skopiować i skompilować z aktualnymi wydaniami Guava
Tom Carchrae

1
Aktualizacja: Ta klasa została oficjalnie wydana wraz z Google Guava w wersji 15 , około 2013-10.
Basil Bourque,

1
@MaciejMiklas Pytanie dotyczy FIFO, EvictingQueueto FIFO. W razie wątpliwości wypróbuj ten program: Queue<Integer> fifo = EvictingQueue.create(2); fifo.add(1); fifo.add(2); fifo.add(3); System.out.println(fifo); Obserwuj wynik:[2, 3]
kostmo

2
To jest teraz poprawna odpowiedź. Jest to trochę niejasne z dokumentacji, ale EvictingQueue jest FIFO.
Michael Böckling,

11

Lubię rozwiązanie @FractalizeR. Ale dodatkowo zatrzymałbym i zwrócił wartość z 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;
    }
}

1
O ile widzę, FractalizeR nie dostarczył żadnego rozwiązania, jedynie zredagował pytanie. „Rozwiązanie” w pytaniu nie jest rozwiązaniem, ponieważ pytanie dotyczyło użycia pewnej klasy w bibliotece standardowej lub pół-standardowej, a nie rozwijania własnej.
GreyCat 17.01.2013

3
Należy zauważyć, że to rozwiązanie nie jest bezpieczne dla wątków
Konrad Morawski,

7
@KonradMorawski cała klasa LinkedList i tak nie jest bezpieczna dla wątków, więc twój komentarz jest bezcelowy w tym kontekście!
Renaud,

Bezpieczeństwo wątków @RenaudBlue jest ważną kwestią (jeśli często pomijaną), więc nie sądzę, aby komentarz był bezcelowy. a przypomnienie, że LinkedListnie jest bezpieczne wątek, również nie byłoby sensu. w kontekście tego pytania szczególne wymaganie OP sprawia, że ​​szczególnie ważne jest, aby dodanie elementu odbywało się jako operacja atomowa. innymi słowy, ryzyko braku zapewnienia atomowości byłoby większe niż w przypadku zwykłej LinkedList.
Konrad Morawski,

4
Łamie się, gdy tylko ktoś zadzwoni add(int,E). To, czy addAlldziała zgodnie z przeznaczeniem, zależy od nieokreślonych szczegółów implementacji. Właśnie dlatego powinieneś preferować przekazanie
Holger,

6

Użyj kompozycji nie rozszerza (tak mam na myśli rozszerzenie, ponieważ w odniesieniu do słowa kluczowego extends w Javie i tak jest to dziedziczenie). Kompozycja jest lepsza, ponieważ całkowicie chroni twoją implementację, pozwalając ci na zmianę implementacji bez wpływu na użytkowników twojej klasy.

Polecam wypróbowanie czegoś takiego (piszę bezpośrednio w tym oknie, więc kupujący uważaj na błędy składniowe):

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

Lepszą opcją (na podstawie odpowiedzi Asafa) może być owinięcie CircularFifoBuffer kolekcji Apache klasą ogólną. Na przykład:

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
}

2
+1, jeśli wyjaśnisz, dlaczego kompozycja jest lepszym wyborem (innym niż „wolę kompozycję niż dziedziczenie) ... i istnieje bardzo dobry powód
kdgregory

1
Kompozycja jest złym wyborem dla mojego zadania tutaj: oznacza co najmniej dwukrotność liczby obiektów => co najmniej dwa razy częściej odśmiecanie. Używam dużych ilości (dziesiątki milionów) tych kolejek o ograniczonych rozmiarach, takich jak: Map <Long, LimitedSizeQueue <String>>.
GreyCat,

@GreyCat - Rozumiem, że nie spojrzałeś na LinkedListto, jak to jest realizowane. Dodatkowy obiekt utworzony jako opakowanie wokół listy będzie dość niewielki, nawet przy „dziesiątkach milionów” instancji.
kdgregory

Chciałem „zmniejszyć rozmiar interfejsu”, ale „osłania implementację” to prawie to samo. Obie odpowiedzi dotyczą skarg Marka Petera na podejście PO.
kdgregory 16.04.11

4

Jedyne, co wiem, że ma ograniczoną przestrzeń to interfejs BlockingQueue (który jest np. Zaimplementowany przez klasę ArrayBlockingQueue) - ale nie usuwają pierwszego elementu, jeśli są wypełnione, ale zamiast tego blokują operację put, dopóki przestrzeń nie będzie wolna (usuwana przez inny wątek ).

Według mojej wiedzy trywialna implementacja jest najprostszym sposobem na uzyskanie takiego zachowania.


Przeglądałem już klasy stdlib Java i niestety BlockingQueuenie jest to odpowiedź. Myślałem o innych popularnych bibliotekach, takich jak Apache Commons, biblioteki Eclipse, Spring, dodatki Google itp.?
GreyCat,

3

Możesz użyć MinMaxPriorityQueue z Google Guava , z javadoc:

Kolejka priorytetowa min. Maks. Może być skonfigurowana z maksymalnym rozmiarem. Jeśli tak, za każdym razem, gdy rozmiar kolejki przekracza tę wartość, kolejka automatycznie usuwa swój największy element zgodnie z jego komparatorem (którym może być właśnie dodany element). Różni się to od konwencjonalnych ograniczonych kolejek, które blokują lub odrzucają nowe elementy, gdy są pełne.


3
Czy rozumiesz, co to jest kolejka priorytetowa i czym różni się od przykładu PO?
kdgregory

2
@Mark Peters - Po prostu nie wiem co powiedzieć. Jasne, że kolejka priorytetowa może zachowywać się jak kolejka fifo. Możesz także Mapzachowywać się jak List. Ale oba pomysły pokazują całkowite niezrozumienie algorytmów i projektowania oprogramowania.
kdgregory

2
@Mark Peters - czy nie każde pytanie w SO dotyczy dobrego sposobu na zrobienie czegoś?
jtahlborn,

3
@jtahlborn: Najwyraźniej nie (code golf), ale nawet gdyby tak było, dobro nie jest kryterium czarno-białym. Dla pewnego projektu dobro może oznaczać „najbardziej wydajny”, dla innego może oznaczać „najłatwiejszy w utrzymaniu”, a dla innego może oznaczać „najmniejszą ilość kodu w istniejących bibliotekach”. Wszystko to jest bez znaczenia, ponieważ nigdy nie powiedział, że ten był dobra odpowiedź. Powiedziałem tylko, że może to być rozwiązanie bez większego wysiłku. Przekształcenie a MinMaxPriorityQueuew to, czego chce OP, jest bardziej trywialne niż modyfikowanie a LinkedList(kod OP nawet się nie zbliża).
Mark Peters

3
Może badacie mój wybór słów „w praktyce, które prawie na pewno wystarczą”. Nie miałem na myśli, że takie rozwiązanie prawie na pewno wystarczyłoby na problem PO lub ogólnie. Odniosłem się do wyboru zejścia longjako typu kursora w ramach mojej własnej sugestii, mówiąc, że będzie on wystarczająco szeroki w praktyce, nawet jeśli teoretycznie można dodać więcej niż 2 ^ 64 obiektów do tej kolejki, w którym to momencie rozwiązanie się załamie .
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;
    }
}

3
Pytanie dotyczyło klas w popularnych bibliotekach klas, a nie własnych - minimalistyczne „rozwiązanie” homebrew już było kwestionowane.
GreyCat,

2
to nie ma znaczenia, znajdź tę stronę także w innych zapytaniach =)
user590444,

1
Ta odpowiedź pojawiła się w kolejce przeglądu niskiej jakości, prawdopodobnie dlatego, że nie podałeś żadnego wyjaśnienia kodu. Jeśli ten kod odpowiada na pytanie, rozważ dodanie tekstu wyjaśniającego kod w swojej odpowiedzi. W ten sposób znacznie częściej zyskujesz więcej głosów pozytywnych - i pomagasz pytającemu dowiedzieć się czegoś nowego.
lmo
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.