Buffer en anneau en Java

Question

J'ai une série temporelle en continu, dont je souhaite conserver les 4 derniers éléments, ce qui signifie que je veux être capable d'extraire le premier et de l'ajouter à la fin. Essentiellement, ce dont j'ai besoin est un tampon circulaire .

Quelle collection Java est la meilleure pour cela ? Vecteur ?

Answer 1

Pensez à CircularFifoBuffer d'Apache Common.Collections . Contrairement à File d'attente vous n'avez pas à maintenir la taille limitée de la collection sous-jacente et à l'emballer dès que vous atteignez la limite.

Buffer buf = new CircularFifoBuffer(4);
buf.add("A");
buf.add("B");
buf.add("C");
buf.add("D"); //ABCD
buf.add("E"); //BCDE

CircularFifoBuffer le fera pour vous grâce aux propriétés suivantes :

• CircularFifoBuffer est un tampon "premier entré, premier sorti" de taille fixe taille fixe qui remplace son élément le plus ancien s'il est plein.
• L'ordre de retrait d'un CircularFifoBuffer est basé sur l'ordre d'insertion. d'insertion ; les éléments sont retirés dans le même ordre que celui dans lequel ils ont été ajoutés. L'ordre d'itération est le même que l'ordre de retrait.
• Les opérations add(Object), BoundedFifoBuffer.remove() et BoundedFifoBuffer.get() opérations tous fonctionnent en temps constant . Toutes les autres opérations s'effectuent en temps linéaire ou pire.

Cependant, vous devez également tenir compte de ses limites - par exemple, vous ne pouvez pas ajouter de séries chronologiques manquantes à cette collection car elle n'autorise pas les valeurs nulles.

NOTE : Lors de l'utilisation du courant Collections communes (4.*), vous devez utiliser Queue. Comme ceci :

Queue buf = new CircularFifoQueue(4);

Answer 2

Depuis Guava 15.0 (publié en septembre 2013), il y a EvictingQueue :

Une file d'attente non bloquante qui expulse automatiquement les éléments de la tête de la file lorsqu'on tente d'y ajouter de nouveaux éléments. de la file d'attente lorsqu'on tente d'ajouter de nouveaux éléments dans la file d'attente et elle est pleine. Une file d'attente avec éviction doit être configurée avec une taille maximale. Chaque fois qu'un élément est ajouté à une file pleine, la file retire automatiquement son élément de tête. automatiquement son élément de tête. Ceci est différent des files d'attente conventionnelles conventionnelles, qui bloquent ou rejettent les nouveaux éléments lorsqu'elles sont pleines.

Cette classe n'est pas thread-safe, et n'accepte pas les éléments nuls.

Exemple d'utilisation :

EvictingQueue<String> queue = EvictingQueue.create(2);
queue.add("a");
queue.add("b");
queue.add("c");
queue.add("d");
System.out.print(queue); //outputs [c, d]

Answer 3

Depuis Java 1.6, il existe ArrayDeque qui met en œuvre Queue et semble être plus rapide et plus efficace en termes de mémoire qu'une LinkedList et n'a pas la surcharge de synchronisation des threads de l'option ArrayBlockingQueue : à partir des documents de l'API : "Cette classe est susceptible d'être plus rapide que Stack lorsqu'elle est utilisée comme une pile, et plus rapide que LinkedList lorsqu'elle est utilisée comme une file d'attente".

final Queue<Object> q = new ArrayDeque<Object>();
q.add(new Object()); //insert element
q.poll(); //remove element

Answer 4

Si vous avez besoin

• Insertion et retrait O(1)
• Indexation O(1) des éléments intérieurs
• accès à partir d'un seul thread seulement
• type d'élément générique

alors vous pouvez utiliser cette CircularArrayList pour Java de cette manière (par exemple) :

CircularArrayList<String> buf = new CircularArrayList<String>(4);

buf.add("A");
buf.add("B");
buf.add("C");
buf.add("D"); // ABCD

String pop = buf.remove(0); // A <- BCD
buf.add("E"); // BCDE

String interiorElement = buf.get(i);

Toutes ces méthodes s'exécutent en O(1).

Answer 5

J'ai eu le même problème il y a quelque temps et j'ai été déçu parce que je n'ai pas trouvé de solution qui réponde à mes besoins, alors j'ai écrit ma propre classe. Honnêtement, j'ai trouvé du code à l'époque, mais ce n'était pas ce que je cherchais, alors je l'ai adapté et maintenant je le partage, tout comme l'auteur de ce code.

EDIT : C'est le code original (bien que légèrement différent) : CircularArrayList pour java

Je n'ai pas le lien de la source car c'était il y a longtemps, mais voici le code :

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.RandomAccess;

public class CircularArrayList<E> extends AbstractList<E> implements RandomAccess {

private final int n; // buffer length
private final List<E> buf; // a List implementing RandomAccess
private int leader = 0;
private int size = 0;

public CircularArrayList(int capacity) {
    n = capacity + 1;
    buf = new ArrayList<E>(Collections.nCopies(n, (E) null));
}

public int capacity() {
    return n - 1;
}

private int wrapIndex(int i) {
    int m = i % n;
    if (m < 0) { // modulus can be negative
        m += n;
    }
    return m;
}

@Override
public int size() {
    return this.size;
}

@Override
public E get(int i) {
    if (i < 0 || i >= n-1) throw new IndexOutOfBoundsException();

    if(i > size()) throw new NullPointerException("Index is greater than size.");

    return buf.get(wrapIndex(leader + i));
}

@Override
public E set(int i, E e) {
    if (i < 0 || i >= n-1) {
        throw new IndexOutOfBoundsException();
    }
    if(i == size()) // assume leader's position as invalid (should use insert(e))
        throw new IndexOutOfBoundsException("The size of the list is " + size() + " while the index was " + i
                +". Please use insert(e) method to fill the list.");
    return buf.set(wrapIndex(leader - size + i), e);
}

public void insert(E e)
{
    int s = size();     
    buf.set(wrapIndex(leader), e);
    leader = wrapIndex(++leader);
    buf.set(leader, null);
    if(s == n-1)
        return; // we have replaced the eldest element.
    this.size++;

}

@Override
public void clear()
{
    int cnt = wrapIndex(leader-size());
    for(; cnt != leader; cnt = wrapIndex(++cnt))
        this.buf.set(cnt, null);
    this.size = 0;      
}

public E removeOldest() {
    int i = wrapIndex(leader+1);

    for(;;i = wrapIndex(++i)) {
        if(buf.get(i) != null) break;
        if(i == leader)
            throw new IllegalStateException("Cannot remove element."
                    + " CircularArrayList is empty.");
    }

    this.size--;
    return buf.set(i, null);
}

@Override
public String toString()
{
    int i = wrapIndex(leader - size());
    StringBuilder str = new StringBuilder(size());

    for(; i != leader; i = wrapIndex(++i)){
        str.append(buf.get(i));
    }
    return str.toString();
}

public E getOldest(){
    int i = wrapIndex(leader+1);

    for(;;i = wrapIndex(++i)) {
        if(buf.get(i) != null) break;
        if(i == leader)
            throw new IllegalStateException("Cannot remove element."
                    + " CircularArrayList is empty.");
    }

    return buf.get(i);
}

public E getNewest(){
    int i = wrapIndex(leader-1);
    if(buf.get(i) == null)
        throw new IndexOutOfBoundsException("Error while retrieving the newest element. The Circular Array list is empty.");
    return buf.get(i);
}
}