Возможно ли разумно эмулировать синтаксис yield, возможно, с помощью Java 8?

Ответ 1

Ну, я думаю, что мы увлеклись использованием Streams API из "снаружи", используя flatMap, оптимизируя алгоритм поиска палиндрома и т.д. См. ответы Борис Паук и assylias. Тем не менее, мы обошли оригинальный вопрос о том, как написать генераторную функцию, используя что-то вроде инструкции Python yield. (Я думаю, что OP, вложенный, например, с помощью yield, использовал Python.)

Одна из проблем с использованием flatMap заключается в том, что параллельное расщепление может происходить только во внешнем потоке. Внутренние потоки (возвращаемые из flatMap) обрабатываются последовательно. Мы могли бы попытаться сделать внутренние потоки параллельными, но они могли бы конкурировать с внешними. Я полагаю, что вложенное расщепление может работать, но я не слишком уверен.

Один из подходов - использовать Stream.generate или (как ответ assylias) функции Stream.iterate. Тем не менее, они создают бесконечные потоки, поэтому для завершения потока должен быть предоставлен внешний limit.

Было бы хорошо, если бы мы могли создать конечный, но "сплющенный" поток, чтобы весь поток значений подвергался расщеплению. К сожалению, создание потока не так удобно, как функции генератора Python. Однако это можно сделать без особых проблем. Вот пример, который использует классы StreamSupport и AbstractSpliterator:

class Generator extends Spliterators.AbstractIntSpliterator {
    final int min;
    final int max;
    int i;
    int j;

    public Generator(int min, int max) {
        super((max - min) * (max - min), 0);
        this.min = min;
        this.max = max;
        i = min;
        j = min;
    }

    public boolean tryAdvance(IntConsumer ic) {
        if (i == max) {
            return false;
        }
        ic.accept(i * j);
        j++;
        if (j == max) {
            i++;
            j = min;
        }
        return true;
    }
}

public static void main(String[] args) {
    Generator gen = new Generator(100, 1000);
    System.out.println(
        StreamSupport.intStream(gen, false)
            .filter(i -> isPalindrome(i))
            .max()
            .getAsInt());
}

Вместо того, чтобы переменные итерации находились в стеке (как в подходе с вложенными данными с доходностью), мы должны сделать их полями объекта и прирастить tryAdvance до завершения итерации. Теперь это простейшая форма разделителя, и это не обязательно хорошо распараллеливает. С дополнительной работой можно было реализовать метод trySplit для лучшего расщепления, что, в свою очередь, позволило бы лучше parallelism.

Метод forEachRemaining может быть переопределен, и он будет выглядеть почти как пример вложенного цикла для примера с вызовом IntConsumer вместо yield. К сожалению, tryAdvance является абстрактным и поэтому должен быть реализован, поэтому все же необходимо, чтобы переменные итерации были полями объекта.

Ответ 2

Как смотреть на него с другого направления:

Вы хотите Stream от [100,1000), и для каждого элемента этого Stream вам нужен еще один Stream этого элемента, умноженный на каждый из [100, 1000). Это то, что flatMap для:

public static void main(final String[] args) throws Exception {
    OptionalInt max = IntStream.range(100, 1000).
            flatMap((i) -> IntStream.range(i, 1000).map((j) -> i * j)).
            unordered().
            parallel().
            filter((i) -> {
                String forward = Integer.toString(i);
                String backward = new StringBuilder(forward).reverse().toString();
                return forward.equals(backward);
            }).
            max();
    System.out.println(max);
}

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

final String asString = Integer.toString(i);
for (int j = 0, k = asString.length() - 1; j < k; j++, k--) {
    if (asString.charAt(j) != asString.charAt(k)) {
        return false;
    }
}
return true;

Он дает тот же ответ, но я не подвергал его строгому тестированию... Кажется, на моей машине около 100 мс.

Также не уверен, что эта проблема достаточно велика для unordered().parallel() - удаление, что дает немного повысить скорость тоже.

Просто попытался продемонстрировать возможности API Stream.

