44

固定サイズの循環 bufferを実装する単純なクラスが必要です。効率的で、見やすく、一般的に型付けされている必要があります。

今のところ、MT 対応である必要はありません。後でいつでもロックを追加できますが、いずれにしても同時実行性は高くありません。

メソッドは次のようにする必要があります。すべてのエントリを取得する場所です.Add().List()考え直して、検索はインデクサーを介して行うべきだと思います。いつでもバッファ内の任意の要素をindexで取得できるようにしたいと考えています。ただし、循環バッファがいっぱいになってロールオーバーするため、ある瞬間から次の Element[n] が異なる可能性があることに注意してください。これはstackではなく、循環バッファーです。

オーバーフロー」について: 内部的にはアイテムを保持する配列があり、時間の経過とともにバッファの先頭末尾がその固定配列を中心に回転することが予想されます。しかし、それはユーザーから見えないはずです。外部から検出可能な「オーバーフロー」イベントまたは動作があってはなりません。

これは学校の課題ではありません。通常、MRU キャッシュ、固定サイズのトランザクション、またはイベント ログに使用されます。

4

13 に答える 13

22

Tの配列、ヘッドポインターとテールポインターを使用し、メソッドを追加および取得します。

のように:(バグハンティングはユーザーに任されています)

// 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();
    }
  }
}
于 2009-02-26T11:33:19.140 に答える
8

これは、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;
    }
}
于 2010-05-24T23:01:58.640 に答える
4

必要に応じて、 ArrayBlockingQueueまたは他のビルド済み Queue 実装のいずれかを使用します。そのようなデータ構造を自分で実装する必要があることはほとんどありません (学校の課題でない限り)。

編集:「バッファ内の要素をインデックスで取得する」という要件を追加したので、独自のクラスを実装する必要があると思います(google-collectionsまたは他のライブラリが提供しない限り)。JeeBee の例が示すように、循環バッファーは非常に簡単に実装できます。また、ArrayBlockingQueue のソース コードを確認することもできます。そのコードは非常にクリーンで、ロック メソッドと不要なメソッドを削除し、インデックスでアクセスするメソッドを追加するだけです。

于 2009-02-26T11:58:29.640 に答える
4

Java のArrayDequeを使用する

于 2011-12-08T07:31:45.447 に答える
4

これは、私が本番コードで使用するJava用のすぐに使用できるCircularArrayList 実装です。Java 推奨の方法で AbstractList をオーバーライドすることにより、Java Collections Framework の標準的な List 実装に期待されるすべての機能 (汎用要素型、subList、反復など) をサポートします。

次の呼び出しは O(1) で完了します。

  • add(item) - リストの最後に追加
  • remove(0) - リストの先頭から削除します
  • get(i) - リスト内のランダムな要素を取得します
于 2011-07-03T21:42:19.897 に答える
2

他の人の実装を使用するだけです:

Power Collections Deque<T>は、循環バッファーによって実装されます。

パワー コレクション ライブラリはまだらですが、Deque は拡張循環バッファとして完全に受け入れられます。

拡張を希望せず、代わりに上書きを希望することを示しているため、コードを簡単に変更して上書きすることができます。これには、ポインターが論理的に隣接していることのチェックを削除し、とにかく書き込むだけで済みます。同時に、プライベート バッファを読み取り専用にすることができます。

于 2009-02-26T19:52:58.610 に答える
1

System.Collections.Generic.Queue-内部の単純な循環バッファーです( JeeBeeのサンプルと同様に、ヘッドとテールを備えたT [] )。

于 2010-05-10T18:57:35.750 に答える
0

これは、Apache 共通コレクションの BoundedFifoBuffer を使用する別の実装です。以下のクラスは非推奨であるため、Apache の最新の JAR を使用している場合は、CircularFifoQueue を使用してください。

    BoundedFifoBuffer apiCallHistory = new BoundedFifoBuffer(20);

    for(int i =1 ; i < 25; i++){

        if(apiCallHistory.isFull()){
          System.out.println("removing :: "+apiCallHistory.remove());
        }
        apiCallHistory.add(i);

}
于 2014-06-04T02:03:21.727 に答える
0

これは、私が自分で使用するためにコーディングした実装ですが、役に立つ可能性があります。

バッファーには、アイテムの最大固定セットが含まれます。セットは円形で、古いアイテムは自動的に削除されます。呼び出し元は、絶対増分インデックス (long) によってアイテムの末尾を取得できますが、時間的に離れすぎた呼び出し間でアイテムが失われる可能性があります。このクラスは完全にスレッドセーフです。

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;
        }
    }
}
于 2014-04-27T17:29:29.583 に答える
-8
// 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;
        }
    }
}
于 2010-05-22T21:25:43.770 に答える