Warteschlange mit begrenzter Größe, die die letzten N Elemente in Java enthält

197

Eine sehr einfache und schnelle Frage zu Java-Bibliotheken: Gibt es eine vorgefertigte Klasse, die eine Queuemit einer festen maximalen Größe implementiert - dh sie ermöglicht immer das Hinzufügen von Elementen, entfernt jedoch stillschweigend Kopfelemente, um Platz für neu hinzugefügte Elemente zu schaffen.

Natürlich ist es trivial, es manuell zu implementieren:

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

Soweit ich sehe, gibt es keine Standardimplementierung in Java stdlibs, aber vielleicht gibt es eine in Apache Commons oder so?

GreyCat
quelle
9
@ Kevin: Du bist so ein Scherz.
Mark Peters
5
Persönlich würde ich keine andere Bibliothek vorstellen, wenn dies die einzige Verwendung dieser Bibliothek wäre ...
Nicolas Bousquet
2
@Override public boolean add (PropagationTask t) {boolean hinzugefügt = super.add (t); while (hinzugefügt && size ()> limit) {super.remove (); } return hinzugefügt; }
Renaud
6
Warnung: Der betreffende Code kann, obwohl er anscheinend funktioniert, nach hinten losgehen. Es gibt zusätzliche Methoden, mit denen der Warteschlange weitere Elemente hinzugefügt werden können (z. B. addAll ()), die diese Größenprüfung ignorieren. Weitere Informationen finden Sie unter Effektive Java 2nd Edition - Punkt 16: Komposition gegenüber Vererbung
Diego

Antworten:

171

Apache Commons Collections 4 verfügt über eine CircularFifoQueue <> der Sie suchen. Javadoc zitieren:

CircularFifoQueue ist eine First-In-First-Out-Warteschlange mit einer festen Größe, die das älteste Element ersetzt, wenn es voll ist.

    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]

Wenn Sie eine ältere Version der Apache Commons-Sammlungen (3.x) verwenden, können Sie den CircularFifoBuffer verwenden, der ohne Generika im Grunde dasselbe ist.

Update : Aktualisierte Antwort nach Veröffentlichung von Commons Collections Version 4, die Generika unterstützt.

Asaf
quelle
1
Das ist ein guter Kandidat, aber leider verwendet es keine Generika :(
GreyCat
Vielen Dank! Sieht so aus, als wäre dies die derzeit praktikabelste Alternative :)
GreyCat
3
In dieser anderen Antwort finden Sie einen Link EvictingQueuezu Google Guava Version 15 um 2013-10.
Basil Bourque
Wird ein Rückruf aufgerufen, wenn ein Element aufgrund der Hinzufügung zur vollständigen Warteschlange aus der Warteschlange entfernt wird?
ed22
Eine "Circular Queue" ist nur eine Implementierung, die die Frage erfüllt. Die Frage profitiert jedoch nicht direkt von den Hauptunterschieden einer kreisförmigen Warteschlange, dh sie muss nicht jeden Bucket bei jedem Hinzufügen / Löschen freigeben / neu zuweisen.
Simpleuser
90

Guava hat jetzt eine EvictingQueue , eine nicht blockierende Warteschlange, die automatisch Elemente aus dem Kopf der Warteschlange entfernt, wenn versucht wird, neue Elemente zur Warteschlange hinzuzufügen, und diese ist voll.

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
quelle
Dies sollte interessant sein, sobald es offiziell herauskommt.
Asaf
Hier ist die Quelle: code.google.com/p/guava-libraries/source/browse/guava/src/com/… - es sieht so aus, als wäre es einfach, mit aktuellen Versionen von Guava zu kopieren und zu kompilieren
Tom Carchrae
1
Update: Diese Klasse wurde offiziell mit Google Guava in Version 15 um 2013-10 veröffentlicht.
Basil Bourque
1
@MaciejMiklas Die Frage nach einem FIFO EvictingQueueist ein FIFO. Versuchen Queue<Integer> fifo = EvictingQueue.create(2); fifo.add(1); fifo.add(2); fifo.add(3); System.out.println(fifo); Sie im Zweifelsfall dieses Programm: Beachten Sie das Ergebnis:[2, 3]
kostmo
2
Dies ist jetzt die richtige Antwort. Es ist ein bisschen unklar aus der Dokumentation, aber EvictingQueue ist ein FIFO.
Michael Böckling
11

