Java – Tampon en anneau

J’ai une série chronologique en streaming, dont je souhaite garder les 4 derniers éléments, ce qui signifie que je veux pouvoir faire apparaître le premier et append à la fin. Quelle collection Java est la meilleure pour cela? Vecteur?

Envisagez CircularFifoBuffer d’Apache Common.Collections . Contrairement à la file d’ attente, vous n’avez pas à conserver la taille limitée de la collection sous-jacente et à l’envelopper une fois que vous avez atteint 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 à cause des propriétés suivantes:

  • CircularFifoBuffer est un tampon premier entré, premier sorti avec une taille fixe qui remplace son élément le plus ancien s’il est plein.
  • L’ordre de suppression d’un CircularFifoBuffer est basé sur l’ordre d’insertion; les éléments sont supprimés dans l’ordre dans lequel ils ont été ajoutés. L’ordre d’itération est identique à l’ordre de suppression.
  • Les opérations add (Object), BoundedFifoBuffer.remove () et BoundedFifoBuffer.get () fonctionnent toutes à temps constant . Toutes les autres opérations fonctionnent dans le temps linéaire ou pire.

Cependant, vous devez également tenir compte de ses limites – par exemple, vous ne pouvez pas append de séries de temps manquantes à cette collection car elle n’autorise pas les valeurs NULL.

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

Une queue non bloquante qui expulse automatiquement les éléments de la tête de la queue lors de la tentative d’ajout de nouveaux éléments dans la queue et est pleine. Une queue expulsante doit être configurée avec une taille maximale. Chaque fois qu’un élément est ajouté à une queue complète, la queue supprime automatiquement son élément principal. Ceci est différent des files d’attente limitées classiques, qui bloquent ou rejettent de nouveaux éléments lorsqu’ils sont pleins.

Cette classe n’est pas adaptée aux threads et n’accepte pas les éléments nuls.

Exemple d’utilisation:

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

Depuis Java 1.6, il existe ArrayDeque , qui implémente Queue et semble être plus rapide et plus efficace en ArrayDeque mémoire qu’une LinkedList et n’a pas la surcharge de synchronisation des threads de ArrayBlockingQueue : à partir des documents API: “Cette classe est probablement plus rapide que Emstackr lorsqu’il est utilisé en tant que stack et plus rapide que LinkedList lorsqu’il est utilisé en tant que queue. “

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

Si tu as besoin

  • O (1) insertion et retrait
  • O (1) indexation aux éléments intérieurs
  • access à partir d’un seul thread uniquement
  • type d’élément générique

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

 CircularArrayList buf = new CircularArrayList(4); buf.add("A"); buf.add("B"); buf.add("C"); buf.add("D"); // ABCD Ssortingng pop = buf.remove(0); // A <- BCD buf.add("E"); // BCDE String interiorElement = buf.get(i); 

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

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

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

Je n’ai pas le lien de la source car il y a un temps, 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 extends AbstractList implements RandomAccess { private final int n; // buffer length private final List buf; // a List implementing RandomAccess private int leader = 0; private int size = 0; public CircularArrayList(int capacity) { n = capacity + 1; buf = new ArrayList(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 Ssortingng toSsortingng() { int i = wrapIndex(leader - size()); SsortingngBuilder str = new SsortingngBuilder(size()); for(; i != leader; i = wrapIndex(++i)){ str.append(buf.get(i)); } return str.toSsortingng(); } 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 resortingeving the newest element. The Circular Array list is empty."); return buf.get(i); } } 

Aucun des exemples donnés ne répondait complètement à mes besoins, alors j’ai écrit ma propre queue qui permet les fonctionnalités suivantes: itération, indexation, indexOf, lastIndexOf, premier, dernier, offre, capacité restante, capacité, dé-queue en premier lieu, élément de mise en queue / d’ajout, élément dequeue / remove, subQueueCopy, subArrayCopy, toArray, image instantanée, notions de base telles que la taille, supprimer ou contenir.

ÉjecterQueue

EjectingIntQueue

Un projet très intéressant est perturbateur. Il a un ringbuffer et est utilisé à partir de ce que je sais dans les applications financières.

Voir ici: code de ringbuffer

J’ai vérifié les deux EvictingQueue et ArrayDeque de Guava.

ArrayDeque ne limite pas la croissance s’il est plein, il double sa taille et n’agit donc pas comme un tampon de sonnerie.

EvictingQueue fait ce qu’il promet mais utilise en interne un Deque pour stocker des choses et délimiter la mémoire.

Par conséquent, si vous tenez à ce que la mémoire soit limitée, ArrayDeque ne remplit pas votre promesse. Si vous vous souciez du nombre d’objects, EvictingQueue utilise la composition interne (taille d’object plus grande).

Un simple et efficace mémoire peut être volé à jmonkeyengine . copie textuelle

 import java.util.Iterator; import java.util.NoSuchElementException; public class RingBuffer implements Iterable { private T[] buffer; // queue elements private int count = 0; // number of elements on queue private int indexOut = 0; // index of first element of queue private int indexIn = 0; // index of next available slot // cast needed since no generic array creation in Java public RingBuffer(int capacity) { buffer = (T[]) new Object[capacity]; } public boolean isEmpty() { return count == 0; } public int size() { return count; } public void push(T item) { if (count == buffer.length) { throw new RuntimeException("Ring buffer overflow"); } buffer[indexIn] = item; indexIn = (indexIn + 1) % buffer.length; // wrap-around count++; } public T pop() { if (isEmpty()) { throw new RuntimeException("Ring buffer underflow"); } T item = buffer[indexOut]; buffer[indexOut] = null; // to help with garbage collection count--; indexOut = (indexOut + 1) % buffer.length; // wrap-around return item; } public Iterator iterator() { return new RingBufferIterator(); } // an iterator, doesn't implement remove() since it's optional private class RingBufferIterator implements Iterator { private int i = 0; public boolean hasNext() { return i < count; } public void remove() { throw new UnsupportedOperationException(); } public T next() { if (!hasNext()) { throw new NoSuchElementException(); } return buffer[i++]; } } } 

Utiliser une queue

 Queue qe=new LinkedList(); qe.add("a"); qe.add("b"); qe.add("c"); qe.add("d"); System.out.println(qe.poll()); //returns a System.out.println(qe.poll()); //returns b System.out.println(qe.poll()); //returns c System.out.println(qe.poll()); //returns d 

Il y a cinq méthodes simples d’une queue

  • element () – Récupère, mais ne supprime pas, la tête de cette queue.

  • offre (E o) – Insère l’élément spécifié dans cette queue, si
    possible.

  • peek () – Récupère, mais ne supprime pas, la tête de cette queue, en renvoyant null si cette file est vide.

  • poll () – Récupère et supprime la tête de cette queue ou null si cette queue est vide.

  • remove () – Récupère et supprime la tête de cette queue.