Java - 环形缓冲区

Question

我有一个流时间序列,我有兴趣保留最后4个元素,这意味着我希望能够弹出第一个,然后添加到最后.哪个Java Collection最适合这个？矢量？

Answer 1

考虑CircularFifoBuffer Apache的Common.Collections.与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()操作都在恒定时间内执行.所有其他操作在线性时间或更差时执行.

但是你也应该考虑它的局限性 - 例如,你不能在这个集合中添加缺少的时间序列,因为它不允许空值.

Answer 2

自Guava 15.0(2013年9月发布)以来,有EvictingQueue:

一种非阻塞队列,在尝试将新元素添加到队列并且已满时,会自动从队列头部驱逐元素.必须使用最大大小配置驱逐队列.每次将元素添加到完整队列时,队列都会自动删除其head元素.这与传统的有界队列不同,传统的有界队列在满时阻止或拒绝新元素.

此类不是线程安全的,并且不接受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并且似乎比a更快,更高效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)插入和移除
• O(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);

所有这些方法都在O(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

使用队列

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

队列有五种简单的方法

• element()——检索但不删除该队列的头部。

• Offer(E o) -- 如果可能，将指定元素插入此队列
  。

• peek() —— 检索但不删除此队列的头部，如果此队列为空，则返回 null。

• poll() —— 检索并删除此队列的头部，如果此队列为空，则返回 null。

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