Ich mag die @ FractalizeR-Lösung. Aber ich würde zusätzlich den Wert von super.add (o) behalten und zurückgeben!

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
quelle
1
Soweit ich sehen kann, hat FractalizeR keine Lösung bereitgestellt, sondern nur die Frage bearbeitet. "Lösung" in der Frage ist keine Lösung, da es bei der Frage darum ging, eine Klasse in einer Standard- oder Semi-Standard-Bibliothek zu verwenden und nicht Ihre eigene zu rollen.
GreyCat
3
Es sollte darauf hingewiesen werden, dass diese Lösung nicht threadsicher ist
Konrad Morawski
7
@KonradMorawski Die gesamte LinkedList-Klasse ist sowieso nicht threadsicher, daher ist Ihr Kommentar in diesem Zusammenhang sinnlos!
Renaud
@RenaudBlue Thread-Sicherheit ist ein berechtigtes Anliegen (wenn oft übersehen), daher halte ich den Kommentar nicht für sinnlos. und daran zu erinnern, dass LinkedListThread nicht sicher ist, wäre auch nicht sinnlos. Im Zusammenhang mit dieser Frage ist es aufgrund der spezifischen Anforderungen von OP besonders wichtig, dass das Hinzufügen eines Elements als atomare Operation ausgeführt wird. Mit anderen Worten, das Risiko, die Atomizität nicht sicherzustellen, wäre größer als bei einer regulären LinkedList.
Konrad Morawski
4
Pausen, sobald add(int,E)stattdessen jemand anruft . Und ob es addAllwie beabsichtigt funktioniert, hängt von nicht spezifizierten Implementierungsdetails ab. Deshalb sollten Sie die Delegation der Vererbung vorziehen…
Holger
6

Verwenden Sie Komposition nicht erweitert (ja, ich meine erweitert, wie in einem Verweis auf das Schlüsselwort erweitert in Java und ja, dies ist Vererbung). Die Komposition ist besser, da sie Ihre Implementierung vollständig abschirmt und es Ihnen ermöglicht, die Implementierung zu ändern, ohne die Benutzer Ihrer Klasse zu beeinträchtigen.

Ich empfehle, so etwas zu versuchen (ich tippe direkt in dieses Fenster, damit der Käufer auf Syntaxfehler achtet):

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

Eine bessere Option (basierend auf der Antwort von Asaf) könnte darin bestehen, den Apache Collections CircularFifoBuffer mit einer generischen Klasse zu versehen. Beispielsweise:

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
quelle
2
+1, wenn Sie erklären, warum Komposition eine bessere Wahl ist (außer "Komposition gegenüber Vererbung bevorzugen") ... und es gibt einen sehr guten Grund
kdgregory
1
Komposition ist hier eine schlechte Wahl für meine Aufgabe: Sie bedeutet mindestens doppelt so viele Objekte => mindestens zweimal häufiger Müllabfuhr. Ich verwende große Mengen (zig Millionen) dieser Warteschlangen mit begrenzter Größe, wie folgt: Map <Long, LimitedSizeQueue <String >>.
GreyCat
@GreyCat - Ich nehme an, Sie haben sich nicht angesehen, wie LinkedListes implementiert wird. Das zusätzliche Objekt, das als Wrapper um die Liste erstellt wird, ist selbst bei "zig Millionen" Instanzen ziemlich klein.
kdgregory
Ich wollte "reduziert die Größe der Schnittstelle", aber "schirmt die Implementierung ab" ist so ziemlich das Gleiche. Beide beantworten Mark Peters Beschwerden über den Ansatz des OP.
kdgregory
4

Das einzige, was ich weiß, das nur über begrenzten Speicherplatz verfügt, ist die BlockingQueue-Schnittstelle (die z. B. von der ArrayBlockingQueue-Klasse implementiert wird). Sie entfernen jedoch nicht das erste Element, wenn es gefüllt ist, sondern blockieren die Put-Operation, bis Speicherplatz frei ist (von einem anderen Thread entfernt) ).

