Java中的环缓冲区

Question

我有一个流时间序列，其中我有兴趣保留最后4个元素，这意味着我希望能够弹出第一个元素，并添加到最后。实际上，我需要的是一个环缓冲区。

哪个Java集合是最好的?向量?

Answer 1

考虑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是一个先入先出缓冲区，具有固定的size在满的情况下替换最老的元素。
• CircularFifoBuffer的移除顺序是基于插入的秩序;元素按照它们原来的顺序被删除补充道。迭代顺序与移除顺序相同。
• add(Object)， BoundedFifoBuffer.remove()和BoundedFifoBuffer.get()操作都在常量时间内执行。所有其他操作在线性时间内执行或更差。

但是你也应该考虑到它的局限性——例如，你不能将缺失的时间序列添加到这个集合中，因为它不允许为空。

注意:当使用当前的公共集合(4.*)时，你必须使用Queue。这样的:

Queue buf = new CircularFifoQueue(4);

Answer 2

自Guava 15.0(2013年9月发布)以来，有了evtingqueue:

一个非阻塞队列，自动从头部移除元素在尝试向队列和队列中添加新元素时已经满了。必须为退出队列配置最大大小。每当一个元素被添加到一个已满的队列中时，该队列就会自动加入移除头部元素。这与传统的有界不同队列，当满时阻塞或拒绝新元素。

这个类不是线程安全的，不接受null元素。

使用例子:

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

自从Java 1.6以来，有ArrayDeque，它实现了Queue，似乎比LinkedList更快，内存效率更高，并且没有ArrayBlockingQueue的线程同步开销:来自API文档:"这个类在用作堆栈时可能比Stack更快，并且在用作队列时比LinkedList更快。"

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

Answer 4

如果你需要

• O(1)插入和移除
• 0(1)内部元素索引
• 单线程访问
• 元素类型

，那么你可以这样使用CircularArrayList for Java:

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

所有这些方法的运行时间为0(1)。

Answer 5

我以前也遇到过同样的问题，我很失望，因为我找不到任何满足我需要的解决方案，所以我自己写了一个类。老实说，我当时确实找到了一些代码，但即使那也不是我想要的，所以我改编了它，现在我正在分享它，就像那段代码的作者所做的那样。

编辑:这是原始的(虽然略有不同)代码: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);
}
}

Answer 6

一个非常有趣的项目是disruptor。它有一个环缓冲区，据我所知，它被用于金融应用程序。

查看这里:ringbuffer

的代码

我检查了Guava的evingqueue和ArrayDeque。

ArrayDeque不限制增长，如果它是满的，它将加倍大小，因此不完全像一个环形缓冲区。

EvictingQueue做了它承诺的事情，但在内部使用Deque来存储东西，只是限制内存。

因此，如果你关心内存是有界的，ArrayDeque并没有履行你的承诺。如果你关心对象的数量，使用内部组合(更大的对象大小)。

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

Answer 7

前面给出的示例都不能完全满足我的需求，所以我编写了自己的队列，允许以下功能:迭代，索引访问，indexOf, lastIndexOf, get first, get last, offer，剩余容量，扩展容量，dequeue last, dequeue first, enqueue/add element, dequeue/remove element, subQueueCopy, subArrayCopy, toArray, snapshot，基本的大小，remove或contains。

EjectingQueue

EjectingIntQueue

Answer 8

如果你不想为此导入一些库，你可以使用Deque作为队列，并在它周围包装RingBuffer逻辑:

import java.util.ArrayDeque;
import java.util.Deque;
public class RingBuffer<E> {
   private final Deque<E> queue;
   private final int size;
   public RingBuffer(final int size) {
       queue = new ArrayDeque<>(size);
       this.size = size;
   }
   public void add(final E e) {
       if (queue.size() == size) {
           queue.poll();
       }
       queue.add(e);
   }
   public E poll() {
       return queue.poll();
   }
   @Override
   public String toString() {
       return queue.toString();
   }
}

Answer 9

使用队列

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

有五种简单的Queue方法

• element()——检索，但不删除此标题队列。

• offer(E o)—将指定的元素插入到队列中，如果
  可能的。

• peek() -检索，但不删除，这个头

• poll()——检索并删除这个队列的头部，或者

• remove()——检索并删除这个队列的头部。