Можно ли разумно эмулировать синтаксис yield, возможно, с помощью Java 8?
Я экспериментировал с этим вопросом сегодня, от Эйлера.
Палиндромное число читается одинаково в обоих направлениях. Самый большой палиндром из двух двузначных чисел равен 9009 = 91 × 99.
Найдите самый большой палиндром из двух трехзначных чисел.
Я думал об этом, и это, конечно, можно сделать с помощью циклов for, однако я хочу использовать Java 8, так как он открывает новые возможности.
Однако, прежде всего, я не знаю, как генерировать IntStream который производит такие элементы, так что я все равно использовал обычные циклы for:
public class Problem4 extends Problem<Integer> {
private final int digitsCount;
private int min;
private int max;
public Problem4(final int digitsCount) {
this.digitsCount = digitsCount;
}
@Override
public void run() {
List<Integer> list = new ArrayList<>();
min = (int)Math.pow(10, digitsCount - 1);
max = min * 10;
for (int i = min; i < max; i++) {
for (int j = min; j < max; j++) {
int sum = i * j;
if (isPalindrome(sum)) {
list.add(sum);
}
}
}
result = list.stream().mapToInt(i -> i).max().getAsInt();
}
private boolean isPalindrome(final int number) {
String numberString = String.valueOf(number);
String reversed = new StringBuilder(numberString).reverse().toString();
return (numberString.equals(reversed));
}
@Override
public String getName() {
return "Problem 4";
}
}
Как вы можете видеть, я могу быть немного ленивым, IntStream::max Это очень хороший метод, и я думаю, что лучше использовать его, чтобы написать его самостоятельно.
Здесь возникает проблема, хотя, мне нужно иметь list Теперь я могу получить максимум таким способом, а это значит, что мне нужно хранить данные там, где я действительно не должен этого делать.
Итак, вопрос сейчас, возможно ли реализовать это в Java 8?
for (int i = min; i < max; i++) {
for (int j = min; j < max; j++) {
yield i * j;
}
}
А затем из этого метода создать PrimitiveIterator.OfInt (распаковывает версию Iterator<Integer>или создайте IntStream напрямую?
Затем получить ответ с streamFromYield.filter(this::isPalindrome).max().getAsInt() было бы действительно легко реализовать.
Наконец, я знаю, что этот вопрос задавался ранее, однако в последний раз это было совсем немного назад, и теперь Java 8 появится очень скоро, где они были добавлены как большая концепция. Stream<T> и новая языковая конструкция, называемая лямбдами.
Поэтому создание такого кода сейчас может сильно отличаться от того, когда люди создавали его для Java 6 или 7.
4 ответа
Ну, я думаю, что мы увлеклись использованием Streams API извне, используя flatMapоптимизация алгоритма поиска палиндрома и т. д. См. ответы Бориса Паука и ассилий. Тем не менее, мы обошли первоначальный вопрос о том, как написать функцию генератора, используя что-то вроде Python yield заявление. (Я думаю, что OP является вложенным, например, с yield использовал Python.)
Одна из проблем с использованием flatMap является то, что параллельное расщепление может происходить только на самом внешнем потоке. Внутренние потоки (возвращенные из flatMap) обрабатываются последовательно. Мы могли бы попытаться сделать внутренние потоки также параллельными, но они могли бы конкурировать с внешними. Я полагаю, что вложенное разбиение может работать, но я не слишком уверен в этом.
Одним из подходов является использование Stream.generate или (как ответ Ассилия) 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 метод для лучшего разделения, что, в свою очередь, позволило бы улучшить параллелизм.
forEachRemaining метод может быть переопределен, и он будет выглядеть почти как пример вложенного цикла с выходом, вызывая IntConsumer вместо yield, к несчастью tryAdvance является абстрактным и, следовательно, должен быть реализован, поэтому все еще необходимо, чтобы переменные итерации были полями объекта.
Как насчет того, чтобы смотреть на это с другой стороны:
Вы хотите 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() - удаление, которое также дает небольшой прирост скорости.
Просто пытался продемонстрировать возможности Stream API.
РЕДАКТИРОВАТЬ
Как указывает @Stuart в комментариях, так как умножение является коммутативным, нам нужно только IntStream.range(i, 1000) в подпотоке. Это потому, что как только мы проверим a x b нам не нужно проверять b x a, Я обновил ответ.
Всегда были способы подражать этому переоцененному 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 логика не нужна для решения такой проблемы).
Я попробую. Версия с петлей, затем с потоком. Хотя я начинаю с другого конца, так что легче, потому что я могу 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;
}
}