Java – Ring Buffer

Ho una serie temporale in streaming, di cui sono interessato a mantenere gli ultimi 4 elementi, il che significa che voglio essere in grado di eseguire il pop del primo e aggiungere alla fine. Quale Java Collection è la migliore per questo? Vettore?

Considera CircularFifoBuffer da Apache Common.Collections . A differenza della coda , non è necessario mantenere la dimensione limitata della raccolta sottostante e avvolgerla una volta raggiunto il limite.

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

CircularFifoBuffer farà questo per te a causa delle seguenti proprietà:

  • CircularFifoBuffer è un primo nel primo buffer esterno con una dimensione fissa che sostituisce il suo elemento più vecchio se pieno.
  • L’ordine di rimozione di un CircularFifoBuffer si basa sull’ordine di inserimento; gli elementi vengono rimossi nello stesso ordine in cui sono stati aggiunti. L’ordine di iterazione è lo stesso dell’ordine di rimozione.
  • Le operazioni di aggiunta (Object), BoundedFifoBuffer.remove () e BoundedFifoBuffer.get () vengono eseguite tutte in tempo costante . Tutte le altre operazioni si svolgono in tempo lineare o peggio.

Comunque dovresti considerare anche le sue limitazioni – per esempio, non puoi aggiungere temporizzazioni mancanti a questa collezione perché non consente i null.

Dal momento che Guava 15.0 (pubblicato a settembre 2013) c’è EvictingQueue :

Una coda non bloccante che rimuove automaticamente gli elementi dal capo della coda quando si tenta di aggiungere nuovi elementi alla coda ed è piena. Una coda di espulsione deve essere configurata con una dimensione massima. Ogni volta che un elemento viene aggiunto a una coda completa, la coda rimuove automaticamente l’elemento principale. Questo è diverso dalle convenzionali code limitate, che bloccano o rifiutano nuovi elementi quando sono pieni.

Questa class non è thread-safe e non accetta elementi null.

Esempio di utilizzo:

 EvictingQueue queue = EvictingQueue.create(2); queue.add("a"); queue.add("b"); queue.add("c"); queue.add("d"); System.out.print(queue); //outputs [c, d] 

Da Java 1.6, c’è ArrayDeque , che implementa Queue e sembra essere più veloce e più efficiente della memoria di una LinkedList e non ha il sovraccarico di sincronizzazione dei thread di ArrayBlockingQueue : dai documenti API: “Questa class è probabilmente più veloce di Stack se usato come stack e più veloce di LinkedList quando usato come coda. “

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

Se avete bisogno

  • O (1) inserimento e rimozione
  • O (1) indicizzazione agli elementi interni
  • accesso solo da un singolo thread
  • tipo di elemento generico

quindi è ansible utilizzare questo CircularArrayList per Java in questo modo (ad esempio):

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

Tutti questi metodi vengono eseguiti in O (1).

Ho avuto lo stesso problema qualche tempo fa e sono rimasto deluso perché non sono riuscito a trovare nessuna soluzione adatta alle mie esigenze, così ho scritto la mia class. Onestamente, ho trovato un codice allora, ma anche quello non era quello che stavo cercando, quindi l’ho adattato e ora lo sto condividendo, proprio come ha fatto l’autore di quel pezzo di codice.

EDIT: Questo è il codice originale (anche se leggermente diverso): CircularArrayList per java

Non ho il link della fonte perché era tempo fa, ma ecco il codice:

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

Nessuno degli esempi forniti in precedenza soddisfaceva completamente le mie esigenze, quindi ho scritto la mia coda che consente le seguenti funzionalità: iterazione, accesso all’indice, indexOf, lastIndexOf, ottenere prima, ottenere ultimo, offrire, capacità rimanente, espandere capacità, eliminare la coda, desinare per prima cosa, accodare / aggiungere elemento, dequeue / remove element, subQueueCopy, subArrayCopy, toArray, snapshot, elementi di base come size, remove o contains.

EjectingQueue

EjectingIntQueue

Un progetto molto interessante è il disgregatore. Ha un ringbuffer ed è usato da quello che so nelle applicazioni finanziarie.

Vedi qui: codice del ringbuffer

Ho controllato sia EvictingQueue che ArrayDeque di Guava.

ArrayDeque non limita la crescita se è piena raddoppierà le dimensioni e quindi non si comporta esattamente come un ringbuffer.

EvictingQueue fa ciò che promette, ma internamente utilizza un Deque per archiviare le cose e solo limiti di memoria.

Quindi, se ti interessa che la memoria sia limitata, ArrayDeque non rispetta la tua promise. Se ti interessa il numero di oggetti EvictingQueue usa la composizione interna (dimensione dell’object più grande).

Uno strumento semplice e di memoria può essere rubato da jmonkeyengine . copia letterale

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

Usa una coda

 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 

Esistono cinque metodi semplici di coda

  • element () – Recupera, ma non rimuove, il capo di questa coda.

  • offerta (E o) – Inserisce l’elemento specificato in questa coda, se
    ansible.

  • peek () – Recupera, ma non rimuove, il capo di questa coda, restituendo null se questa coda è vuota.

  • poll () – Recupera e rimuove il capo di questa coda, o null se questa coda è vuota.

  • remove () – Recupera e rimuove il capo di questa coda.