Есть ли эквивалент Guava для Apache Commons CircularFifoBuffer?

Мне нужна структура данных, которая может эффективно буферизовать определенное количество элементов в порядке FIFO.

Как упоминалось в этом вопросе, Apache Commons имеет CircularFifoBuffer, но, к сожалению, он не сгенерирован. Некоторые форки существуют, но я не уверен в их статусе обслуживания.

Поскольку Guava — это библиотека для нужд моей коллекции, мне интересно: есть ли хорошая альтернатива в Guava? Если нет, должен ли я реализовать его в своем проекте на основе CircularFifoBuffer Apache Commons?


person Etienne Neveu    schedule 09.01.2013    source источник
comment
Что нужно от круглой части? Бесконечная итерация?   -  person fge    schedule 09.01.2013
comment
Круговая часть относится к общей реализации, которая представляет собой массив с двумя индексами на начало и конец буфера. Когда массив заполнен, структура данных снова начинает запись в начале массива, циклически перезаписывая самые старые элементы. Крутая вещь в этой реализации заключается в том, что вам не нужно создавать ненужные записи, как в LinkedList, что сокращает сборку мусора. Поскольку мне не нужно удалять элементы в середине буфера, это кажется идеальным вариантом.   -  person Etienne Neveu    schedule 09.01.2013
comment
Да, извините, я пошел и прочитал javadoc только после того, как опубликовал первый комментарий;) Похоже, у Guava нет коллекций ограниченного размера, поэтому вы, вероятно, обречены на реализацию этого самостоятельно:/   -  person fge    schedule 09.01.2013
comment
Является ли обязательной функция, чтобы при заполнении самая старая запись перезаписывалась? Если это так, я удалю свой ответ, так как ArrayBlockingQueue заблокируется при заполнении.   -  person SimonC    schedule 09.01.2013
comment
Ну, у меня есть два варианта использования. 1) Я хочу хранить скользящий буфер последних N событий, обработанных нашим приложением, и регистрировать эти события при возникновении исключения. В идеале буфер должен автоматически перезаписывать самое старое событие, а не делать это вручную. 2) У меня есть преобразование, которое буферизует последние 10 событий. Когда буфер заполнен, я хочу обработать самое старое событие и удалить его из буфера. Таким образом, удаление в этом случае выполняется вручную.   -  person Etienne Neveu    schedule 09.01.2013


Ответы (4)


Начиная с Guava 15.0 — вы можете использовать Исключение очереди

person MosheElisha    schedule 06.05.2013

Я не вижу ничего подобного в Guava, но как насчет ForwardingQueue построен на основе ArrayDeque где вы проверяете емкость add(), offer() и т. д. и remove() старых записей, если она уже заполнена?

person Frank Pavageau    schedule 09.01.2013
comment
Мне очень нравится это решение, потому что поведение ArrayDeque на самом деле очень близко к поведению CircularFifoBuffer, как только вы декорируете его, чтобы удалить самый старый элемент, когда он заполнен. У класса нет блокировки/синхронизации, что хорошо, так как потокобезопасность меня не волнует. Единственный недостаток, который я вижу, заключается в том, что базовый массив может быть больше, чем необходимо, поскольку его размер должен быть степенью 2. Но это преждевременная оптимизация :) - person Etienne Neveu; 09.01.2013

Commons-Collections with Generics (maven link) — это то, что вам нужно, если вы хотите использовать коллекции Apache с дженериками (и он содержит рабочий класс CircularFifoBuffer<E>).

С другой стороны, как говорит @FrankPavageau, вы можете использовать свою собственную реализацию ForwardingQueue. Наивный подход (с местом для дальнейшей оптимизации) будет примерно таким:

static class BoundedQueue<E> extends ForwardingQueue<E> {

  private final Queue<E> delegate;
  private final int capacity;

