Как Вы кодировали бы эффективный Кольцевой буфер в Java или C#?

Я использовал бы ArrayBlockingQueue или одна из других предварительно созданных реализаций Очереди, в зависимости от того, каковы потребности. Очень редко существует потребность реализовать такую структуру данных самостоятельно (если это не школьное присвоение).

РЕДАКТИРОВАНИЕ: Теперь, когда Вы добавили требование, "для получения любого элемента в буфере индексом", я предполагаю, что необходимо реализовать собственный класс (если наборы Google или некоторая другая библиотека не обеспечивают одну). Кольцевой буфер довольно легко реализовать как шоу JeeBee в качестве примера. Можно также посмотреть на исходный код ArrayBlockingQueue - его код является довольно чистым, просто удалите блокировку и ненужные методы, и добавьте методы для доступа к нему индексом.

Просто используйте чужую реализацию:

Наборы Питания Двухсторонняя очередь <T> реализована кольцевым буфером.

библиотека наборов питания неоднородна, но Двухсторонняя очередь является совершенно приемлемым расширяющимся кольцевым буфером.

, Так как Вы указываете, что не хотите расширение и вместо этого требуете перезаписи, которую Вы могли довольно легко изменить код для перезаписи. Это просто включило бы удаление проверки на указатели, являющиеся логически смежным и просто пишущие так или иначе. В то же время частный буфер мог быть сделан только для чтения.

если lru кэш работал бы, рассмотрите просто использование http://java.sun.com/javase/6/docs/api/java/util/LinkedHashMap.html#LinkedHashMap (интервал, %20float, %20boolean) , http://java.sun.com/javase/6/docs/api/java/util/LinkedHashMap.html#removeEldestEntry (java.util. Карта. Запись)

System.Collections.Generic.Queue - это простой кольцевой буфер внутри (T [] с головой и хвостом, как в примере из JeeBee ).

// 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;
        }
    }
}

Вот как я (или сделал) написал эффективный круговой буфер в 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;
    }
}