programacion - Cómo codificaría un eficiente Buffer circular en Java o C#
buffer informatica (13)
Quiero una clase simple que implemente un buffer circular de tamaño fijo. Debería ser eficiente, fácil para los ojos, genéricamente mecanografiado.
EDITAR: No tiene por qué ser compatible con MT, por ahora. Siempre puedo agregar un candado más tarde, no será concurrencia alta en ningún caso.
Los métodos deben ser: .Add y supongo .List, donde recupero todas las entradas. Pensándolo bien, la recuperación creo que debería hacerse a través de un indexador. En cualquier momento, querré poder recuperar cualquier elemento en el buffer por índice. Pero tenga en cuenta que de un momento a otro Element [n] puede ser diferente, a medida que el buffer circular se llena y gira.
Esto no es una pila, es un buffer circular. Con respecto al "desbordamiento": esperaría internamente que hubiera un arreglo que contenga los elementos, y con el tiempo la cabeza y la cola del búfer rotarán alrededor de ese arreglo fijo. Pero eso debería ser invisible para el usuario. No debe haber ningún evento o comportamiento de "desbordamiento" detectable externamente.
Esta no es una tarea escolar, sino que más comúnmente se utilizará para un caché MRU o una transacción de tamaño fijo o registro de eventos.
Aquí hay otra implementación que usa BoundedFifoBuffer de la colección común de Apache. utilice CircularFifoQueue si está utilizando el último JAR de Apache ya que la clase siguiente 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);
}
Aquí hay una implementación CircularArrayList lista para usar para Java que uso en el código de producción. Al sustituir AbstractList en la forma recomendada por Java, es compatible con todas las funciones que cabría esperar de una implementación de lista estándar en Java Collections Framework (tipo de elemento genérico, subList, iteración, etc.).
Las siguientes llamadas se completan en O (1):
- agregar (elemento) - agrega al final de la lista
- remove (0) - elimina del comienzo de la lista
- get (i) - recupera elementos aleatorios en la lista
Aquí hay una implementación que he codificado para mi propio uso, pero que podría ser útil.
El buffer contiene un conjunto fijo máximo de elementos. El conjunto es circular, los elementos antiguos se eliminan automáticamente. La persona que llama puede obtener elementos de cola por un índice incremental absoluto (un largo), pero los artículos pueden haberse perdido entre llamadas demasiado distantes en el tiempo. Esta clase es completamente segura para subprocesos.
public sealed class ConcurrentCircularBuffer<T> : ICollection<T>
{
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<T> 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<T> GetEnumerator()
{
return ToArray().AsEnumerable().GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
bool ICollection<T>.Contains(T item)
{
return _items.Contains(item);
}
void ICollection<T>.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<T>.IsReadOnly
{
get
{
return false;
}
}
bool ICollection<T>.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;
}
}
}
Así es como escribiría (o escribiría ) un búfer circular eficaz en Java. Está respaldado por una matriz simple. Para mi caso de uso particular, necesitaba un alto rendimiento simultáneo, así que usé CAS para la asignación del índice. Luego creé mecanismos para copias confiables incluyendo una copia CAS de todo el buffer. Usé esto en un caso que se describe con mayor detalle en un breve artículo .
import java.util.concurrent.atomic.AtomicLong;
import java.lang.reflect.Array;
/**
* A circular array buffer with a copy-and-swap cursor.
*
* <p>This class provides an list of T objects who''s size is <em>unstable</em>.
* It''s intended for capturing data where the frequency of sampling greatly
* outweighs the frequency of inspection (for instance, monitoring).</p>
*
* <p>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.</p>
*
* <p>Adding buffer to the buffer is <em>O(1)</em>, and lockless. Taking a
* stable copy of the sample is <em>O(n)</em>.</p>
*/
public class ConcurrentCircularBuffer <T> {
private final AtomicLong cursor = new AtomicLong();
private final T[] buffer;
private final Class<T> 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 <T> 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.
*
* <p>Add a new object to the cursor-point of the buffer.</p>
*
* @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.
*
* <p>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.</p>
*
* @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.
*
* <p>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.</p>
*
* <p><em>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.</em></p>
*
* @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;
}
}
En Guava 15, presentamos EvictingQueue , que es una cola acotada no bloqueante que desaloja automáticamente (elimina) elementos del jefe de la cola cuando intenta agregar elementos a una cola completa. Esto es diferente de las colas limitadas convencionales, que bloquean o rechazan nuevos elementos cuando están llenos.
Parece que esto debería adaptarse a sus necesidades, y tiene una interfaz mucho más simple que usar un ArrayDeque directamente (aunque usa uno debajo del capó).
Más información se puede encontrar here .
Quiero responder esta pregunta desde la perspectiva de Java.
Para implementar un búfer circular con java, probablemente necesite tres cosas, entre ellas: una clase de memoria circular circular, genérica y pocas operaciones en ella (para aprender qué operaciones necesita y el mecanismo interno en estas operaciones, es posible que necesite leer wiki para tampón circular al principio).
En segundo lugar, el juicio de la memoria intermedia llena o vacía debe tratarse con mucho cuidado. Aquí doy dos soluciones instintivas para el juicio completo / vacío. En la solución uno, necesita crear dos variantes enteras para almacenar tanto el tamaño actual de su búfer como el tamaño máximo de su búfer. Obviamente, si el tamaño actual es igual al tamaño máximo, el buffer está lleno.
En otra solución, configuramos el último lugar de almacenamiento en inactivo (para el búfer circular con el tamaño siete, configuramos el almacenamiento en siete en inactivo). De acuerdo con esto, podemos determinar que el búfer está lleno cuando la expresión (rp+1)%MAXSIZE == fp; Está satisfecho.
Para obtener más aclaraciones, aquí presentamos una implementación con el lenguaje Java.
import java.nio.BufferOverflowException;
import java.nio.BufferUnderflowException;
public class CircularBuffer<T> {
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<Integer> 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());
}
}
Simplemente use la implementación de otra persona:
Power Collections Deque<T> se implementa mediante un búfer circular.
La biblioteca de colecciones de poder es desigual, pero el Deque es perfectamente aceptable expandiendo el búfer circular.
Dado que usted indica que no desea la expansión y en su lugar desea sobrescribir, puede modificar el código fácilmente para sobrescribirlo. Esto simplemente implicaría quitar el cheque para que los punteros sean lógicamente adyacentes y simplemente escribir de todos modos. Al mismo tiempo, el buffer privado podría ser de solo lectura.
System.Collections.Generic.Queue - es un simple buffer circular dentro (T [] con cabeza y cola, como en la share ).
Usa ArrayDeque de Java
Utilizaría ArrayBlockingQueue o una de las otras implementaciones de Queue precompiladas, según cuáles sean las necesidades. Muy rara vez hay necesidad de implementar dicha estructura de datos usted mismo (a menos que sea una tarea escolar).
EDITAR: Ahora que ha agregado el requisito "para recuperar cualquier elemento en el búfer por índice", supongo que debe implementar su propia clase (a menos que google-collections o alguna otra biblioteca proporcione uno). Un búfer circular es bastante fácil de implementar, como lo muestra el ejemplo de JeeBee. También puede consultar el código fuente de ArrayBlockingQueue: su código es bastante limpio, solo elimine los métodos de bloqueo y los innecesarios, y agregue métodos para acceder a ellos por índice.
Utilizaría una matriz de T, un puntero de cabeza y cola, y agregar y obtener métodos.
Me gusta: (La búsqueda de errores se deja al usuario)
// Hijack these for simplicity
import java.nio.BufferOverflowException;
import java.nio.BufferUnderflowException;
public class CircularBuffer<T> {
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<String> b = new CircularBuffer<String>(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();
}
}
}
si un lru cache funcionaría, considere simplemente usar 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)
// 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;
}
}
}