Перейти к основному содержимому

Введение в Spliterator в Java

· 7 мин. чтения

Задача: Наибольшая подстрока палиндром

Для заданной строки s, верните наибольшую подстроку палиндром входящую в s. Подстрока — это непрерывная непустая последовательность символов внутри строки. Стока является палиндромом, если она читается одинаково в обоих направлениях...

ANDROMEDA 42

1. Обзор

Интерфейс Spliterator , представленный в Java 8, можно использовать для обхода и разделения последовательностей . Это базовая утилита для потоков , особенно параллельных.

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

2. API -разделитель

2.1. попробуй вперед

Это основной метод, используемый для пошагового прохождения последовательности. Метод принимает Consumer , который используется для последовательного использования элементов Spliterator , и возвращает false , если нет элементов для обхода.

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

Во-первых, давайте предположим, что у нас есть список ArrayList с 35 000 статей и класс Article определен как:

public class Article {
private List<Author> listOfAuthors;
private int id;
private String name;

// standard constructors/getters/setters
}

Теперь давайте реализуем задачу, которая обрабатывает список статей и добавляет к названию каждой статьи суффикс « -published by ForEach» :

public String call() {
int current = 0;
while (spliterator.tryAdvance(a -> a.setName(article.getName()
.concat("- published by ForEach")))) {
current++;
}

return Thread.currentThread().getName() + ":" + current;
}

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

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

2.2. попробоватьСплит

Далее давайте разобьем сплитеры (отсюда и название) и обработаем разделы независимо друг от друга.

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

Давайте сначала сгенерируем наш список:

public static List<Article> generateElements() {
return Stream.generate(() -> new Article("Java"))
.limit(35000)
.collect(Collectors.toList());
}

Затем мы получаем наш экземпляр Spliterator , используя метод spliterator() . Затем мы применяем наш метод trySplit() :

@Test
public void givenSpliterator_whenAppliedToAListOfArticle_thenSplittedInHalf() {
Spliterator<Article> split1 = Executor.generateElements().spliterator();
Spliterator<Article> split2 = split1.trySplit();

assertThat(new Task(split1).call())
.containsSequence(Executor.generateElements().size() / 2 + "");
assertThat(new Task(split2).call())
.containsSequence(Executor.generateElements().size() / 2 + "");
}

Процесс разделения работал, как и предполагалось, и разделил записи поровну .

2.3. расчетный размер

Метод предполагаемого размера дает нам приблизительное количество элементов:

LOG.info("Size: " + split1.estimateSize());

Это выведет:

Size: 17500

2.4. имеетХарактеристики

Этот API проверяет, соответствуют ли заданные характеристики свойствам Spliterator. Затем, если мы вызовем описанный выше метод, результатом будет представление этих характеристик в виде int :

LOG.info("Characteristics: " + split1.characteristics());
Characteristics: 16464

3. Характеристики сплиттеров

Он имеет восемь различных характеристик, описывающих его поведение. Их можно использовать как подсказки для внешних инструментов:

  • SIZED если он может возвращать точное количество элементов с помощью метода AssessmentSize() .
  • SORTED — если он перебирает отсортированный источник
  • SUBSIZED — если мы разделим экземпляр с помощью метода trySplit() и получим Spliterators, которые также имеют SIZED
  • CONCURRENT — если исходный код может быть безопасно изменен одновременно
  • DISTINCT — если для каждой пары встречающихся элементов x, y, !x.equals(y)
  • IMMUTABLE — если элементы, хранящиеся в источнике, не могут быть структурно изменены
  • NONNULL — если источник содержит нули или нет
  • ORDERED - при повторении упорядоченной последовательности

4. Пользовательский сплитератор

4.1. Когда настраивать

Во-первых, давайте предположим следующий сценарий:

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

Наш класс Author будет выглядеть следующим образом:

public class Author {
private String name;
private int relatedArticleId;

// standard getters, setters & constructors
}

Далее мы реализуем класс для подсчета авторов при обходе потока авторов. Затем класс выполнит сокращение потока.

Давайте посмотрим на реализацию класса:

public class RelatedAuthorCounter {
private int counter;
private boolean isRelated;

// standard constructors/getters

public RelatedAuthorCounter accumulate(Author author) {
if (author.getRelatedArticleId() == 0) {
return isRelated ? this : new RelatedAuthorCounter( counter, true);
} else {
return isRelated ? new RelatedAuthorCounter(counter + 1, false) : this;
}
}

public RelatedAuthorCounter combine(RelatedAuthorCounter RelatedAuthorCounter) {
return new RelatedAuthorCounter(
counter + RelatedAuthorCounter.counter,
RelatedAuthorCounter.isRelated);
}
}

