Como você codificaria um Buffer Circular eficiente em Java ou C #?

Eu quero uma class simples que implementa um buffer circular de tamanho fixo. Deve ser eficiente, fácil para os olhos, genericamente typescript.

EDIT: Não precisa ser capaz de MT, por enquanto. Eu sempre posso adicionar um bloqueio mais tarde, não será de alta concorrência em qualquer caso.

Os methods devem ser: .Adicionar e eu acho .List, onde eu recupero todas as inputs. No segundo pensamento, recuperação, acho que deve ser feito através de um indexador. A qualquer momento, quero poder recuperar qualquer elemento no buffer por índice. Mas lembre-se de que, de um momento para o próximo, o elemento [n] pode ser diferente, à medida que o buffer Circular é preenchido e revertido.

Isso não é uma pilha, é um buffer circular. Em relação ao “estouro”: eu esperaria internamente que haveria uma matriz contendo os itens, e com o tempo a cabeça e a cauda do buffer girariam em torno dessa matriz fixa. Mas isso deve ser invisível do usuário. Não deve haver nenhum evento ou comportamento de “estouro” detectável externamente.

Esta não é uma atribuição da escola – é mais comumente usada para um cache de MRU ou uma transação de tamanho fixo ou um log de events.

Eu usaria uma matriz de T, um ponteiro de header e cauda, ​​e adicionaria e obteria methods.

Como: (Caça aos bugs é deixada para o usuário)

// Hijack these for simplicity import java.nio.BufferOverflowException; import java.nio.BufferUnderflowException; public class CircularBuffer { private T[] buffer; private int tail; private int head; @SuppressWarnings("unchecked") public CircularBuffer(int n) { buffer = (T[]) new Object[n]; tail = 0; head = 0; } public void add(T toAdd) { if (head != (tail - 1)) { buffer[head++] = toAdd; } else { throw new BufferOverflowException(); } head = head % buffer.length; } public T get() { T t = null; int adjTail = tail > head ? tail - buffer.length : tail; if (adjTail < head) { t = (T) buffer[tail++]; tail = tail % buffer.length; } else { throw new BufferUnderflowException(); } return t; } public String toString() { return "CircularBuffer(size=" + buffer.length + ", head=" + head + ", tail=" + tail + ")"; } public static void main(String[] args) { CircularBuffer b = new CircularBuffer(3); for (int i = 0; i < 10; i++) { System.out.println("Start: " + b); b.add("One"); System.out.println("One: " + b); b.add("Two"); System.out.println("Two: " + b); System.out.println("Got '" + b.get() + "', now " + b); b.add("Three"); System.out.println("Three: " + b); // Test Overflow // b.add("Four"); // System.out.println("Four: " + b); System.out.println("Got '" + b.get() + "', now " + b); System.out.println("Got '" + b.get() + "', now " + b); // Test Underflow // System.out.println("Got '" + b.get() + "', now " + b); // Back to start, let's shift on one b.add("Foo"); b.get(); } } } 

