Ringpuffer in Java

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?

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

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]

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

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.

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

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

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

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.