Что не так в Java 8, часть VII: снова потоки

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

Проблема с доступом к включенной области видимости состоит в том, что цикл нигде не может быть повторно использован. Функциональное программирование приносит решение:

Функциональный эквивалент для этого кода:

IntStream.range(0, 10).forEach(System.out::println);

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

Конструкции for eachJava также имеют очень простой функциональный эквивалент. Этот итерационный пример:

//
//
List<Integer> integerList = Arrays.asList(1, 2, 3, 4, 5);
List<String> stringList = new ArrayList<>();
for (Integer value : integerList) {
  stringList.add(“Value = “ + value);
}

может быть заменено на:

//
//
List<Integer> integerList = Arrays.asList(1, 2, 3, 4, 5);
integerList.map(x -> "Value = " + x);

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

Есть, конечно, много других форм циклов, например:

//
//
for (int i = 1; i < limit; i += 2) {
  ...
}

Этот цикл будет перебирать все нечетные числа в limit. И следующее — потенциально бесконечный цикл по четным числам:

for (int i = 0;; i += 2) {
  ...
}

Потоки могут использоваться для замены некоторых из этих конструкций, что делает код намного чище. К сожалению, в Java 8 отсутствуют две очень важные функции для этого вида использования: указание шага и ограничение потока предикатом.

Ограничение потока предикатом

Давайте посмотрим на следующий итерационный пример и посмотрим, как мы можем переписать его, используя функциональную парадигму:

//
//
public static boolean isPrime(final int n) {
  if (n < 2) return true;
  for(int i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      return false;
    }
  }
  return true;
}

Этот (очень неэффективный) код определяет, является ли целое число простым числом.

Этот код может быть переписан с использованием функционального подхода:

//
//
public static IntPredicate isPrime = n -> n < 4 || !(n % 2 == 0 ||
  IntStream.range(2, (int) Math.sqrt(n) + 1)
      .filter(x -> x % 2 != 0 && n % x == 0)
      .count() != 0);

Эта реализация дает тот же результат. Однако он может быть оптимизирован:

//
//
public static IntPredicate isPrime = n -> n < 4 || !(n % 2 == 0 ||
  IntStream.range(2, (int) Math.sqrt(n) + 1)
      .filter(x -> x % 2 != 0 && n % x == 0)
      .findAny()
      .isPresent());

Замена .count()на .findAny().isPresent()позволяет одному и тому же коду запускаться за 663 мс вместо 2 760 мс для нахождения всех простых чисел от 1 до 1 000 000. Это намного лучше, потому что findAny()остановит оценку потока, как только будет найдено значение, так как в отличие от count()которого необходимо оценить общий поток перед возвратом значения. Еще более быстрое решение заключается в использовании anyMatch():

