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

«1. Обзор

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

2. EvictingQueue

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

Когда мы хотим добавить новый элемент в 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

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, поэтому его должно быть легко импортировать и запускать как есть.