É assim que eu escrevia (ou escrevia ) um buffer circular eficiente em Java. É apoiado por um array simples. Para meu caso de uso específico, eu precisava de alta taxa de transferência simultânea, então usei o CAS para alocação do índice. Eu então criei mecanismos para cópias confiáveis, incluindo uma cópia do CAS de todo o buffer. Eu usei isso em um caso que é descrito em maior detalhe no artigo curto .

 import java.util.concurrent.atomic.AtomicLong; import java.lang.reflect.Array; /** * A circular array buffer with a copy-and-swap cursor. * * 

This class provides an list of T objects who's size is unstable. * It's intended for capturing data where the frequency of sampling greatly * outweighs the frequency of inspection (for instance, monitoring).

* *

This object keeps in memory a fixed size buffer which is used for * capturing objects. It copies the objects to a snapshot array which may be * worked with. The size of the snapshot array will vary based on the * stability of the array during the copy operation.

* *

Adding buffer to the buffer is O(1), and lockless. Taking a * stable copy of the sample is O(n).

*/ public class ConcurrentCircularBuffer { private final AtomicLong cursor = new AtomicLong(); private final T[] buffer; private final Class type; /** * Create a new concurrent circular buffer. * * @param type The type of the array. This is captured for the same reason * it's required by {@link java.util.List.toArray()}. * * @param bufferSize The size of the buffer. * * @throws IllegalArgumentException if the bufferSize is a non-positive * value. */ public ConcurrentCircularBuffer (final Class type, final int bufferSize) { if (bufferSize < 1) { throw new IllegalArgumentException( "Buffer size must be a positive value" ); } this.type = type; this.buffer = (T[]) new Object [ bufferSize ]; } /** * Add a new object to this buffer. * *

Add a new object to the cursor-point of the buffer.

* * @param sample The object to add. */ public void add (T sample) { buffer[(int) (cursor.getAndIncrement() % buffer.length)] = sample; } /** * Return a stable snapshot of the buffer. * *

Capture a stable snapshot of the buffer as an array. The snapshot * may not be the same length as the buffer, any objects which were * unstable during the copy will be factored out.

* * @return An array snapshot of the buffer. */ public T[] snapshot () { T[] snapshots = (T[]) new Object [ buffer.length ]; /* Determine the size of the snapshot by the number of affected * records. Trim the size of the snapshot by the number of records * which are considered to be unstable during the copy (the amount the * cursor may have moved while the copy took place). * * If the cursor eliminated the sample (if the sample size is so small * compared to the rate of mutation that it did a full-wrap during the * copy) then just treat the buffer as though the cursor is * buffer.length - 1 and it was not changed during copy (this is * unlikley, but it should typically provide fairly stable results). */ long before = cursor.get(); /* If the cursor hasn't yet moved, skip the copying and simply return a * zero-length array. */ if (before == 0) { return (T[]) Array.newInstance(type, 0); } System.arraycopy(buffer, 0, snapshots, 0, buffer.length); long after = cursor.get(); int size = buffer.length - (int) (after - before); long snapshotCursor = before - 1; /* Highly unlikely, but the entire buffer was replaced while we * waited...so just return a zero length array, since we can't get a * stable snapshot... */ if (size <= 0) { return (T[]) Array.newInstance(type, 0); } long start = snapshotCursor - (size - 1); long end = snapshotCursor; if (snapshotCursor < snapshots.length) { size = (int) snapshotCursor + 1; start = 0; } /* Copy the sample snapshot to a new array the size of our stable * snapshot area. */ T[] result = (T[]) Array.newInstance(type, size); int startOfCopy = (int) (start % snapshots.length); int endOfCopy = (int) (end % snapshots.length); /* If the buffer space wraps the physical end of the array, use two * copies to construct the new array. */ if (startOfCopy > endOfCopy) { System.arraycopy(snapshots, startOfCopy, result, 0, snapshots.length - startOfCopy); System.arraycopy(snapshots, 0, result, (snapshots.length - startOfCopy), endOfCopy + 1); } else { /* Otherwise it's a single continuous segment, copy the whole thing * into the result. */ System.arraycopy(snapshots, startOfCopy, result, 0, endOfCopy - startOfCopy + 1); } return (T[]) result; } /** * Get a stable snapshot of the complete buffer. * *

This operation fetches a snapshot of the buffer using the algorithm * defined in {@link snapshot()}. If there was concurrent modification of * the buffer during the copy, however, it will retry until a full stable * snapshot of the buffer was acquired.

* *

Note, for very busy buffers on large symmetric multiprocessing * machines and supercomputers running data processing intensive * applications, this operation has the potential of being fairly * expensive. In practice on commodity hardware, dualcore processors and * non-processing intensive systems (such as web services) it very rarely * retries.

* * @return A full copy of the internal buffer. */ public T[] completeSnapshot () { T[] snapshot = snapshot(); /* Try again until we get a snapshot that's the same size as the * buffer... This is very often a single iteration, but it depends on * how busy the system is. */ while (snapshot.length != buffer.length) { snapshot = snapshot(); } return snapshot; } /** * The size of this buffer. */ public int size () { return buffer.length; } }

Eu usaria ArrayBlockingQueue ou uma das outras implementações de fila pré-construídas, dependendo de quais são as necessidades. Muito raramente é necessário implementar essa estrutura de dados (a menos que seja uma tarefa da escola).

EDIT: Agora que você adicionou o requisito “para recuperar qualquer elemento no buffer por índice”, suponho que você precisa para implementar sua própria class (a menos que o Google-collections ou alguma outra biblioteca fornece um). Um buffer circular é muito fácil de implementar, como mostra o exemplo de JeeBee. Você também pode olhar para o código-fonte do ArrayBlockingQueue – seu código é bastante limpo, basta remover os methods de travamento e desnecessários, e adicionar methods para acessá-lo pelo índice.

Aqui está uma implementação CircularArrayList pronta para uso para Java que eu uso no código de produção. Substituindo AbstractList da maneira recomendada por Java, ele suporta todas as funcionalidades que você esperaria de uma implementação de Lista padrão no Java Collections Framework (tipo de elemento genérico, subList, iteração, etc.).

As seguintes chamadas são concluídas em O (1):

  • add (item) – adiciona no final da lista
  • remove (0) – remove do início da lista
  • get (i) – recupera o elemento random na lista

Use o ArrayDeque de Java

Apenas use a implementação de outra pessoa:

