Ring Buffer in Java

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

Какая коллекция Java лучше всего подходит для этого? Vector?

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

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 . Вот так:

Queue buf = new CircularFifoQueue(4);

Начиная с 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]

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

• 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).

Начиная с 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