Руководство по Guava MinMaxPriorityQueue и EvictingQueue

1 . Обзор

В этой статье мы рассмотрим конструкции EvictingQueue и MinMaxPriorityQueue из библиотеки Guava. EvictingQueue — это реализация концепции циклического буфера . MinMaxPriorityQueue дает нам доступ к наименьшему и наибольшему элементу с помощью предоставленного компаратора.

2. Выселение из очереди

Начнем с построения — при построении экземпляра очереди нам нужно указать максимальный размер очереди в качестве аргумента.

Когда мы хотим добавить новый элемент в EvictingQueue , а очередь заполнена, он автоматически вытесняет элемент из своего заголовка .

По сравнению со стандартным поведением очереди добавление элемента в полную очередь не блокирует, а удаляет головной элемент и добавляет новый элемент в хвост.

Мы можем представить EvictingQueue как кольцо, в которое мы вставляем элементы только для добавления. Если есть элемент в позиции, в которую мы хотим добавить новый элемент, мы просто переопределяем существующий элемент в данной позиции.

Давайте создадим экземпляр EvictingQueue с максимальным размером 10. Далее мы добавим к нему 10 элементов:

Queue<Integer> evictingQueue = EvictingQueue.create(10);

IntStream.range(0, 10)
  .forEach(evictingQueue::add);

assertThat(evictingQueue)
  .containsExactly(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);

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

Это не относится к реализации EvictingQueue . Добавление к нему нового элемента приведет к тому, что у него будет удалена голова, а новый элемент будет добавлен к хвосту:

evictingQueue.add(100);

assertThat(evictingQueue)
  .containsExactly(1, 2, 3, 4, 5, 6, 7, 8, 9, 100);

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

3. Минимальная очередь приоритетов

MinMaxPriorityQueue обеспечивает постоянный доступ к своим наименьшим и наибольшим элементам.

Чтобы получить наименьший элемент, нам нужно вызвать метод peekFirst() . Чтобы получить наибольший элемент, мы можем вызвать метод peekLast() . Обратите внимание, что они не удаляют элементы из очереди, а только извлекают их.

Упорядочивание элементов осуществляется компаратором , который необходимо передать конструктору этой очереди.

Допустим, у нас есть класс CustomClass , в котором есть поле значения целочисленного типа :

class CustomClass {
    private Integer value;

    // standard constructor, getters and setters
}

Давайте создадим MinMaxPriorityQueue , которая будет использовать компаратор для типов int . Далее добавим в очередь 10 объектов типа CustomClass :

MinMaxPriorityQueue<CustomClass> queue = MinMaxPriorityQueue
  .orderedBy(Comparator.comparing(CustomClass::getValue))
  .maximumSize(10)
  .create();

IntStream
  .iterate(10, i -> i - 1)
  .limit(10)
  .forEach(i -> queue.add(new CustomClass(i)));

Из-за характеристик MinMaxPriorityQueue и переданного Компаратора элемент в начале очереди будет равен 1, а элемент в хвосте очереди будет равен 10:

assertThat(
  queue.peekFirst().getValue()).isEqualTo(1);
assertThat(
  queue.peekLast().getValue()).isEqualTo(10);

Поскольку вместимость нашей очереди равна 10, и мы добавили 10 элементов, очередь заполнена. Добавление к нему нового элемента приведет к удалению последнего элемента в очереди. Добавим CustomClass со значением , равным -1:

queue.add(new CustomClass(-1));

После этого действия последний элемент в очереди будет удален, а новый элемент в хвосте будет равен 9. Новый заголовок будет равен -1, так как это новый наименьший элемент в соответствии с компаратором , который мы передали, когда построил нашу очередь:

assertThat(
  queue.peekFirst().getValue()).isEqualTo(-1);
assertThat(
  queue.peekLast().getValue()).isEqualTo(9);

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

Давайте добавим число 100 и проверим, находится ли этот элемент в очереди после этой операции:

queue.add(new CustomClass(100));
assertThat(queue.peekFirst().getValue())
  .isEqualTo(-1);
assertThat(queue.peekLast().getValue())
  .isEqualTo(9);

Как мы видим, первый элемент в очереди по-прежнему равен -1, а последний равен 9. Поэтому добавление целого числа было проигнорировано, так как оно больше уже самого большого элемента в очереди.

4. Вывод

В этой статье мы рассмотрели конструкцию EvictingQueue и MinMaxPriorityQueue из библиотеки Guava.

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

Мы использовали MinMaxPriorityQueue в сочетании с компаратором , чтобы иметь постоянный доступ к его наименьшему и наибольшему элементу.

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

Реализацию всех этих примеров и фрагментов кода можно найти в проекте GitHub — это проект Maven, поэтому его должно быть легко импортировать и запускать как есть.