O Deque collections de energia é implementado por um buffer circular.

A biblioteca de collections de energia é irregular, mas o Deque é um buffer circular expansível perfeitamente aceitável.

Como você indica que não deseja expansão e, em vez disso, deseja sobrescrever, pode facilmente modificar o código para sobrescrever. Isso envolveria simplesmente remover a verificação de que os pointers estavam logicamente adjacentes e apenas escreviam mesmo assim. Ao mesmo tempo, o buffer privado poderia ser feito somente para leitura.

System.Collections.Generic.Queue – é um buffer circular simples dentro de (T [] com cabeça e cauda, ​​assim como na amostra do JeeBee ).

Em Guava 15, introduzimos EvictingQueue , que é uma fila limitada, não bloqueante que remove automaticamente (remove) elementos da cabeça da fila ao tentar adicionar elementos a uma fila completa. Isso é diferente das filas limitadas convencionais, que bloqueiam ou rejeitam novos elementos quando estão cheias.

Parece que isso deve atender às suas necessidades, e tem uma interface muito mais simples do que usar um ArrayDeque diretamente (ele usa um sob o capô!).

Mais informações podem ser encontradas aqui .

Eu quero responder a essa pergunta na perspectiva java.

Para implementar um buffer circular com java, você provavelmente precisará de três coisas, incluindo: uma class de buffer circular, genérica e poucas operações (Para aprender quais operações você precisa e o mecanismo interno nessas operações, você pode precisar ler wiki para tampão circular no início).

Em segundo lugar, o julgamento do buffer cheio ou vazio deve ser tratado com muito cuidado. Aqui eu dou duas soluções instintivas para o julgamento completo / vazio. Na solução um, você precisa criar duas variantes inteiras para armazenar o tamanho atual do seu buffer e o tamanho máximo do seu buffer. Obviamente, se o tamanho atual for igual ao tamanho máximo, o buffer estará cheio.

Em outra solução, definimos o último local de armazenamento em ocioso (para buffer circular com tamanho sete, configuramos o armazenamento em sete em inatividade). De acordo com isso, podemos determinar que o buffer está cheio quando a expressão (rp+1)%MAXSIZE == fp; é satisfeito.

Para mais esclarecimentos, aqui dá uma implementação com a linguagem java.

 import java.nio.BufferOverflowException; import java.nio.BufferUnderflowException; public class CircularBuffer { private int front; private int rear; private int currentSize; private int maxSize; private T[] buffer; public CircularBuffer(int n) { buffer = (T[]) new Object[n]; front = 0; rear = 0; currentSize = 0; maxSize = n; } public void push(T e) { if (!isFull()) { buffer[rear] = e; currentSize++; rear = (rear + 1) % maxSize; } else throw new BufferOverflowException(); } public T pop() { if (!isEmpty()) { T temp = buffer[front]; buffer[front] = null; front = (front + 1) % maxSize; currentSize--; return temp; } else throw new BufferUnderflowException(); } public T peekFirst() { if (!isEmpty()) { return buffer[front]; } else return null; } public T peekLast() { if (!isEmpty()) { return buffer[rear - 1]; } else return null; } public int size() { return currentSize; } public boolean isEmpty() { if (currentSize == 0) { return true; } else return false; } public boolean isFull() { if (currentSize == maxSize) { return true; } else return false; } public boolean clean() { front = 0; rear = 0; while (rear != 0) { buffer[rear] = null; rear = (rear + 1) % maxSize; } return true; } public static void main(String[] args) { CircularBuffer buff = new CircularBuffer<>(7); buff.push(0); buff.push(1); buff.push(2); System.out.println(buff.size()); System.out.println("The head element is: " + buff.pop()); System.out.println("Size should be twoo: " + buff.size()); System.out.println("The last element is one: " + buff.peekLast()); System.out.println("Size should be two: " + buff.size()); buff.clean(); System.out.println("Size should be zero: " + buff.size()); } } 

se um cache lru funcionasse, considere usar apenas http://java.sun.com/javase/6/docs/api/java/util/LinkedHashMap.html#LinkedHashMap(int,%20float,%20boolean) , http: / /java.sun.com/javase/6/docs/api/java/util/LinkedHashMap.html#removeEldestEntry(java.util.Map.Entry)

Aqui está uma implementação que eu codifiquei para meu próprio uso, mas que poderia ser útil.

