Java - Ring Buffer

Question

Mam serię transmisji strumieniowych, z których jestem zainteresowany utrzymaniem ostatnich 4 elementów, co oznacza, że ​​chcę mieć możliwość wybrania pierwszego i dodać do końca. Która kolekcja Java jest najlepsza dla tego? Wektor ?

Answer 1

Użyj Queue

Queue<String> qe=new LinkedList<String>(); 

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 

Jest pięć prostych metod elementu() Queue

• - Pobiera, ale nie usuwa, szef tej kolejce.

• oferta (E o) - Wstawia określony element do tej kolejki, jeśli jest możliwe
  .

• peek() - Pobiera, ale nie usuwa, kolejkę tej kolejki , zwracając wartość null, jeśli ta kolejka jest pusta.

• poll() - Pobiera i usuwa nagłówek tej kolejki lub null, jeśli ta kolejka jest pusta.

• remove() - Pobiera i usuwa nagłówek tej kolejki.

Answer 2

Rozważ CircularFifoBuffer z Apache Common.Collections. W przeciwieństwie do Queue, nie musisz utrzymywać ograniczonego rozmiaru podstawowej kolekcji i zawijać ją po osiągnięciu limitu.

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

CircularFifoBuffer zrobi to za ciebie, bo o następujących właściwościach:

• CircularFifoBuffer jest First In First Out bufora o stałej wielkości który zastępuje jego najstarszy element, jeśli pełny.
• Kolejność usuwania CircularFifoBuffer opiera się na zamówieniu ; elementy są usuwane w tej samej kolejności, w jakiej zostały dodane. Kolejność iteracji jest taka sama jak kolejność usuwania.
• Operacje dodawania (obiekt), BoundedFifoBuffer.remove() i BoundedFifoBuffer.get() wszystkie działają w stałym czasie. Wszystkie inne operacje wykonywane są w czasie liniowym lub gorzej.

Należy jednak wziąć pod uwagę również jego ograniczenia - na przykład nie można dodać brakujących serii czasu do tego zbioru, ponieważ nie pozwalają one na zerowanie.

Answer 3

Miałem ten sam problem jakiś czas temu i byłem rozczarowany, ponieważ nie mogłem znaleźć żadnego rozwiązania, które odpowiadałoby moim potrzebom, więc napisałem własną klasę. Szczerze mówiąc, znalazłem wtedy jakiś kod, ale nawet to nie było to, czego szukałem, więc zaadaptowałem to i teraz udostępniam je, tak jak autor tego fragmentu kodu.

EDIT: Jest to oryginalna (choć nieco inaczej) Kod: CircularArrayList for java

nie mam link do źródła, bo to było dawno temu, ale tutaj jest kod:

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

Answer 4

Jeśli trzeba

• O (1) do wprowadzania i usuwania
• O (1) do indeksowania elementów wewnętrznych
• dostęp z jednego wątku tylko
• generyczny typ elementu

następnie można użyć this CircularArrayList for Java w ten sposób (na przykład):

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

Wszystkie te metody działają w czasie O (1).

Answer 5

Ponieważ Java 1.6, istnieje ArrayDeque, który realizuje Queue i wydaje się być szybszy i bardziej wydajny niż pamięć LinkedList i nie ma narzutu synchronizacji gwint ArrayBlockingQueue: od docs API: „Ta klasa jest może być szybszy niż Stack, gdy jest używany jako stos, i szybszy niż LinkedList, gdy jest używany jako kolejka. "

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

Answer 6

Od Guava 15,0 (wydana wrzesień 2013) jest EvictingQueue:

Non-blocking kolejki, która automatycznie evicts elementy z głowy kolejki, gdy próbuje dodać nowe elementy na kolejki i to jest pełne. Kolejka eksmitująca musi mieć skonfigurowany maksymalny rozmiar. Za każdym razem, gdy element jest dodawany do pełnej kolejki, automatycznie usuwana jest jego kolejka z elementu . Różni się to od tradycyjnych ograniczonych kolejek, które blokują lub odrzucają nowe elementy, gdy są pełne.

Ta klasa nie jest wątkowa i nie akceptuje elementów pustych.

Przykład użycia:

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 7

Żaden z poprzednio podanych przykładach realizacji moich potrzeb całkowicie, więc napisałem własną kolejkę, która umożliwia następujące funkcje: iteracji, dostęp do indeksu, indexOf, lastIndexOf, dostać pierwszy , ostatnia, oferta, pozostała pojemność, powiększ pojemność, ostatnia ostatnia, najpierw usuń, wstaw/dodaj element, usuń/usuń element, subQueueCopy, subArrayCopy, Aray, migawka, podstawowe wielkości, usuń lub zawiera.

EjectingQueue

EjectingIntQueue

Answer 8

Bardzo interesujący projekt jest disruptor. Ma bufor pierścieniowy i jest używany z tego, co wiem w aplikacjach finansowych.

Zobacz tutaj: code of ringbuffer