我想要一个实现固定大小循环缓冲区的简单类.它应该是高效的,容易在眼睛上,一般打字.
编辑:目前它不需要具备MT功能.我总是可以在以后添加一个锁,在任何情况下它都不会是高并发性的.
方法应该是:.Add和我猜.List,我检索所有条目.第二个想法,我认为应该通过索引器完成检索.在任何时候,我都希望能够通过索引检索缓冲区中的任何元素.但请记住,从一个时刻到下一个Element [n]可能会有所不同,因为循环缓冲区填满并翻转.
这不是一个堆栈,它是一个循环缓冲区.关于"溢出":我希望内部会有一个包含项目的数组,随着时间的推移,缓冲区的头部和尾部将围绕该固定数组旋转.但这应该是用户不可见的.应该没有外部可检测的"溢出"事件或行为.
这不是学校作业 - 它通常用于MRU缓存或固定大小的事务或事件日志.
我会使用T数组,头部和尾部指针,以及添加和获取方法.
喜欢:(漏洞留给用户)
// 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(); } } }
这是我会怎样(或没有)用Java编写高效的循环缓冲区.它由一个简单的数组支持.对于我的特定用例,我需要高并发吞吐量,所以我使用CAS来分配索引.然后,我创建了可靠副本的机制,包括整个缓冲区的CAS副本.我在短篇文章中更详细地概述了一个案例.
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; } }
这是我在生产代码中使用的Java的现成的CircularArrayList实现。通过以Java建议的方式重写AbstractList,它支持Java Collections Framework中标准List实现所期望的所有功能(通用元素类型,subList,迭代等)。
以下调用在O(1)中完成:
add(item)-在列表末尾添加
remove(0)-从列表的开头删除
get(i)-检索列表中的随机元素