O buffer contém um conjunto fixo máximo de itens. O conjunto é circular, itens antigos são removidos automaticamente. O chamador pode obter itens de cauda por um índice incremental absoluto (um longo), mas os itens podem ter sido perdidos entre as chamadas muito distantes no tempo. Esta class é totalmente thread-safe.

 public sealed class ConcurrentCircularBuffer : ICollection { private T[] _items; private int _index; private bool _full; public ConcurrentCircularBuffer(int capacity) { if (capacity <= 1) // need at least two items throw new ArgumentException(null, "capacity"); Capacity = capacity; _items = new T[capacity]; } public int Capacity { get; private set; } public long TotalCount { get; private set; } public int Count { get { lock (SyncObject) // full & _index need to be in sync { return _full ? Capacity : _index; } } } public void AddRange(IEnumerable items) { if (items == null) return; lock (SyncObject) { foreach (var item in items) { AddWithLock(item); } } } private void AddWithLock(T item) { _items[_index] = item; _index++; if (_index == Capacity) { _full = true; _index = 0; } TotalCount++; } public void Add(T item) { lock (SyncObject) { AddWithLock(item); } } public void Clear() { lock (SyncObject) { _items = new T[Capacity]; _index = 0; _full = false; TotalCount = 0; } } // this gives raw access to the underlying buffer. not sure I should keep that public T this[int index] { get { return _items[index]; } } public T[] GetTail(long startIndex) { long lostCount; return GetTail(startIndex, out lostCount); } public T[] GetTail(long startIndex, out long lostCount) { if (startIndex < 0 || startIndex >= TotalCount) throw new ArgumentOutOfRangeException("startIndex"); T[] array = ToArray(); lostCount = (TotalCount - Count) - startIndex; if (lostCount >= 0) return array; lostCount = 0; // this maybe could optimized to not allocate the initial array // but in multi-threading environment, I suppose this is arguable (and more difficult). T[] chunk = new T[TotalCount - startIndex]; Array.Copy(array, array.Length - (TotalCount - startIndex), chunk, 0, chunk.Length); return chunk; } public T[] ToArray() { lock (SyncObject) { T[] items = new T[_full ? Capacity : _index]; if (_full) { if (_index == 0) { Array.Copy(_items, items, Capacity); } else { Array.Copy(_items, _index, items, 0, Capacity - _index); Array.Copy(_items, 0, items, Capacity - _index, _index); } } else if (_index > 0) { Array.Copy(_items, items, _index); } return items; } } public IEnumerator GetEnumerator() { return ToArray().AsEnumerable().GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } bool ICollection.Contains(T item) { return _items.Contains(item); } void ICollection.CopyTo(T[] array, int arrayIndex) { if (array == null) throw new ArgumentNullException("array"); if (array.Rank != 1) throw new ArgumentException(null, "array"); if (arrayIndex < 0) throw new ArgumentOutOfRangeException("arrayIndex"); if ((array.Length - arrayIndex) < Count) throw new ArgumentException(null, "array"); T[] thisArray = ToArray(); Array.Copy(thisArray, 0, array, arrayIndex, thisArray.Length); } bool ICollection.IsReadOnly { get { return false; } } bool ICollection.Remove(T item) { return false; } private static object _syncObject; private static object SyncObject { get { if (_syncObject == null) { object obj = new object(); Interlocked.CompareExchange(ref _syncObject, obj, null); } return _syncObject; } } } 

Aqui está outra implementação que usa o BoundedFifoBuffer da coleção comum do Apache. por favor, use CircularFifoQueue se você estiver usando o JAR mais recente do Apache, pois a class abaixo está obsoleta

  BoundedFifoBuffer apiCallHistory = new BoundedFifoBuffer(20); for(int i =1 ; i < 25; i++){ if(apiCallHistory.isFull()){ System.out.println("removing :: "+apiCallHistory.remove()); } apiCallHistory.add(i); } 
 // The following is in C# public class fqueue { // The following code implements a circular queue of objects //private data: private bool empty; private bool full; private int begin, end; private object[] x; //public data: public fqueue() { empty = !(full = false); begin = end = 0xA2; x = new object[256]; return; } public fqueue(int size) { if (1 > size) throw new Exception("fqueue: Size cannot be zero or negative"); empty = !(full = false); begin = end = 0xA2; x = new object[size]; return; } public object write { set { if(full) throw new Exception("Write error: Queue is full"); end = empty ? end : (end + 1) % x.Length; full = ((end + 1) % x.Length) == begin; empty = false; x[end] = value; } } public object read { get { if(empty) throw new Exception("Read error: Queue is empty"); full = false; object ret = x[begin]; begin = (empty=end==begin) ? begin : (begin + 1) % x.Length; return ret; } } public int maxSize { get { return x.Length; } } public int queueSize { get { return end - begin + (empty ? 0 : 1 + ((end < begin) ? x.Length : 0)); } } public bool isEmpty { get { return empty; } } public bool isFull { get { return full; } } public int start { get { return begin; } } public int finish { get { return end; } } }