Ringpuffer in Java

77

Ich habe eine Streaming-Zeitreihe, von der ich daran interessiert bin, die letzten 4 Elemente beizubehalten, was bedeutet, dass ich in der Lage sein möchte, die ersten zu platzen und am Ende hinzuzufügen. Im Wesentlichen brauche ich einen Ringpuffer .

Welche Java Collection ist dafür am besten geeignet? Vektor?

Truba
quelle
2
LinkedListscheint eine vernünftige Wahl für O (1) -Einfügungen und -Entfernungen zu sein. Benötigen Sie auch eine O (1) -Indizierung?
Mark Elliot
4
Thread sicher? Nicht threadsicher? Zum Entfernen vom Ende und Hinzufügen am Anfang ist normalerweise eine LinkedList die beste Option.
Maurício Linhares

Antworten:

94

Betrachten Sie CircularFifoBuffer aus Apache Common.Collections . Im Gegensatz zu Queue müssen Sie die begrenzte Größe der zugrunde liegenden Sammlung nicht beibehalten und umbrechen, sobald Sie das Limit erreicht haben.

Buffer buf = new CircularFifoBuffer(4);
buf.add("A");
buf.add("B");
buf.add("C");
buf.add("D"); //ABCD
buf.add("E"); //BCDE

CircularFifoBuffer erledigt dies aufgrund der folgenden Eigenschaften für Sie:

  • CircularFifoBuffer ist ein First-In-First-Out-Puffer mit einer festen Größe , der sein ältestes Element ersetzt, wenn es voll ist.
  • Die Entfernungsreihenfolge eines CircularFifoBuffers basiert auf der Einfügereihenfolge. Elemente werden in derselben Reihenfolge entfernt, in der sie hinzugefügt wurden. Die Iterationsreihenfolge entspricht der Entfernungsreihenfolge.
  • Die Operationen add (Object), BoundedFifoBuffer.remove () und BoundedFifoBuffer.get () werden alle in konstanter Zeit ausgeführt . Alle anderen Operationen werden in linearer Zeit oder schlechter ausgeführt.

Sie sollten jedoch auch die Einschränkungen berücksichtigen. Beispielsweise können Sie dieser Sammlung keine fehlenden Zeitreihen hinzufügen, da keine Nullen zulässig sind.

HINWEIS: Wenn Sie aktuelle allgemeine Sammlungen (4. *) verwenden, müssen Sie Queue verwenden. So was:

Queue buf = new CircularFifoQueue(4);
Andrey Taptunov
quelle
3
Es scheint nun eine Version zu geben, die von den ursprünglichen Commons-Sammlungen abgeleitet ist und Generika verwendet: sourceforge.net/projects/collections (es sieht so aus, als ob das Projekt nach Github verschoben wurde)
Andre Holzner
5
Commons Collections 4.0 enthält CircularFifoQueue mit denselben Eigenschaften und unterstützt Generika.
Pete
Mir ist aufgefallen, dass CircularFifoQueue so nicht funktioniert. Wenn ich "HALLO" in eine Warteschlange mit 3 Einheiten stelle, gehe ich von "HEL" zu "LEL" zu "LOL". Was ist mit der von @AndryTaptunov beschriebenen Funktion passiert?
ES
Das ist die von Andy vorgeschlagene Funktion. "heLlo" lautet "heL" -> "leL" -> "loL" und überschreibt den ältesten Buchstaben zuerst.
Ryan The Leach
Unabhängig davon , wie man durchläuft die CircularFifoQueue (durch Entfernen von Elementen, mit der Iterator der Warteschlange direkt indiziert ansteigend von Po 0, etc.), erhalten Sie die erwarteten heL, eLl, Llo. @RyanTheLeach scheint also zu veranschaulichen, wie die Warteschlange ihre Elemente speichert, aber ich kann das beschriebene Verhalten @ES nicht reproduzieren
fspinnenhirn
49

