Ограниченная по размеру очередь, которая содержит последние N элементов в Java

198

Очень простой и быстрый вопрос о библиотеках Java: есть ли готовый класс, который реализует Queueс фиксированным максимальным размером - то есть он всегда позволяет добавлять элементы, но он будет молча удалять элементы заголовка, чтобы освободить место для вновь добавленных элементов.

Конечно, реализовать это вручную тривиально:

import java.util.LinkedList;

public class LimitedQueue<E> extends LinkedList<E> {
    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        super.add(o);
        while (size() > limit) { super.remove(); }
        return true;
    }
}

Насколько я вижу, в Java stdlibs нет стандартной реализации, но может быть, есть такая в Apache Commons или что-то в этом роде?

GreyCat
источник
1
Связанный stackoverflow.com/questions/590069/…
andersoj
9
@ Кевин: Ты такой дразнить.
Марк Питерс
5
Персонально Я бы не представил другую библиотеку, если бы это было единственное использование этой библиотеки ...
Николас Буске
2
@Override public boolean add (PropagationTask t) {boolean добавлен = super.add (t); while (добавлено && size ()> limit) {super.remove (); } возвращение добавлено; }
Renaud
6
Предупреждение: рассматриваемый код, хотя, по-видимому, работает, может привести к обратным последствиям. Существуют дополнительные методы, которые могут добавлять больше элементов в очередь (например, addAll ()), которые игнорируют эту проверку размера. Для получения более подробной информации см. « Эффективное Java, 2-е издание» - Элемент 16. Композиция Favour по сравнению с наследованием
Диего

Ответы:

171

Apache commons collection 4 имеет CircularFifoQueue <>, который вы ищете. Цитируя Javadoc:

CircularFifoQueue - это очередь «первым пришел - первым вышел» с фиксированным размером, который заменяет самый старый элемент, если он заполнен.

    import java.util.Queue;
    import org.apache.commons.collections4.queue.CircularFifoQueue;

    Queue<Integer> fifo = new CircularFifoQueue<Integer>(2);
    fifo.add(1);
    fifo.add(2);
    fifo.add(3);
    System.out.println(fifo);

    // Observe the result: 
    // [2, 3]

Если вы используете более старую версию коллекций Apache Commons (3.x), вы можете использовать CircularFifoBuffer, который в основном то же самое без дженериков.

Обновление : обновленный ответ после выпуска 4-й коллекции общих фондов, которая поддерживает дженерики.

Асаф
источник
1
Это хороший кандидат, но, увы, он не использует дженерики :(
GreyCat
Спасибо! Похоже, это самая жизнеспособная альтернатива на данный момент :)
GreyCat
3
См. Этот другой ответ для ссылки на EvictingQueueдобавленную в Google Guava версии 15 около 2013-10.
Базилик Бурк
Существует ли какой-либо обратный вызов, когда элемент исключается из очереди из-за добавления в полную очередь?
ed22
«Круговая очередь» - это всего лишь одна реализация, которая удовлетворяет этому вопросу. Но этот вопрос напрямую не выигрывает от основных отличий кольцевой очереди, то есть от необходимости освобождения / перераспределения каждого сегмента при каждом добавлении / удалении.
simpleuser
90

У Guava теперь есть EvictingQueue , неблокирующая очередь, которая автоматически выталкивает элементы из головы очереди при попытке добавить новые элементы в очередь, и она заполнена.

import java.util.Queue;
import com.google.common.collect.EvictingQueue;

Queue<Integer> fifo = EvictingQueue.create(2); 
fifo.add(1); 
fifo.add(2); 
fifo.add(3); 
System.out.println(fifo); 

// Observe the result: 
// [2, 3]
Miguel
источник
Это должно быть интересно использовать, как только оно выйдет официально.
Асаф
Вот источник: code.google.com/p/guava-libraries/source/browse/guava/src/com/… - похоже, что было бы легко скопировать и скомпилировать с текущими выпусками Guava
Том Carchrae
1
Обновление: этот класс был официально выпущен с Google Guava в версии 15 , около 2013-10.
Базилик Бурк
1
@MaciejMiklas Вопрос о ФИФО, ФИФО EvictingQueue. Если есть какие-либо сомнения, попробуйте эту программу: Queue<Integer> fifo = EvictingQueue.create(2); fifo.add(1); fifo.add(2); fifo.add(3); System.out.println(fifo); Обратите внимание на результат:[2, 3]
kostmo
2
Теперь это правильный ответ. Это немного неясно из документации, но EvictingQueue - это FIFO.
Майкл Бёклинг
11

