Ring Buffer en Java

Tengo una serie de tiempo de transmisión, de la cual estoy interesado en mantener los últimos 4 elementos, lo que significa que quiero poder mostrar el primero y agregarlo al final. Básicamente, lo que necesito es un búfer de anillo .

¿Qué colección de Java es la mejor para esto? ¿Vector?

Considere CircularFifoBuffer de Apache Common.Collections . A diferencia de Queue , no tienes que mantener el tamaño limitado de la colección subyacente y ajustarla una vez que alcanzas el límite.

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

CircularFifoBuffer hará esto por usted debido a las siguientes propiedades:

• CircularFifoBuffer es un búfer de primero en entrar, primero en salir con un tamaño fijo que reemplaza su elemento más antiguo si está lleno.
• La orden de eliminación de CircularFifoBuffer se basa en la orden de inserción; los elementos se eliminan en el mismo orden en que se agregaron. El orden de iteración es el mismo que el de eliminación.
• Las operaciones add (Object), BoundedFifoBuffer.remove () y BoundedFifoBuffer.get () se realizan en tiempo constante . Todas las demás operaciones se realizan en tiempo lineal o peor.

Sin embargo, también debe considerar sus limitaciones; por ejemplo, no puede agregar series temporales faltantes a esta colección porque no permite valores nulos.

NOTA: Cuando use Colecciones comunes actuales (4. *), debe usar Cola. Me gusta esto:

Queue buf = new CircularFifoQueue(4);

Desde Guava 15.0 (lanzado en septiembre de 2013) existe EvictingQueue :

Una cola sin bloqueo que desaloja automáticamente los elementos del encabezado de la cola cuando intenta agregar nuevos elementos a la cola y está llena. Se debe configurar una cola de desalojo con un tamaño máximo. Cada vez que se agrega un elemento a una cola completa, la cola elimina automáticamente su elemento principal. Esto es diferente de las colas delimitadas convencionales, que bloquean o rechazan nuevos elementos cuando están llenas.

Esta clase no es segura para subprocesos y no acepta elementos nulos.

Ejemplo de uso:

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]

Desde Java 1.6, existe ArrayDeque, que implementa Queuey parece ser más rápido y más eficiente en memoria que a LinkedListy no tiene la sobrecarga de sincronización de subprocesos de ArrayBlockingQueue: de los documentos de la API: "Es probable que esta clase sea más rápida que Stack cuando se usa como una pila, y más rápido que LinkedList cuando se usa como cola ".

final Queue<Object> q = new ArrayDeque<Object>();
q.add(new Object()); //insert element
q.poll(); //remove element

Si necesitas

• O (1) inserción y extracción
• O (1) indexación a elementos interiores
• acceso desde un solo hilo
• tipo de elemento genérico

entonces puede usar este CircularArrayList para Java de esta manera (por ejemplo):

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

Todos estos métodos se ejecutan en O (1).

Tuve el mismo problema hace algún tiempo y me decepcionó porque no pude encontrar ninguna solución que se adaptara a mis necesidades, así que escribí mi propia clase. Honestamente, encontré un código en ese entonces, pero ni siquiera eso era lo que estaba buscando, así que lo adapté y ahora lo estoy compartiendo, tal como lo hizo el autor de ese código.

EDITAR: Este es el código original (aunque ligeramente diferente): CircularArrayList para java

No tengo el enlace de la fuente porque fue hace tiempo, pero aquí está el código:

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

Un proyecto muy interesante es disruptor. Tiene un búfer de anillo y se usa por lo que sé en aplicaciones financieras.

Ver aquí: código de ringbuffer

Revisé EvictingQueue y ArrayDeque de Guava.

ArrayDeque no limita el crecimiento si está lleno, duplicará su tamaño y, por lo tanto, no actúa precisamente como un búfer de anillo.

EvictingQueue hace lo que promete pero usa internamente un Deque para almacenar cosas y limitar la memoria.

Por lo tanto, si le importa que la memoria esté limitada, ArrayDeque no está cumpliendo su promesa. Si le importa el recuento de objetos, EvictingQueue usa una composición interna (tamaño de objeto más grande).

Se puede robar uno simple y eficiente en memoria de jmonkeyengine . copia literal

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

Ninguno de los ejemplos dados anteriormente satisfacía mis necesidades por completo, así que escribí mi propia cola que permite la siguiente funcionalidad: iteración, acceso al índice, indexOf, lastIndexOf, get first, get last, offer, capacidad restante, expandir capacidad, sacar el último, sacar de la cola primero, poner en cola / agregar elemento, quitar de cola / eliminar elemento, subQueueCopy, subArrayCopy, toArray, instantánea, conceptos básicos como tamaño, eliminar o contiene.

EjectingQueue

EjectingIntQueue

Usar una cola

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

Hay cinco métodos simples de una cola

• element (): recupera, pero no elimina, el encabezado de esta cola.

• oferta (E o): inserta el elemento especificado en esta cola, si es
  posible.

• peek (): recupera, pero no elimina, el encabezado de esta cola, devolviendo nulo si esta cola está vacía.

• poll (): recupera y elimina el encabezado de esta cola, o nulo si esta cola está vacía.

• remove (): recupera y elimina el encabezado de esta cola.