您将如何用 Java 或 C# 编写高效的循环缓冲区？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/590069/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How would you code an efficient Circular Buffer in Java or C#?
提问by Cheeso
I want a simple class that implements a fixed-size circular buffer. It should be efficient, easy on the eyes, generically typed.
我想要一个实现固定大小循环缓冲区的简单类。它应该是高效的、易于理解的、通用的类型。
For now it need not be MT-capable. I can always add a lock later, it won't be high-concurrency in any case.
现在它不需要支持MT。以后可以随时加锁，反正不会高并发。
Methods should be: .Add()and I guess .List(), where I retrieve all the entries. On second thought, Retrieval I think should be done via an indexer. At any moment I will want to be able to retrieve any element in the buffer by index. But keep in mind that from one moment to the next Element[n] may be different, as the circular bufferfills up and rolls over. This isn't a stack, it's a circular buffer.
方法应该是：.Add()我猜.List()，在那里我检索所有条目。再想一想，检索我认为应该通过索引器完成。在任何时候，我都希望能够通过index检索缓冲区中的任何元素。但请记住，从一个时刻到下一个 Element[n] 可能会有所不同，因为循环缓冲区会填满并滚动。这不是堆栈，而是循环缓冲区。
Regarding "overflow": I would expect internally there would be an array holding the items, and over time the headand tailof the buffer will rotate around that fixed array. But that should be invisible from the user. There should be no externally-detectable "overflow" event or behavior.
关于“溢出”：我希望在内部会有一个保存项目的数组，随着时间的推移，缓冲区的头部和尾部将围绕该固定数组旋转。但这对用户来说应该是不可见的。不应有外部可检测的“溢出”事件或行为。
This is not a school assignment - it is most commonly going to be used for a MRU cacheor a fixed-size transaction or event log.
这不是学校作业 - 它最常用于MRU 缓存或固定大小的事务或事件日志。
采纳答案by JeeBee
I would use an array of T, a head and tail pointer, and add and get methods.
我会使用一个 T 数组、一个头尾指针，以及 add 和 get 方法。
Like: (Bug hunting is left to the user)
喜欢：（Bug 搜索留给用户）
// HiHyman 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();
}
}
}
回答by Esko Luontola
I would use ArrayBlockingQueueor one of the other prebuilt Queue implementations, depending on what the needs are. Very rarely there is need to implement such a data structure yourself (unless it's a school assignment).
我会根据需要使用ArrayBlockingQueue或其他预构建的队列实现之一。很少需要自己实现这样的数据结构（除非是学校作业）。
EDIT: Now that you have added the requirement "to retrieve any element in the buffer by index", I suppose that you need to implement your own class (unless google-collectionsor some other library provides one). A circular buffer is quite easy to implement, as JeeBee's example shows. You may also look at ArrayBlockingQueue's source code - its code is quite clean, just remove the locking and unneeded methods, and add methods for accessing it by index.
编辑：既然您已经添加了“通过索引检索缓冲区中的任何元素”的要求，我想您需要实现自己的类（除非google-collections或其他一些库提供了一个）。正如 JeeBee 的示例所示，循环缓冲区很容易实现。您也可以查看 ArrayBlockingQueue 的源代码 - 它的代码非常干净，只需删除锁定和不需要的方法，并添加通过索引访问它的方法。
回答by ShuggyCoUk
Just use someone else's implementation:
只需使用别人的实现：
The Power CollectionsDeque<T>is implemented by a circular buffer.
The power collections library is patchy but the Deque is perfectly acceptable expanding circular buffer.
power collections 库不完整，但 Deque 是完全可以接受的扩展循环缓冲区。
Since you indicate that you do not want expansion and instead desire overwrite you could fairly easily modify the code to overwrite. This would simply involve removing the check for the pointers being logically adjacent and just writing anyway. At the same time the private buffer could be made readonly.
由于您表示不想扩展而是希望覆盖，因此您可以相当轻松地修改代码以进行覆盖。这将只涉及删除对逻辑上相邻的指针的检查，并且无论如何都可以写入。同时，可以将私有缓冲区设为只读。
回答by Ray Tayek
if an lru cache would work, consider just using 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)
如果 lru 缓存可以工作，请考虑使用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)
回答by Zakus
System.Collections.Generic.Queue - is simple circular buffer inside (T[] with head and tail, just like in sample from JeeBee).
System.Collections.Generic.Queue - 内部是简单的循环缓冲区（T[] 带有头部和尾部，就像来自 JeeBee 的示例一样）。
回答by Francis
// 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;
}
}
}
回答by Scott S. McCoy
This is how I would (or did)write an efficient circular buffer in Java. It's backed by a simple array. For my particular use case, I needed high concurrent throughput, so I used CAS for allocation of the index. I then created mechanisms for reliable copies including a CAS copy of the entire buffer. I used this in a case which is outlined in greater detail in short article.
这就是我将（或确实）在 Java 中编写高效循环缓冲区的方式。它由一个简单的数组支持。对于我的特定用例，我需要高并发吞吐量，因此我使用 CAS 来分配索引。然后我创建了可靠副本的机制，包括整个缓冲区的 CAS 副本。我在一篇短文中更详细地概述的案例中使用了它。
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;
}
}
回答by Museful
Here is a ready-to-use CircularArrayList implementation for Javawhich I use in production code. By overriding AbstractList in the Java-recommended way, it supports all functionality you would expect from a standard List implementation in the Java Collections Framework (generic element type, subList, iteration etc.).
这是我在生产代码中使用的Java 的即用型CircularArrayList 实现。通过以 Java 推荐的方式覆盖 AbstractList，它支持您期望从 Java 集合框架中的标准 List 实现中获得的所有功能（通用元素类型、子列表、迭代等）。
The following calls complete in O(1):
以下调用在 O(1) 中完成：
- add(item) - adds at end of list
- remove(0) - removes from beginning of list
- get(i) - retrieves random element in list
- add(item) - 在列表末尾添加
- remove(0) - 从列表的开头删除
- get(i) - 检索列表中的随机元素
回答by Ashwin Jayaprakash
Use Java's ArrayDeque
使用 Java 的ArrayDeque
回答by Simon Mourier
Here is an implementation I've coded for my own use but that could be useful.
这是我为自己使用而编码的实现，但这可能很有用。
The buffer contains a maximum fixed set of items. The set is circular, old items are automatically removed. The caller can get items tail by an absolute incremental index (a long), but items may have been lost between calls too distant in time. This class is fully thread-safe.
缓冲区包含最大的固定项目集。套装是圆形的，旧物品会自动移除。调用者可以通过绝对增量索引（长）获取项目尾部，但项目可能在时间太远的调用之间丢失。这个类是完全线程安全的。
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;
}
}
}