Мне нравится решение @FractalizeR. Но я бы дополнительно сохранил и вернул значение из super.add (o)!

public class LimitedQueue<E> extends LinkedList<E> {

    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
           super.remove();
        }
        return added;
    }
}
Renaud
источник
1
Насколько я вижу, FractalizeR не предоставил никакого решения, только отредактировал вопрос. «Решение» в вопросе не является решением, потому что речь шла об использовании некоторого класса в стандартной или полустандартной библиотеке, а не обкатывании собственного.
GreyCat
3
Следует отметить, что это решение не является потокобезопасным
Конрад Моравский
7
@KonradMorawski весь класс LinkedList не является потокобезопасным в любом случае, поэтому ваш комментарий в этом контексте не имеет смысла!
Рено
@RenaudBlue поток безопасности является действительной проблемой (если часто упускается из виду), поэтому я не думаю, что комментарий является бессмысленным. и напоминание о том, что LinkedListэто не потокобезопасно, также не будет бессмысленным. в контексте этого вопроса особое требование OP делает особенно важным, чтобы добавление элемента выполнялось как элементарная операция. другими словами, риск не обеспечения атомарности был бы больше, чем в случае обычного LinkedList.
Конрад Моравский
4
Перерывы, как только кто-то звонит add(int,E). И addAllработает ли как задумано, зависит от неуказанных деталей реализации. Вот почему вы должны отдавать предпочтение делегированию, а не наследованию…
Хольгер
6

Использовать композицию не расширяет (да, я имею в виду расширяет, как в ссылке на ключевое слово extends в Java, и да, это наследование). Композиция выше, потому что она полностью защищает вашу реализацию, позволяя вам изменять реализацию, не влияя на пользователей вашего класса.

Я рекомендую попробовать что-то вроде этого (я печатаю прямо в этом окне, поэтому покупатель остерегается синтаксических ошибок):