Meines Wissens ist Ihre triviale Implementierung der einfachste Weg, um ein solches Verhalten zu erreichen.

flolo
quelle
Ich habe bereits Java stdlib-Klassen durchsucht und bin leider BlockingQueuekeine Antwort. Ich habe an andere gängige Bibliotheken gedacht, wie Apache Commons, Eclipse-Bibliotheken, Spring-, Google-Ergänzungen usw.?
GreyCat
3

Sie können eine MinMaxPriorityQueue von Google Guava aus dem Javadoc verwenden:

Eine Warteschlange mit Min-Max-Priorität kann mit einer maximalen Größe konfiguriert werden. In diesem Fall entfernt die Warteschlange jedes Mal, wenn die Größe der Warteschlange diesen Wert überschreitet, automatisch das größte Element gemäß ihrem Komparator (möglicherweise das gerade hinzugefügte Element). Dies unterscheidet sich von herkömmlichen begrenzten Warteschlangen, die neue Elemente blockieren oder ablehnen, wenn sie voll sind.

moritz
quelle
3
Verstehen Sie, was eine Prioritätswarteschlange ist und wie sie sich vom Beispiel des OP unterscheidet?
kdgregory
2
@ Mark Peters - Ich weiß nur nicht, was ich sagen soll. Sicher, Sie können festlegen, dass sich eine Prioritätswarteschlange wie eine FIFO-Warteschlange verhält. Sie könnten sich auch Mapwie ein benehmen List. Beide Ideen zeigen jedoch ein völliges Unverständnis der Algorithmen und des Software-Designs.
kdgregory
2
@ Mark Peters - ist nicht jede Frage auf SO eine gute Möglichkeit, etwas zu tun?
Jtahlborn
3
@jtahlborn: Natürlich nicht (Code Golf), aber selbst wenn sie es wären, ist gut kein Schwarz-Weiß-Kriterium. Für ein bestimmtes Projekt bedeutet gut "am effizientesten", für ein anderes "am einfachsten zu warten" und für ein anderes "am wenigsten Code mit vorhandenen Bibliotheken". Alles , was da ich nie irrelevant sagte , dies ist eine gute Antwort. Ich habe nur gesagt, dass es eine Lösung ohne allzu großen Aufwand sein kann. Das Verwandeln von a MinMaxPriorityQueuein das, was das OP will, ist trivialer als das Ändern von a LinkedList(der Code des OP kommt nicht einmal nahe).
Mark Peters
3
Vielleicht untersucht ihr meine Wortwahl "in der Praxis wird das mit ziemlicher Sicherheit ausreichen". Ich meinte nicht, dass diese Lösung mit ziemlicher Sicherheit für das OP-Problem oder allgemein ausreichen würde. Ich bezog longmich in meinem eigenen Vorschlag auf die Wahl eines absteigenden Typs als Cursortyp und sagte, dass er in der Praxis ausreichend breit sein würde, obwohl theoretisch mehr als 2 ^ 64 Objekte zu dieser Warteschlange hinzugefügt werden könnten, an welchem ​​Punkt die Lösung zusammenbrechen würde .
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;
    }
}
user590444
quelle
3
Die Frage bezog sich auf Klassen in populären Sammlungsklassenbibliotheken, nicht auf eigene Rollen - eine minimalistische Homebrew- "Lösung" wurde bereits in Frage gestellt.
GreyCat
2
das ist egal google finde diese seite auch bei anderen
abfragen
1
Diese Antwort wurde in der Überprüfungswarteschlange mit geringer Qualität angezeigt, vermutlich weil Sie keine Erklärung für den Code angeben. Wenn dieser Code die Frage beantwortet, sollten Sie Text hinzufügen, der den Code in Ihrer Antwort erläutert. Auf diese Weise erhalten Sie mit größerer Wahrscheinlichkeit mehr positive Stimmen - und helfen dem Fragesteller, etwas Neues zu lernen.
lmo