Seit Guava 15.0 (veröffentlicht im September 2013) gibt es EvictingQueue :

Eine nicht blockierende Warteschlange, die automatisch Elemente aus dem Kopf der Warteschlange entfernt, wenn versucht wird, neue Elemente zur Warteschlange hinzuzufügen, und die voll ist. Eine Räumungswarteschlange muss mit einer maximalen Größe konfiguriert werden. Jedes Mal, wenn ein Element zu einer vollständigen Warteschlange hinzugefügt wird, entfernt die Warteschlange automatisch ihr Kopfelement. Dies unterscheidet sich von herkömmlichen begrenzten Warteschlangen, die neue Elemente blockieren oder ablehnen, wenn sie voll sind.

Diese Klasse ist nicht threadsicher und akzeptiert keine Nullelemente.

Anwendungsbeispiel:

EvictingQueue<String> queue = EvictingQueue.create(2);
queue.add("a");
queue.add("b");
queue.add("c");
queue.add("d");
System.out.print(queue); //outputs [c, d]
Thomas Ferris Nicolaisen
quelle
1
@MartinVseticka Ja, es ist O (1).
Summe
14

Seit Java 1.6 gibt es eine ArrayDeque, die Queueschneller und speichereffizienter als a implementiert und zu sein scheint LinkedListund nicht den Thread-Synchronisationsaufwand von ArrayBlockingQueue: aus den API-Dokumenten hat: "Diese Klasse ist wahrscheinlich schneller als Stack, wenn sie als verwendet wird ein Stapel und schneller als LinkedList, wenn er als Warteschlange verwendet wird. "

final Queue<Object> q = new ArrayDeque<Object>();
q.add(new Object()); //insert element
q.poll(); //remove element
T. Baum
quelle
13
Dies wächst unbegrenzt und verhält sich nicht wie ein Ringpuffer.
Scorpiodawg
11

Wenn Sie brauchen

  • O (1) Einsetzen und Entfernen
  • O (1) Indizierung auf innere Elemente
  • Zugriff nur von einem einzigen Thread
  • generischer Elementtyp

Dann können Sie diese CircularArrayList für Java folgendermaßen verwenden (zum Beispiel):

CircularArrayList<String> buf = new CircularArrayList<String>(4);

buf.add("A");
buf.add("B");
buf.add("C");
buf.add("D"); // ABCD

String pop = buf.remove(0); // A <- BCD
buf.add("E"); // BCDE

String interiorElement = buf.get(i);

Alle diese Methoden werden in O (1) ausgeführt.

Museful
quelle
5

Ich hatte vor einiger Zeit das gleiche Problem und war enttäuscht, weil ich keine Lösung finden konnte, die meinen Bedürfnissen entspricht, also schrieb ich meine eigene Klasse. Ehrlich gesagt habe ich damals Code gefunden, aber selbst das war nicht das, wonach ich gesucht habe, also habe ich ihn angepasst und jetzt teile ich ihn, genau wie der Autor dieses Codes.

EDIT: Dies ist der ursprüngliche (wenn auch etwas andere) Code: CircularArrayList für Java

Ich habe den Link der Quelle nicht, weil es vor einiger Zeit war, aber hier ist der Code:

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.RandomAccess;

