Кольцевой буфер на Java

Ответ 1

Рассмотрим CircularFifoBuffer из Apache Common.Collections. В отличие от очереди, вам не нужно поддерживать ограниченный размер базовой коллекции и переносить ее, как только вы достигнете предела.

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() выполняются в постоянное время. Все остальные операции выполняются за линейное время или хуже.

Однако вы должны учитывать и его ограничения - например, вы не можете добавить отсутствующие временные ряды в эту коллекцию, потому что она не допускает нулевые значения.

ПРИМЕЧАНИЕ. При использовании текущих общих коллекций (4. *) необходимо использовать очередь. Как это:

Queue buf = new CircularFifoQueue(4);

Ответ 2

Так как Guava 15.0 (выпущен в сентябре 2013 года), 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]

Ответ 3

Начиная с Java 1.6 существует ArrayDeque, который реализует Queue и, кажется, быстрее и эффективнее памяти, чем LinkedList и не имеет служебных данных синхронизации потоков ArrayBlockingQueue: из API docs: "Этот класс, вероятно, будет быстрее, чем Stack при использовании в качестве стека, и быстрее, чем LinkedList при использовании в качестве очереди".

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

Ответ 4

Если вам нужно

• O (1) вставка и удаление
• O (1) индексирование на внутренние элементы
• доступ только из одного потока
• тип универсального элемента

то вы можете использовать этот CircularArrayList для 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).

Ответ 5

У меня была такая же проблема некоторое время назад, и я был разочарован, потому что не мог найти решение, которое удовлетворяет мои потребности, поэтому я написал свой собственный класс. Честно говоря, я нашел код тогда, но даже это было не то, что я искал, поэтому я адаптировал его, и теперь я делюсь им, как и автор этого фрагмента кода.

EDIT: это оригинальный (хотя и немного другой) код: CircularArrayList для 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 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);
}
}

Ответ 6

Очень интересный проект - разрушитель. Он имеет кольцевой буфер и используется из того, что я знаю в финансовых приложениях.

Смотрите здесь: код звонка

Я проверил Guava EvictingQueue и ArrayDeque.

ArrayDeque не ограничивает рост, если он заполнен, он удваивает размер и, следовательно, не точно действует как кольцевой буфер.

EvictingQueue делает то, что обещает, но внутренне использует Deque для хранения вещей и просто ограничивает память.

Следовательно, если вы заботитесь об ограничении памяти, ArrayDeque не выполняет ваше обещание. Если вы заботитесь о количестве объектов, 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 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++];
    }
  }
}

Ответ 7

Ни один из приведенных ранее примеров полностью не отвечал моим потребностям, поэтому я написал свою собственную очередь, которая обеспечивает следующие функциональные возможности: итерация, доступ к индексу, indexOf, lastIndexOf, получение первого, получение последнего, предложение, оставшаяся емкость, расширение емкости, удаление последней, удаление очереди во-первых, поставить в очередь/добавить элемент, удалить/удалить элемент, subQueueCopy, subArrayCopy, toArray, снимок, основы, такие как размер, удалить или содержит.

EjectingQueue

EjectingIntQueue

Ответ 8

Используйте 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

Существует пять простых методов Queue

• element() - извлекает, но не удаляет, голова этого очередь.

• offer (E o) - Вставляет указанный элемент в эту очередь, если возможно.

• peek() - извлекает, но не удаляет, голова этого queue, возвращая null, если эта очередь пуста.

• poll() - извлекает и удаляет головку этой очереди или null, если эта очередь пуста.

• remove() - извлекает и удаляет головку этой очереди.