//
//
public static IntPredicate isPrime = n -> n < 4 || !(n % 2 == 0 ||
  IntStream.range(2, (int) Math.sqrt(n) + 1)
      .filter(x -> x % 2 != 0 && n % x == 0)
      .anyMatch(x -> true);

Это примерно на 10% быстрее, но это менее элегантно, поскольку .findAny().isPresent()лучше выразить, что поток содержит хотя бы один элемент.

Обратите внимание, что у нас проблема с тем, как мы ограничиваем поток. В итеративном решении пределом является предикат:

i * i <= n

Во многих функциональных языках мы ограничиваем поток чем-то вроде:

//
//
public static IntPredicate isPrime4 = n -> n < 4 || !(n % 2 == 0 ||
  IntStream.range(2, n)
      .takeWhile(x -> x * x <= n)
      .filter(x -> x % 2 != 0 && n % x == 0)
      .findAny()
      .isPresent());

Но это невозможно в Java 8, потому что IntStreamне имеет takeWhileни эквивалентного метода. Затем мы должны использовать уродливый трюк, используя квадратный корень из n .

Другое решение было бы использовать метод итерации для создания потока:

//
IntStream.iterate(2, x -> x + 1)

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

//
//
IntStream.iterate(2, x -> x + 1).filter(x -> x < 10).forEach(System.out::println);

Это напечатает числа от 1 до 9, затем остановится на некоторое время, затем напечатает:

-2147483648
-2147483647
-2147483646
-2147483645
-2147483644
-2147483643
-2147483642
-2147483641
    ...

Это связано с тем, что поток бесконечен, а значение, полученное функцией, в конечном итоге переполнится и даст отрицательный результат, который будет удовлетворять предикату. Используя следующее условие:

//
//
IntStream.iterate(2, x -> x + 1).filter(x -> x >= 0 && x < 10).forEach(System.out::println);

не решит проблему.

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

Мы действительно пропускаем takeWhileметод здесь. Мы можем смоделировать это с помощью следующего кода:

// This code is extracted from the
// IntStream class and slighty modified
public static IntStream iterate(final int seed, final IntUnaryOperator f, IntPredicate p) { // change here
  Objects.requireNonNull(f);
  final PrimitiveIterator.OfInt iterator = new PrimitiveIterator.OfInt() {
    int t = seed;

    @Override
    public boolean hasNext() {
      return p.test(t); // change here
    }

    @Override
    public int nextInt() {
      int v = t;
      t = f.applyAsInt(t);
      return v;
    }
  };
  return StreamSupport.intStream(Spliterators.spliteratorUnknownSize(
      iterator,
      Spliterator.ORDERED | Spliterator.IMMUTABLE | Spliterator.NONNULL), false);
}

Этот код может быть использован следующим образом:

//
//
public static IntPredicate isPrime = n -> n < 4 || !(n % 2 == 0 ||
  iterate(2, x -> x + 1, x-> x * x <= n)
      .filter(x -> x % 2 != 0 && n % x == 0)
      .findAny()
      .isPresent());

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

Указание шага

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

//
//
public static boolean isPrime(final int n) {
  if (n < 4) return true;
  if (n % 2 == 0) return false;
  for(int i = 3; i * i <= n; i += 2) {
    if(n % i==0) {
      return false;
    }
  }
  return true;
}

Оптимизация заключается в использовании шага 2, поскольку мы хотим проверять только нечетные числа. Это возможно с функциональной идиомой? Мы не можем использовать:

//
IntStream.iterate(2, x -> x + 2)

Так как мы не сможем ограничить поток предикатом, и мы не знаем длину потока, поэтому мы не можем использовать l imit().

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

//
//
public static IntPredicate isPrime = n -> n < 4 || !(n % 2 == 0 ||
  iterate(3, x -> x + 2, x-> x * x <= n)
       .filter(x -> n % x == 0)
       .findAny()
       .isPresent());

Другим решением будет следующее:

//
//
public static IntPredicate isPrime = n -> n < 4 || !(n % 2 == 0 ||
  IntStream.range(1, (int) Math.sqrt(n) / 2 + 1)
      .map(x -> x * 2 + 1)
      .filter(x -> n % x == 0)
      .findAny()
      .isPresent());

Эта версия создает поток с шагом один, а затем отображает его с помощью функции x -> x * 2 + 1.

Мы также можем создать поток с шагом 1, а затем отфильтровать четные значения:

//
//
public static IntPredicate isPrime = n -> n < 4 || !(n % 2 == 0 ||
  IntStream.range(2, (int) Math.sqrt(n) + 1)
      .filter(x -> x % 2 != 0 && n % x == 0)
      .findAny()
      .isPresent());

Или мы могли бы использовать модифицированную (снова) версию RangeIntSpliteratorкласса:

//
//
static final class RangeIntSpliterator implements Spliterator.OfInt {

  private int from;
  private final int upTo;
  private final int step;
  private int last;

  RangeIntSpliterator(int from, int upTo, int step, boolean closed) { // change
    this(from, upTo, step, closed ? 1 : 0); // change
  }

  private RangeIntSpliterator(int from, int upTo, int step, int last) { // change
    this.from = from;
    this.upTo = upTo;
    this.step = Math.max(1, step); // added
    this.last = last;
  }

  @Override
  public boolean tryAdvance(IntConsumer consumer) {
    Objects.requireNonNull(consumer);

    final int i = from;
    if (upTo - i >= step) {
      from += step; // change
      consumer.accept(i);
      return true;
    }
    else if (last > 0) {
      last = 0;
      consumer.accept(i);
      return true;
    }
    return false;
  }

  @Override
  public void forEachRemaining(IntConsumer consumer) {
    Objects.requireNonNull(consumer);

    int i = from;
    final int hUpTo = upTo;
    int hLast = last;
    from = upTo;
    last = 0;
    while (i < hUpTo) {
      consumer.accept(i);
      i += step; // change
    }
    if (hLast > 0) {
      // Last element of closed range
      consumer.accept(i);
    }
  }

  @Override
  public long estimateSize() {
    // Ensure ranges of size > Integer.MAX_VALUE report the correct size
    return (((long) upTo) - from + last) / step;
  }

  @Override
  public int characteristics() {
    return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED |
        Spliterator.IMMUTABLE | Spliterator.NONNULL |
        Spliterator.DISTINCT | Spliterator.SORTED;
  }

  @Override
  public Comparator<? super Integer> getComparator() {
    return null;
  }

  @Override
  public Spliterator.OfInt trySplit() {
    long size = estimateSize();
    return size <= 1
        ? null
        // Left split always has a half-open range
        : new RangeIntSpliterator(from, from = from + splitPoint(size), step, 0);
  }

  private static final int BALANCED_SPLIT_THRESHOLD = 1 << 24;

  private static final int RIGHT_BALANCED_SPLIT_RATIO = 1 << 3;

  private int splitPoint(long size) {
    int d = (size < BALANCED_SPLIT_THRESHOLD) ? 2 : RIGHT_BALANCED_SPLIT_RATIO;
    return (int) (size / d);
  }
}

Этот класс может использоваться со следующим методом (извлеченным из IntStreamкласса и слегка измененным:

//
//
public static IntStream rangeStep(int startInclusive, int endExclusive, int step) { // change
  if (startInclusive >= endExclusive) {
    return IntStream.empty();
  } else {
  return StreamSupport.intStream(
    new RangeIntSpliterator(startInclusive, endExclusive, step, false), false); // change
  }
}

Затем он может быть использован как:

//
//
public static IntPredicate isPrime = n -> n < 4 || !(n % 2 == 0 ||
    rangeStep(3, (int) Math.sqrt(n) + 2, 2)
         .filter(x -> n % x == 0)
         .findAny()
         .isPresent());

эталонный тест

Функциональные версии в любом случае медленнее императивных. Вот производительность каждого решения для нахождения 78 499 простых чисел в диапазоне от 1 до 1 000 000. Все тесты были проведены несколько раз перед измерением времени, чтобы прогреть компилятор. (Это очень важно. Несоблюдение этого требования может дать забавные результаты.)

//
//
Non optimized iterative: 78499 primes in 307 ms.
Optimized iterative: 78499 primes in 160 ms.
Functional with step 1 and mapping with x -> x * 2 + 1: 78499 primes in 763 ms.
Functional with step 2 limited by a predicate: 78499 primes in 746 ms.
Functional idem, tested with anyMatch: 78499 primes in 653 ms.
Functional with step 1 and filtering even values: 78499 primes in 1186 ms.
Functional with iterate, step 2 and limit with a predicate: 78499 primes in 760 ms.

Вывод

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

Преимущество функциональных версий — очень низкая цикломатическая сложность и тот факт, что код показывает, что предназначено, а не как оно реализовано (поскольку реальная реализация скрыта в используемых библиотеках).

Чего не хватает (помимо лучшей производительности) — это способ еще лучше выразить свои намерения. Другими словами, для основного примера мы должны иметь возможность написать:

//
//
public static IntPredicate isPrime = n -> n < 4 || (n % 2 != 0 &&
  IntStream.iterate(3, x -> x + 2, x-> x * x <= n)
      .filter(x -> n % x == 0)
      .isEmpty());

или:

//
//
public static IntPredicate isPrime2 = n -> n < 4 || (n % 2 != 0 &&
  IntStream.range(3, (int) Math.sqrt(n) + 2, 2)
      .filter(x -> n % x == 0)
      .isEmpty());

Есть также другие очень полезные методы, которые отсутствуют в классе Stream. Один — zip(и наоборот unzip), который принимает два потока и возвращает поток кортежей (но в Java 8 тоже нет кортежей!).

Предыдущие статьи

Что не так в Java 8, часть I: каррирование против замыканий

Что не так в Java 8, часть II: функции и примитивы

Что не так в Java 8, часть III: потоки и параллельные потоки

Что не так в Java 8, часть IV: монады

Что не так в Java 8, часть V: кортежи

Что не так в Java 8, часть VI: Строгость