public class CircularArrayList<E> extends AbstractList<E> implements RandomAccess {

private final int n; // buffer length
private final List<E> buf; // a List implementing RandomAccess
private int leader = 0;
private int size = 0;


public CircularArrayList(int capacity) {
    n = capacity + 1;
    buf = new ArrayList<E>(Collections.nCopies(n, (E) null));
}

public int capacity() {
    return n - 1;
}

private int wrapIndex(int i) {
    int m = i % n;
    if (m < 0) { // modulus can be negative
        m += n;
    }
    return m;
}

@Override
public int size() {
    return this.size;
}

@Override
public E get(int i) {
    if (i < 0 || i >= n-1) throw new IndexOutOfBoundsException();

    if(i > size()) throw new NullPointerException("Index is greater than size.");

    return buf.get(wrapIndex(leader + i));
}

@Override
public E set(int i, E e) {
    if (i < 0 || i >= n-1) {
        throw new IndexOutOfBoundsException();
    }
    if(i == size()) // assume leader's position as invalid (should use insert(e))
        throw new IndexOutOfBoundsException("The size of the list is " + size() + " while the index was " + i
                +". Please use insert(e) method to fill the list.");
    return buf.set(wrapIndex(leader - size + i), e);
}

public void insert(E e)
{
    int s = size();     
    buf.set(wrapIndex(leader), e);
    leader = wrapIndex(++leader);
    buf.set(leader, null);
    if(s == n-1)
        return; // we have replaced the eldest element.
    this.size++;

}

@Override
public void clear()
{
    int cnt = wrapIndex(leader-size());
    for(; cnt != leader; cnt = wrapIndex(++cnt))
        this.buf.set(cnt, null);
    this.size = 0;      
}

public E removeOldest() {
    int i = wrapIndex(leader+1);

    for(;;i = wrapIndex(++i)) {
        if(buf.get(i) != null) break;
        if(i == leader)
            throw new IllegalStateException("Cannot remove element."
                    + " CircularArrayList is empty.");
    }

    this.size--;
    return buf.set(i, null);
}

@Override
public String toString()
{
    int i = wrapIndex(leader - size());
    StringBuilder str = new StringBuilder(size());

    for(; i != leader; i = wrapIndex(++i)){
        str.append(buf.get(i));
    }
    return str.toString();
}

public E getOldest(){
    int i = wrapIndex(leader+1);

    for(;;i = wrapIndex(++i)) {
        if(buf.get(i) != null) break;
        if(i == leader)
            throw new IllegalStateException("Cannot remove element."
                    + " CircularArrayList is empty.");
    }

    return buf.get(i);
}

public E getNewest(){
    int i = wrapIndex(leader-1);
    if(buf.get(i) == null)
        throw new IndexOutOfBoundsException("Error while retrieving the newest element. The Circular Array list is empty.");
    return buf.get(i);
}
}
vgfeit
quelle
3
Dies könnte die Quelle sein, auf die Sie sich beziehen: museful.net/2011/software-development/…
Lorne Laliberte
1
Ich habe diesen Code ausprobiert. CircularArrayList <String> buf = new CircularArrayList <String> (4); buf.insert ("A"); buf.insert ("B"); System.out.println (buf); // [null, null] buf.insert ("C"); buf.insert ("D"); System.out.println (buf); // [null, A, B, C] String res = buf.get (0); // null Der Code unter museful.net/2011/software-development/… funktioniert für mich besser.
Mauro Zallocco
Der zugehörige Iterator ist defekt
vlain
2

Ein sehr interessantes Projekt ist Disruptor. Es hat einen Ringpuffer und wird von dem verwendet, was ich in Finanzanwendungen weiß.

Siehe hier: Code des Ringpuffers

Ich habe sowohl Guavas EvictingQueue als auch ArrayDeque überprüft.

ArrayDeque begrenzt das Wachstum nicht, wenn es voll ist, verdoppelt es seine Größe und verhält sich daher nicht genau wie ein Ringpuffer.

EvictingQueue hält, was es verspricht, verwendet jedoch intern eine Deque, um Dinge zu speichern, und begrenzt nur den Speicher.

Wenn Sie also Wert darauf legen, dass der Speicher begrenzt wird, erfüllt ArrayDeque Ihr Versprechen nicht. Wenn Sie sich für die Anzahl der Objekte interessieren, verwendet EvictingQueue die interne Komposition (größere Objektgröße).

Ein einfacher und speichereffizienter kann von jmonkeyengine gestohlen werden . wörtliche Kopie

import java.util.Iterator;
import java.util.NoSuchElementException;