  public BoundedQueue(final int capacity) {
    this.delegate = 
        new ArrayDeque<E>(capacity); // specifying initial capacity is optional
    this.capacity = capacity;
  }

  @Override
  protected Queue<E> delegate() {
    return delegate;
  }

  @Override
  public boolean add(final E element) {
    if (size() >= capacity) {
      delegate.poll();
    }
    return delegate.add(element);
  }

  @Override
  public boolean addAll(final Collection<? extends E> collection) {
    return standardAddAll(collection);
  }

  @Override
  public boolean offer(final E o) {
    return standardOffer(o);
  }

}

Применение:

final BoundedQueue<Integer> boundedQueue = new BoundedQueue<Integer>(3);
boundedQueue.add(1);
System.out.println(boundedQueue); // [1]
boundedQueue.add(2);
System.out.println(boundedQueue); // [1, 2]
boundedQueue.add(3);
System.out.println(boundedQueue); // [1, 2, 3]
boundedQueue.add(4);
System.out.println(boundedQueue); // [2, 3, 4]
boundedQueue.addAll(Arrays.asList(5, 6, 7, 8));
System.out.println(boundedQueue); // [6, 7, 8]
((Queue<Integer>) boundedQueue).offer(9);
System.out.println(boundedQueue); // [7, 8, 9]
person Xaerxess    schedule 09.01.2013
comment
Ага. Я собираюсь использовать CircularFifoBuffer для решения моей текущей проблемы. Я изменил свою зависимость с commons-collections:commons-collections:3.2 на net.sourceforge.collections:collections-generic:4.01 после некоторого поиска (документации не так много). Я надеюсь, что скоро будет выпущена официальная обобщенная версия общих коллекций. За исключением этого, было бы здорово, если бы такую ​​структуру данных можно было добавить в Guava. - person Etienne Neveu; 09.01.2013
comment
Запрос на аналогичную функцию отправлен как проблема № 336. Поставьте звездочку и/или прокомментируйте, будет ли это реализовано. - person Xaerxess; 09.01.2013
comment
Guava только что открыл исходный код EvictingQueue: code.google.com/p/ guava-libraries/source/ Похоже на то, что мне нужно :) - person Etienne Neveu; 12.02.2013
comment
Красиво, но не раньше 15.0... К тому же, они придумали имя получше моего ;) - person Xaerxess; 12.02.2013

Java ArrayBlockingQueue предлагает циркуляр фиксированного размера. буфер.

person SimonC    schedule 09.01.2013
comment
enevu упоминает в комментарии, что когда массив заполнен, структура данных снова начинает запись в начале массива, перезаписывая самые старые элементы. ArrayBlockingQueue этим не занимается. Тем не менее, это не должно быть слишком сложно изменить его. - person Tom Anderson; 09.01.2013
comment
ArrayBlockingQueue довольно близок к тому, что я хочу, но мне не нужна синхронизация. Я думаю, что предпочитаю ArrayDeque. Но это определенно хороший выбор в параллельной среде. Тот факт, что он блокируется при заполнении, не так уж и проблематичен, поскольку на самом деле его довольно легко украсить, чтобы удалить самые старые элементы при заполнении. - person Etienne Neveu; 09.01.2013
comment
Этот ответ неверный. При добавлении элемента сверх установленного лимита ArrayBlockingQueue блокирует (отсюда и название), тогда как CircularFifoQueue удаляет самый старый элемент. Процитируем документ ArrayBlockingQueue: Attempts to put an element into a full queue will result in the operation blocking - person Basil Bourque; 11.02.2014
comment
@BasilBourque, почему этот ответ неверен? Вопрос заключался в том, есть ли в Гуаве хорошая альтернатива? А не альтернатива, функционально идентичная во всех отношениях. Кроме того, в ОП прямо над вашим комментарием указано, что блокировка при заполнении не так уж и проблематична. Пожалуйста, прочитайте другие комментарии перед публикацией. - person SimonC; 11.02.2014