Comment coder un tampon circulaire efficace en Java ou C#

C'est comment je l' (ou a fait) écrire un tampon circulaire efficace en Java. Il est soutenu par un tableau simple. Pour mon cas d'utilisation particulier, j'avais besoin d'un débit simultané élevé, donc j'ai utilisé le CAS pour l'attribution de l'indice. J'ai alors créé des mécanismes pour des copies fiables, y compris une copie CAS de l'intégralité du tampon. J'ai utilisé ce dans un cas qui est décrit plus en détail dans bref article.

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

je voudrais utiliser ArrayBlockingQueue ou l'une des autres implémentations de la file d'attente préconstruite, selon les besoins. Très rarement, il est nécessaire de mettre en œuvre vous-même une telle structure de données (à moins que ce ne soit un devoir scolaire).

EDIT: maintenant que vous avez ajouté l'exigence "pour récupérer n'importe quel élément dans le buffer par index", je suppose que vous devez implémenter votre propre classe (sauf si google-collections ou une autre bibliothèque fournit un). Un circular buffer est assez facile à mettre en œuvre, comme le montre L'exemple de JeeBee. Vous pouvez également regarder le code source de ArrayBlockingQueue - son code est assez propre, il suffit de supprimer le verrouillage et les méthodes inutiles, et ajouter des méthodes pour y accéder par index.

Ici est un prêt-à-utiliser CircularArrayList mise en œuvre pour Java que j'utilise dans le code de production. En outrepassant AbstractList de la manière recommandée par Java, il prend en charge toutes les fonctionnalités que vous attendez d'une implémentation de liste standard dans le cadre Java Collections (type d'élément générique, sous-liste, itération, etc.).).

La suite d'appels complet en O(1):

• add(item) - ajoute à la fin de la liste
• enlever(0) - supprime à partir de début de liste
• get(i)): récupère l'élément aléatoire dans la liste

utilisez Java ArrayDeque

il suffit D'utiliser l'implémentation de quelqu'un d'autre:

Collections Deque<T> est implémenté par un tampon circulaire.

la bibliothèque de power collections est inégale, mais la Deque est parfaitement acceptable.

puisque vous indiquez que vous ne voulez pas d'expansion et que vous voulez plutôt réécrire, vous pouvez assez facilement modifier le code pour réécrire. Il s'agirait simplement de supprimer le chèque pour le les pointeurs étant logiquement adjacents et n'écrivant que de toute façon. Dans le même temps, le tampon privé ne pouvait être utilisé qu'en lecture seule.

Système.Collection.Générique.Queue - est un tampon circulaire simple à l'intérieur (T [] avec la tête et la queue, comme dans exemple de JeeBee