Java – Tampón de anillo

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. ¿Qué colección 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 envolverlo 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 lo hará por usted debido a las siguientes propiedades:

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

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

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

Una cola sin locking que desaloja automáticamente los elementos del jefe de la cola cuando intenta agregar nuevos elementos a la cola y está llena. Una cola de desalojo debe configurarse 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 limitadas convencionales, que bloquean o rechazan nuevos elementos cuando están llenos.

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

Ejemplo de uso:

 EvictingQueue 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, hay ArrayDeque , que implementa Queue y parece ser más rápido y más eficiente en cuanto a la memoria que LinkedList y no tiene la sobrecarga de sincronización de subprocesos de ArrayBlockingQueue : de los documentos API: “Esta clase probablemente sea más rápida que Astack cuando se usa como una stack, y más rápido que LinkedList cuando se usa como cola. “

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

Si necesitas

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

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

 CircularArrayList buf = new CircularArrayList(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 un tiempo y me decepcionó porque no pude encontrar ninguna solución que satisficiera mis necesidades, así que escribí mi propia clase. Honestamente, encontré un código en ese momento, pero incluso eso no era lo que estaba buscando, así que lo adapté y ahora lo estoy compartiendo, al igual que 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 mucho 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 extends AbstractList implements RandomAccess { private final int n; // buffer length private final List buf; // a List implementing RandomAccess private int leader = 0; private int size = 0; public CircularArrayList(int capacity) { n = capacity + 1; buf = new ArrayList(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); } } 

Ninguno de los ejemplos anteriores satisfacían mis necesidades por completo, así que escribí mi propia cola que permite la siguiente funcionalidad: iteración, acceso al índice, indexOf, lastIndexOf, obtener primero, obtener el último, ofrecer, capacidad restante, expandir capacidad, dequeue el último, dequeue primero, enqueue / add element, dequeue / remove element, subQueueCopy, subArrayCopy, toArray, snapshot, elementos básicos como size, remove o contains.

EjectingQueue

EjectingIntQueue

Un proyecto muy interesante es disruptor. Tiene un ringbuffer y se utiliza a partir de lo que sé en aplicaciones financieras.

Vea aquí: código de ringbuffer

Revisé tanto EvictingQueue como ArrayDeque de Guava.

ArrayDeque no limita el crecimiento, si está lleno, tendrá el doble de tamaño y, por lo tanto, no actúa precisamente como un ringbuffer.

EvictingQueue hace lo que promete pero internamente usa un Deque para almacenar cosas y solo limita 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 utiliza la composición interna (tamaño de objeto más grande).

Un simple y eficiente en la memoria puede ser robado de jmonkeyengine . copia literal

 import java.util.Iterator; import java.util.NoSuchElementException; public class RingBuffer implements Iterable { 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 iterator() { return new RingBufferIterator(); } // an iterator, doesn't implement remove() since it's optional private class RingBufferIterator implements Iterator { 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++]; } } } 

Use una cola

 Queue qe=new LinkedList(); 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
    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 null si esta cola está vacía.

  • remove () – Recupera y elimina el encabezado de esta cola.