public LimitedSizeQueue implements Queue
{
  private int maxSize;
  private LinkedList storageArea;

  public LimitedSizeQueue(final int maxSize)
  {
    this.maxSize = maxSize;
    storageArea = new LinkedList();
  }

  public boolean offer(ElementType element)
  {
    if (storageArea.size() < maxSize)
    {
      storageArea.addFirst(element);
    }
    else
    {
      ... remove last element;
      storageArea.addFirst(element);
    }
  }

  ... the rest of this class

Лучшим вариантом (основанным на ответе Асафа) может быть обертывание коллекций Apache CircularFifoBuffer с универсальным классом. Например:

public LimitedSizeQueue<ElementType> implements Queue<ElementType>
{
    private int maxSize;
    private CircularFifoBuffer storageArea;

    public LimitedSizeQueue(final int maxSize)
    {
        if (maxSize > 0)
        {
            this.maxSize = maxSize;
            storateArea = new CircularFifoBuffer(maxSize);
        }
        else
        {
            throw new IllegalArgumentException("blah blah blah");
        }
    }

    ... implement the Queue interface using the CircularFifoBuffer class
}
DWB
источник
2
+1, если вы объясните, почему композиция является лучшим выбором (кроме «предпочитаю композицию наследованию) ... и есть очень веская причина
kdgregory
1
Композиция - плохой выбор для моей задачи: она означает как минимум вдвое больше объектов => как минимум вдвое чаще сборщик мусора. Я использую большое количество (десятки миллионов) этих очередей ограниченного размера, например: Map <Long, LimitedSizeQueue <String >>.
GreyCat
@GreyCat - я так понимаю, вы еще не посмотрели, как LinkedListэто реализовано. Дополнительный объект, созданный как обертка вокруг списка, будет довольно незначительным, даже с «десятками миллионов» экземпляров.
kdgregory
Я собирался «уменьшить размер интерфейса», но «защищает реализацию» - это почти то же самое. Либо отвечает на жалобы Марка Питера на подход ОП.
kdgregory
4

Единственное, что я знаю, что имеет ограниченное пространство - это интерфейс BlockingQueue (который, например, реализуется классом ArrayBlockingQueue) - но они не удаляют первый элемент, если он заполнен, а вместо этого блокируют операцию put до тех пор, пока пространство не освободится (удаляется другим потоком ).

Насколько мне известно, ваша тривиальная реализация - самый простой способ получить такое поведение.

flolo
источник
Я уже просмотрел классы Java stdlib, и, к сожалению, BlockingQueueэто не ответ. Я думал о других распространенных библиотеках, таких как Apache Commons, библиотеки Eclipse, Spring, Google и т.д.?
GreyCat
3

Вы можете использовать MinMaxPriorityQueue из Google Guava , из javadoc:

Минимальная-приоритетная очередь может быть настроена с максимальным размером. Если так, то каждый раз, когда размер очереди превышает это значение, очередь автоматически удаляет свой наибольший элемент в соответствии со своим компаратором (который может быть элементом, который был только что добавлен). Это отличается от обычных ограниченных очередей, которые блокируют или отклоняют новые элементы при заполнении.

Moritz
источник
3
Понимаете ли вы, что такое приоритетная очередь и чем она отличается от примера ОП?
kdgregory
2
@ Марк Питерс - я просто не знаю, что сказать. Конечно, вы можете сделать приоритетную очередь похожей на очередь fifo. Вы также можете заставить Mapсебя вести себя как List. Но обе идеи показывают полное непонимание алгоритмов и дизайна программного обеспечения.
kdgregory
2
@ Марк Питерс - разве не каждый вопрос на SO о хорошем способе сделать что-то?
jtahlborn
3
@jtahlborn: Ясно, что нет (код гольф), но даже если бы они были, хорошо, это не черно-белый критерий. Для определенного проекта good может означать «наиболее эффективный», для другого - «проще поддерживать», а для другого - «наименьшее количество кода в существующих библиотеках». Все , что не имеет никакого значения , так как я никогда не говорил , что это был хороший ответ. Я только что сказал, что это может быть решение без особых усилий. Превращение MinMaxPriorityQueueв то, что хочет ОП, более тривиально, чем изменение LinkedList(код ОП даже близко не подходит).
Марк Питерс
3
Может быть, вы, ребята, изучаете мой выбор слов «на практике этого почти наверняка будет достаточно». Я не имел в виду, что этого решения почти наверняка будет достаточно для проблемы ОП или вообще. Я имел в виду выбор нисходящего longв качестве типа курсора в моем собственном предложении, говоря, что на практике он будет достаточно широким, хотя теоретически вы можете добавить более 2 ^ 64 объектов в эту очередь, и в этот момент решение будет нарушено. ,
Марк Питерс
-2
    public class ArrayLimitedQueue<E> extends ArrayDeque<E> {

    private int limit;

    public ArrayLimitedQueue(int limit) {
        super(limit + 1);
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
            super.remove();
        }
        return added;
    }

    @Override
    public void addLast(E e) {
        super.addLast(e);
        while (size() > limit) {
            super.removeLast();
        }
    }

    @Override
    public boolean offerLast(E e) {
        boolean added = super.offerLast(e);
        while (added && size() > limit) {
            super.pollLast();
        }
        return added;
    }
}
user590444
источник
3
Речь шла о классах в популярных библиотеках классов коллекций, а не о том, что нужно делать самостоятельно - минималистичное доморощенное «решение» уже было под вопросом.
GreyCat
2
это не имеет значения, Google найти эту страницу также по другим запросам =)
user590444
1
Этот ответ появился в очереди проверки низкого качества, возможно потому, что вы не предоставили никакого объяснения кода. Если этот код отвечает на вопрос, подумайте над добавлением текста, объясняющего код в вашем ответе. Таким образом, у вас гораздо больше шансов получить больше голосов и помочь спрашивающему узнать что-то новое.
ИМО