자바의 링 버퍼

자바의 링 버퍼

---

스트리밍 시계열이 있는데, 그중 마지막 4 개 요소를 유지하는 데 관심이 있습니다. 즉, 첫 번째 요소를 팝하고 끝에 추가 할 수 있기를 원합니다. 내장으로 필요한 것은 링 버퍼 입니다.

이에 가장 구매 한 Java 컬렉션은 무엇입니까? 벡터?

---

Apache Common.Collections의 CircularFifoBuffer 를 고려하십시오 . Queue 와 달리 기본 컬렉션의 크기를 유지하고 제한에 접근하면 래핑 할 필요가 없습니다.

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

CircularFifoBuffer는 다음 속성으로 인해이 작업을 수행합니다.

• CircularFifoBuffer는 가장 오래된 요소가 가득 차면 대체 하는 고정 크기의 선입 선출 버퍼입니다 .
• CircularFifoBuffer의 순서는 순서를 기반으로합니다. 요소는 추가 된 순서대로 제거됩니다. 반복 순서는 처분 순서와 동일합니다.
• add (Object), BoundedFifoBuffer.remove () 및 BoundedFifoBuffer.get () 작업은 모두 시간에 수행 됩니다. 다른 모든 작업은 선형 시간 또는 더 나쁘게 수행됩니다.

그러나 제한 사항도 있습니다. 예를 들어 null을 허용하지 않기 때문에 컬렉션에 누락 된 시간이 추가 될 수 없습니다.

참고 : 현재 공통 컬렉션 (4. *)을 사용하는 경우 많은 경우를 사용합니다. 이렇게 :

Queue buf = new CircularFifoQueue(4);

---

Guava 15.0 (2013 년 9 월 출시)부터 EvictingQueue 가 있습니다 .

큐에 새 요소를 추가 할 때 큐가 가득 찼을 때 큐의 헤드에서 요소를 자동으로 제거하는 비 차단 큐입니다. 제거 대기열은 최대 크기로 구성해야합니다. 요소가 전체 큐에 추가 될 때마다 큐는 자동으로 헤드 요소를 제거합니다. 이는 차단 된 차단 차단하는 기존의 경계 큐와 차단합니다.

이 클래스는 형식으로부터 안전하지 않은 요소를 허용하지 않습니다.

사용 예 :

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]

---

자바 1.6 이후,이 ArrayDeque되는 구현, Queue더 빨리 메모리 ,보다 것처럼, LinkedList와의 동기화 오버 헤드가없는 ArrayBlockingQueueAPI를 워드 프로세서에서 : "로 때이 클래스는 빠른 스택보다 가능성이 많고 스택이 있고 빠르게 스택 할 때 LinkedList보다 빠릅니다. "

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

---

필요한 경우

• O (1) 삽입 및 제거
• 내부 요소에 대한 O (1) 인덱싱
• 단일 단일에서만 액세스
• 일반 요소 유형

그런 다음 다음 과 같은 방식으로 Java 용 CircularArrayList를 사용할 수 있습니다 (예 :

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

이 모든 메서드는 O (1)에서 실행됩니다.

---

얼마 전 같은 문제가 있었는데 내 필요에 맞는 솔루션을 수 없어서 내 자신의 수업을 작성했기 때문에 실망했습니다. 솔직히 그랬는데 내가 몇 가지 코드를 찾았지만 그것이 내가 계획하는 것이 아니었기 때문에 코드 작성자가 랬던 것처럼 수정하고 이제 공유하고 있습니다.

편집 : 이것은 원본 (약간 다르지만) 코드입니다 : CircularArrayList for java

시간 전 이었기 때문에 소스의 링크가 없지만 다음은 코드입니다.

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

---

매우 흥미로운 프로젝트는 파괴자입니다. 링 버퍼가 가상화 된 금융 애플리케이션에서 내가 아는 바에서 사용됩니다.

여기를 형광 : 링 버퍼의 코드

Guava의 EvictingQueue와 ArrayDeque를 모두 확인했습니다.

ArrayDeque는 가득 차면 성장을 제한하지 않습니다.

EvictingQueue는 약속 한대로 수행하지만 내부적으로 Deque를 사용하여 사물을 저장하고 메모리를 제한합니다.

따라서 메모리가 제한되는 것에 관심이 있습니다. EvictingQueue는 내부 구성 (더 큰 크기)을 사용합니다.

간단하고 메모리 용이성은 jmonkeyengine 에서 훔칠 수 있습니다 . 그대로 복사

import java.util.Iterator;
import java.util.NoSuchElementException;

public class RingBuffer<T> implements Iterable<T> {

  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<T> iterator() {
    return new RingBufferIterator();
  }

  // an iterator, doesn't implement remove() since it's optional
  private class RingBufferIterator implements Iterator<T> {

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

---

이전에 제공된 예제 중 어느 것도 내 요구를 완전히 충족하지 못했기 때문에 다음 기능을 허용하는 자체 대기열을 작성했습니다. 먼저, 요소를 큐에 넣거나 추가하고, 요소를 큐에서 제거 / 제거, subQueueCopy, subArrayCopy, toArray, 스냅 샷, 크기와 같은 기본 사항, 제거 또는 포함을 수행합니다.

EjectingQueue

EjectingIntQueue

---

대기열 사용

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

대기열 에는 5 가지 간단한 방법이 있습니다.

• element ()-이 큐의 헤드를 검색하지만 제거하지는 않습니다.

• offer (E o)-
  가능한 경우 지정된 요소를이 큐에 삽입 합니다.

• peek ()-이 큐의 헤드를 검색하지만 제거하지는 않으며이 큐가 비어 있으면 null을 반환합니다.

• poll ()-이 큐의 헤드를 검색하고 제거합니다.이 큐가 비어 있으면 null입니다.

• remove ()-이 큐의 헤드를 검색하고 제거합니다.

참고 URL : https://stackoverflow.com/questions/7266042/ring-buffer-in-java