Каждый метод в приведенном выше классе выполняет определенную операцию для подсчета при обходе.

Во-первых, метод calculate() итеративно проходит по авторам один за другим , а затем comb() суммирует два счетчика, используя их значения . Наконец, getCounter() возвращает счетчик.

Теперь, чтобы проверить, что мы сделали до сих пор. Преобразуем список авторов нашей статьи в поток авторов:

Stream<Author> stream = article.getListOfAuthors().stream();

И реализуйте метод countAuthor() для выполнения сокращения потока с помощью RelatedAuthorCounter :

private int countAutors(Stream<Author> stream) {
RelatedAuthorCounter wordCounter = stream.reduce(
new RelatedAuthorCounter(0, true),
RelatedAuthorCounter::accumulate,
RelatedAuthorCounter::combine);
return wordCounter.getCounter();
}

Если бы мы использовали последовательный поток, вывод будет, как и ожидалось, «count = 9» , однако проблема возникает, когда мы пытаемся распараллелить операцию.

Давайте рассмотрим следующий тестовый пример:

@Test
void
givenAStreamOfAuthors_whenProcessedInParallel_countProducesWrongOutput() {
assertThat(Executor.countAutors(stream.parallel())).isGreaterThan(9);
}

Видимо, что-то пошло не так — разбиение потока в случайном месте приводило к двойному учету автора.

4.2. Как настроить

Чтобы решить эту проблему, нам нужно реализовать Spliterator , который разделяет авторов только тогда, когда соответствующие идентификаторы и articleId совпадают . Вот реализация нашего пользовательского Spliterator :

public class RelatedAuthorSpliterator implements Spliterator<Author> {
private final List<Author> list;
AtomicInteger current = new AtomicInteger();
// standard constructor/getters

@Override
public boolean tryAdvance(Consumer<? super Author> action) {
action.accept(list.get(current.getAndIncrement()));
return current.get() < list.size();
}

@Override
public Spliterator<Author> trySplit() {
int currentSize = list.size() - current.get();
if (currentSize < 10) {
return null;
}
for (int splitPos = currentSize / 2 + current.intValue();
splitPos < list.size(); splitPos++) {
if (list.get(splitPos).getRelatedArticleId() == 0) {
Spliterator<Author> spliterator
= new RelatedAuthorSpliterator(
list.subList(current.get(), splitPos));
current.set(splitPos);
return spliterator;
}
}
return null;
}

@Override
public long estimateSize() {
return list.size() - current.get();
}

@Override
public int characteristics() {
return CONCURRENT;
}
}

Теперь применение метода countAuthors() даст правильный результат. Следующий код демонстрирует, что:

@Test
public void
givenAStreamOfAuthors_whenProcessedInParallel_countProducesRightOutput() {
Stream<Author> stream2 = StreamSupport.stream(spliterator, true);

assertThat(Executor.countAutors(stream2.parallel())).isEqualTo(9);
}

Кроме того, пользовательский Spliterator создается из списка авторов и проходит через него, удерживая текущую позицию.

Остановимся подробнее на реализации каждого метода:

  • tryAdvance — передает авторов Потребителю в текущей позиции индекса и увеличивает свою позицию
  • trySplit — определяет механизм разделения, в нашем случае RelatedAuthorSpliterator создается при совпадении id, и разделение делит список на две части
  • предполагаемый размер — разница между размером списка и позицией текущего итерируемого автора
  • характеристики — возвращает характеристики Spliterator , в нашем случае SIZED , так как значение, возвращаемое методом оцениваемого размера() , является точным; кроме того, CONCURRENT указывает, что источник этого Spliterator может быть безопасно изменен другими потоками.

5. Поддержка примитивных значений

API Spliterator поддерживает примитивные значения , включая double , int и long .

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

Например, когда нам это нужно для значения int , нам нужно передать intConsumer . Кроме того, вот список примитивных выделенных разветвителей :

  • OfPrimitive<T, T_CONS, T_SPLITR расширяет Spliterator.OfPrimitive<T, T_CONS, T_SPLITR>> : родительский интерфейс для других примитивов
  • OfInt : сплитератор, специализирующийся на int .
  • OfDouble : сплитератор, предназначенный для двойного
  • OfLong : сплитератор, предназначенный для длинных

6. Заключение

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

Как всегда, полную реализацию этой статьи можно найти на Github .