public class RingBuffer<T> implements Iterable<T> {

  private T[] buffer;          // queue elements
  private int count = 0;          // number of elements on queue
  private int indexOut = 0;       // index of first element of queue
  private int indexIn = 0;       // index of next available slot

  // cast needed since no generic array creation in Java
  public RingBuffer(int capacity) {
    buffer = (T[]) new Object[capacity];
  }

  public boolean isEmpty() {
    return count == 0;
  }

  public int size() {
    return count;
  }

  public void push(T item) {
    if (count == buffer.length) {
        throw new RuntimeException("Ring buffer overflow");
    }
    buffer[indexIn] = item;
    indexIn = (indexIn + 1) % buffer.length;     // wrap-around
    count++;
  }

  public T pop() {
    if (isEmpty()) {
        throw new RuntimeException("Ring buffer underflow");
    }
    T item = buffer[indexOut];
    buffer[indexOut] = null;                  // to help with garbage collection
    count--;
    indexOut = (indexOut + 1) % buffer.length; // wrap-around
    return item;
  }

  public Iterator<T> iterator() {
    return new RingBufferIterator();
  }

  // an iterator, doesn't implement remove() since it's optional
  private class RingBufferIterator implements Iterator<T> {

    private int i = 0;

    public boolean hasNext() {
        return i < count;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }

    public T next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        return buffer[i++];
    }
  }
}
Alex
quelle
LIFO-Ringpuffer können in Überlaufsituationen hilfreich sein. Stellen Sie sich vor, Sie stellen Zeitstempeldaten bereit und interessieren sich mehr für aktuelle als für alte Zeitstempel. Anstatt die neuesten Elemente in einer Warteschlangenimpelmentation zu löschen, löschen Sie die ältesten von einem Stapel. Dies gilt insbesondere für die Automatisierung, die Abschwächung bewirkt.
Alex
Der Iteratorcode dafür ist falsch. Es werden Artikel in der falschen Reihenfolge zurückgegeben, da das Umwickeln nicht korrekt ausgeführt wird.
MattWallace
1

Keines der zuvor angegebenen Beispiele entsprach vollständig meinen Anforderungen, daher habe ich eine eigene Warteschlange geschrieben, die folgende Funktionen ermöglicht: Iteration, Indexzugriff, indexOf, lastIndexOf, zuerst erhalten, zuletzt erhalten, Angebot, verbleibende Kapazität, Kapazität erweitern, letzte Warteschlange entfernen, Warteschlange entfernen Zuerst Element in die Warteschlange stellen / hinzufügen, Element in die Warteschlange stellen / entfernen, subQueueCopy, subArrayCopy, toArray, Snapshot, Grundlagen wie Größe, Entfernen oder Enthalten.

EjectingQueue

EjectingIntQueue

Terraner
quelle
-3

Verwenden Sie eine Warteschlange

Queue<String> qe=new LinkedList<String>();

qe.add("a");
qe.add("b");
qe.add("c");
qe.add("d");

System.out.println(qe.poll()); //returns a
System.out.println(qe.poll()); //returns b
System.out.println(qe.poll()); //returns c
System.out.println(qe.poll()); //returns d

Es gibt fünf einfache Methoden für eine Warteschlange

  • element () - Ruft den Kopf dieser Warteschlange ab, entfernt ihn jedoch nicht.

  • Angebot (E o) - Fügt das angegebene Element nach
    Möglichkeit in diese Warteschlange ein.

  • peek () - Ruft den Kopf dieser Warteschlange ab, entfernt ihn jedoch nicht und gibt null zurück, wenn diese Warteschlange leer ist.

  • poll () - Ruft den Kopf dieser Warteschlange ab und entfernt ihn, oder null, wenn diese Warteschlange leer ist.

  • remove () - Ruft den Kopf dieser Warteschlange ab und entfernt ihn.
Shawn
quelle
18
Dies hält alle Elemente, nicht nur die letzten 4
dkneller