ИЗМЕНИТЬ

Как отмечает @Stuart в комментариях, поскольку умножение является коммутативным, нам нужно только IntStream.range(i, 1000) в подпотоке. Это связано с тем, что после проверки a x b нам не нужно проверять b x a. Я обновил ответ.

Ответ 3

Я отдам его. Версия с петлей, затем с потоком. Хотя я начинаю с другого конца, так что это проще, потому что я могу limit(1).

public class Problem0004 {

    public static void main(String[] args) {
        int maxNumber = 999 * 999;
        //with a loop
        for (int i = maxNumber; i > 0; i--) {
            if (isPalindrome(i) && has3DigitsFactors(i)) {
                System.out.println(i);
                break;
            }
        }
        //with a stream
        IntStream.iterate(maxNumber, i -> i - 1)
                .parallel()
                .filter(i -> isPalindrome(i) && has3DigitsFactors(i))
                .limit(1)
                .forEach(System.out::println);
    }

    private static boolean isPalindrome(int n) {
        StringBuilder numbers = new StringBuilder(String.valueOf(n));
        return numbers.toString().equals(numbers.reverse().toString());
    }

    private static boolean has3DigitsFactors(int n) {
        for (int i = 999; i > 0; i--) {
            if (n % i == 0 && n / i < 1000) {
                return true;
            }
        }
        return false;
    }
}

Ответ 4

Всегда существовали способы эмулировать эту переоцененную функцию yield, даже без Java 8. В основном речь идет о сохранении состояния выполнения, то есть кадра (ов) стека, который может выполняться потоком. Очень простая реализация может выглядеть так:

import java.util.Iterator;
import java.util.NoSuchElementException;

public abstract class Yield<E> implements Iterable<E> {
  protected interface Flow<T> { void yield(T item); }
  private final class State implements Runnable, Iterator<E>, Flow<E> {
    private E nextValue;
    private boolean finished, value;

    public synchronized boolean hasNext() {
      while(!(value|finished)) try { wait(); } catch(InterruptedException ex){}
      return value;
    }
    public synchronized E next() {
      while(!(value|finished)) try { wait(); } catch(InterruptedException ex){}
      if(!value) throw new NoSuchElementException();
      final E next = nextValue;
      value=false;
      notify();
      return next;
    }
    public void remove() { throw new UnsupportedOperationException(); }
    public void run() {
      try { produce(this); }
      finally {
        synchronized(this) {
          finished=true;
          notify();
        }
      }
    }
    public synchronized void yield(E next) {
      while(value) try { wait(); } catch(InterruptedException ex){}
      nextValue=next;
      value=true;
      notify();
    }
  }

  protected abstract void produce(Flow<E> f);

  public Iterator<E> iterator() {
    final State state = new State();
    new Thread(state).start();
    return state;
  }
}

Как только у вас будет такой класс-помощник, прецедент будет выглядеть прямолинейно:

// implement a logic the yield-style
Iterable<Integer> y=new Yield<Integer>() {
  protected void produce(Flow<Integer> f) {

    for (int i = min; i < max; i++) {
      for (int j = min; j < max; j++) {
          f.yield(i * j);
      }
    }

  }
};

// use the Iterable, e.g. in a for-each loop
int maxPalindrome=0;
for(int i:y) if(isPalindrome(i) && i>maxPalindrome) maxPalindrome=i;
System.out.println(maxPalindrome);

В предыдущем коде не использовались функции Java 8. Но это позволит использовать их без каких-либо изменений:

// the Java 8 way
StreamSupport.stream(y.spliterator(), false).filter(i->isPalindrome(i))
  .max(Integer::compare).ifPresent(System.out::println);

Обратите внимание, что класс поддержки yield выше не является самой эффективной реализацией, и он не обрабатывает случай, если итерация не завершена, а Iterator заброшена. Но это показывает, что такую ​​логику действительно можно реализовать на Java (в то время как другие ответы убедительно показывают, что такая логика yield не нужна для решения такой проблемы).