Java 8 Stream, получая голову и хвост

java scala java-8 java-stream

7897 просмотра

9 ответа

2034 Репутация автора

Java 8 представила класс Stream, который похож на Scala Stream , мощную ленивую конструкцию, с помощью которой можно сделать что-то подобное очень кратко:

def from(n: Int): Stream[Int] = n #:: from(n+1)

def sieve(s: Stream[Int]): Stream[Int] = {
  s.head #:: sieve(s.tail filter (_ % s.head != 0))
}

val primes = sieve(from(2))

primes takeWhile(_ < 1000) print  // prints all primes less than 1000

Я задавался вопросом, возможно ли сделать это в Java 8, поэтому я написал что-то вроде этого:

IntStream from(int n) {
    return IntStream.iterate(n, m -> m + 1);
}

IntStream sieve(IntStream s) {
    int head = s.findFirst().getAsInt();
    return IntStream.concat(IntStream.of(head), sieve(s.skip(1).filter(n -> n % head != 0)));
}

IntStream primes = sieve(from(2));

Довольно простой, но он производит java.lang.IllegalStateException: stream has already been operated upon or closedпотому, что оба findFirst()и skip()являются терминальными операциями, Streamкоторые могут быть выполнены только один раз.

Мне не нужно использовать поток дважды, так как все, что мне нужно, - это первое число в потоке, а остальное - как другой поток, то есть эквивалент Scala Stream.headи Stream.tail. Есть ли метод в Java 8, Streamкоторый я могу использовать для достижения этой цели?

Благодарю.

Автор: lyomi Источник Размещён: 06.11.2013 02:37

Ответы (9)


10 плюса

164748 Репутация автора

Решение

Даже если у вас не было проблемы, которую вы не можете разделить IntStream, ваш код не работал, потому что вы вызываете свой sieveметод рекурсивно, а не лениво. Таким образом, у вас была бесконечная рекурсия, прежде чем вы могли запросить ваш результирующий поток для первого значения.

Возможно разделение IntStream sголовы и хвоста IntStream(который еще не употреблен):

PrimitiveIterator.OfInt it = s.iterator();
int head = it.nextInt();
IntStream tail = IntStream.generate(it::next).filter(i -> i % head != 0);

В этом месте вам нужно sieveлениво вызвать конструкцию вызова . Streamне обеспечивает это; concatожидает существующие экземпляры потока в качестве аргументов, и вы не можете создать поток, вызывающий sieveлениво с лямбда-выражением, так как ленивое создание работает только с изменяемым состоянием, которое лямбда-выражения не поддерживают. Если у вас нет реализации библиотеки, скрывающей изменяемое состояние, вы должны использовать изменяемый объект. Но как только вы принимаете требование изменяемого состояния, решение может быть даже проще, чем ваш первый подход:

IntStream primes = from(2).filter(i -> p.test(i)).peek(i -> p = p.and(v -> v % i != 0));

IntPredicate p = x -> true;

IntStream from(int n)
{
  return IntStream.iterate(n, m -> m + 1);
}

Это рекурсивно создаст фильтр, но, в конце концов, не имеет значения, создаете ли вы дерево IntPredicates или дерево IntStreams (как с вашим IntStream.concatподходом, если он работал). Если вам не нравится изменяемое поле экземпляра для фильтра, вы можете скрыть его во внутреннем классе (но не в лямбда-выражении ...).

Автор: Holger Размещён: 15.11.2013 05:40

2 плюса

132975 Репутация автора

Вы можете по существу реализовать это так:

static <T> Tuple2<Optional<T>, Seq<T>> splitAtHead(Stream<T> stream) {
    Iterator<T> it = stream.iterator();
    return tuple(it.hasNext() ? Optional.of(it.next()) : Optional.empty(), seq(it));
}

В приведенном выше примере Tuple2и Seqтипы заимствованы из jOOλ , библиотеки, которую мы разработали для интеграционных тестов jOOQ . Если вы не хотите никаких дополнительных зависимостей, вы можете также реализовать их самостоятельно:

class Tuple2<T1, T2> {
    final T1 v1;
    final T2 v2;

    Tuple2(T1 v1, T2 v2) {
        this.v1 = v1;
        this.v2 = v2;
    }

    static <T1, T2> Tuple2<T1, T2> tuple(T1 v1, T2 v2) {
        return new Tuple<>(v1, v2);
    }
}

static <T> Tuple2<Optional<T>, Stream<T>> splitAtHead(Stream<T> stream) {
    Iterator<T> it = stream.iterator();
    return tuple(
        it.hasNext() ? Optional.of(it.next()) : Optional.empty,
        StreamSupport.stream(Spliterators.spliteratorUnknownSize(
            it, Spliterator.ORDERED
        ), false)
    );
}
Автор: Lukas Eder Размещён: 22.09.2014 02:28

0 плюса

2696 Репутация автора

Чтобы получить преимущество, вам нужна реализация Lazy Stream. Java 8 stream или RxJava не подходят.

Вы можете использовать, например, LazySeq следующим образом.

Ленивые последовательности всегда просматриваются с самого начала с использованием очень дешевой декомпозиции first / rest (head () и tail ())

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


package com.company;

import com.nurkiewicz.lazyseq.LazySeq;

public class Main {

    public static void main(String[] args) {

        LazySeq<Integer> ints = integers(2);
        LazySeq primes = sieve(ints);
        primes.take(10).forEach(p -> System.out.println(p));

    }

    private static LazySeq<Integer> sieve(LazySeq<Integer> s) {
        return LazySeq.cons(s.head(), () -> sieve(s.filter(x -> x % s.head() != 0)));
    }

    private static LazySeq<Integer> integers(int from) {
        return LazySeq.cons(from, () -> integers(from + 1));
    }

}
Автор: frhack Размещён: 06.06.2015 10:23

0 плюса

2696 Репутация автора

Вот еще один рецепт с использованием способа, предложенного Хольгером. Он использует RxJava только для того, чтобы добавить возможность использовать метод take (int) и многие другие.

package com.company;

import rx.Observable;

import java.util.function.IntPredicate;
import java.util.stream.IntStream;

public class Main {

    public static void main(String[] args) {

        final IntPredicate[] p={(x)->true};
        IntStream primesStream=IntStream.iterate(2,n->n+1).filter(i -> p[0].test(i)).peek(i->p[0]=p[0].and(v->v%i!=0)   );

        Observable primes = Observable.from(()->primesStream.iterator());

        primes.take(10).forEach((x) -> System.out.println(x.toString()));


    }

}
Автор: frhack Размещён: 06.06.2015 11:11

2 плюса

690 Репутация автора

Решение ниже не делает мутации состояния, за исключением деконструкции головы / хвоста потока.

Ленивость получается с помощью IntStream.iterate. Класс Prime используется для поддержания состояния генератора

    import java.util.PrimitiveIterator;
    import java.util.stream.IntStream;
    import java.util.stream.Stream;

    public class Prime {
        private final IntStream candidates;
        private final int current;

        private Prime(int current, IntStream candidates)
        {
            this.current = current;
            this.candidates = candidates;
        }

        private Prime next()
        {
            PrimitiveIterator.OfInt it = candidates.filter(n -> n % current != 0).iterator();

            int head = it.next();
            IntStream tail = IntStream.generate(it::next);

            return new Prime(head, tail);
        }

        public static Stream<Integer> stream() {
            IntStream possiblePrimes = IntStream.iterate(3, i -> i + 1);

            return Stream.iterate(new Prime(2, possiblePrimes), Prime::next)
                         .map(p -> p.current);
        }
    }

Использование будет следующим:

Stream<Integer> first10Primes = Prime.stream().limit(10)
Автор: vidi Размещён: 17.09.2015 03:20

1 плюс

3729 Репутация автора

Если вы не возражаете против использования сторонних библиотек cyclops-streams , у моей библиотеки есть несколько потенциальных решений.

Класс StreamUtils имеет большое количество статических методов для работы напрямую с java.util.stream.Streamsвключением headAndTail.

HeadAndTail<Integer> headAndTail = StreamUtils.headAndTail(Stream.of(1,2,3,4));
int head = headAndTail.head(); //1
Stream<Integer> tail = headAndTail.tail(); //Stream[2,3,4]

Класс Streamable представляет собой воспроизводимый объект Streamи работает путем создания ленивой, кэширующей промежуточной структуры данных. Поскольку он кэшируется и подлежит возврату - голова и хвост могут быть реализованы напрямую и по отдельности.

Streamable<Integer> replayable=  Streamable.fromStream(Stream.of(1,2,3,4));
int head = repayable.head(); //1
Stream<Integer> tail = replayable.tail(); //Stream[2,3,4]

Циклоп-потоки также обеспечивает последовательное Streamрасширение, которое, в свою очередь, расширяет jOOλ и имеет как Tupleоснованные (из jOOλ), так и доменные (HeadAndTail) решения для извлечения головы и хвоста.

SequenceM.of(1,2,3,4)
         .splitAtHead(); //Tuple[1,SequenceM[2,3,4]

SequenceM.of(1,2,3,4)
         .headAndTail();

Обновление по запросу Тагира -> Java-версия сита Scala с использованием SequenceM

public void sieveTest(){
    sieve(SequenceM.range(2, 1_000)).forEach(System.out::println);
}

SequenceM<Integer> sieve(SequenceM<Integer> s){

    return s.headAndTailOptional().map(ht ->SequenceM.of(ht.head())
                            .appendStream(sieve(ht.tail().filter(n -> n % ht.head() != 0))))
                    .orElse(SequenceM.of());
}

И еще одна версия через Streamable

public void sieveTest2(){
    sieve(Streamable.range(2, 1_000)).forEach(System.out::println);
}

Streamable<Integer> sieve(Streamable<Integer> s){

    return s.size()==0? Streamable.of() : Streamable.of(s.head())
                                                    .appendStreamable(sieve(s.tail()
                                                                    .filter(n -> n % s.head() != 0)));
}

Обратите внимание - ни одна Streamableиз SequenceMних не имеет пустой реализации - отсюда проверка размера Streamableи использование headAndTailOptional.

Наконец версия с использованием простого java.util.stream.Stream

import static com.aol.cyclops.streams.StreamUtils.headAndTailOptional;

public void sieveTest(){
    sieve(IntStream.range(2, 1_000).boxed()).forEach(System.out::println);
}

Stream<Integer> sieve(Stream<Integer> s){

    return headAndTailOptional(s).map(ht ->Stream.concat(Stream.of(ht.head())
                            ,sieve(ht.tail().filter(n -> n % ht.head() != 0))))
                    .orElse(Stream.of());
}

Другое обновление - ленивая итерация, основанная на версии @ Holger с использованием объектов, а не примитивов (обратите внимание, что примитивная версия также возможна)

  final Mutable<Predicate<Integer>> predicate = Mutable.of(x->true);
  SequenceM.iterate(2, n->n+1)
           .filter(i->predicate.get().test(i))
           .peek(i->predicate.mutate(p-> p.and(v -> v%i!=0)))
           .limit(100000)
           .forEach(System.out::println);
Автор: John McClean Размещён: 11.01.2016 06:00

2 плюса

67780 Репутация автора

Моя библиотека StreamEx теперь имеет headTail()операцию, которая решает проблему:

public static StreamEx<Integer> sieve(StreamEx<Integer> input) {
    return input.headTail((head, tail) -> 
        sieve(tail.filter(n -> n % head != 0)).prepend(head));
}

headTailМетод занимает , BiFunctionкоторый будет выполняться не более одного раза во время выполнения операции потока терминала. Так что эта реализация ленива: она ничего не вычисляет, пока не начнется обход, и вычисляет только столько простых чисел, сколько требуется. BiFunctionПолучает первый элемент потока headи поток остальных элементов tailи может модифицировать tailлюбой способ, который хочет. Вы можете использовать его с предопределенным вводом:

sieve(IntStreamEx.range(2, 1000).boxed()).forEach(System.out::println);

Но бесконечный поток работает также

sieve(StreamEx.iterate(2, x -> x+1)).takeWhile(x -> x < 1000)
     .forEach(System.out::println);
// Not the primes till 1000, but 1000 first primes
sieve(StreamEx.iterate(2, x -> x+1)).limit(1000).forEach(System.out::println);

Есть также альтернативное решение, использующее headTailи предикатное объединение:

public static StreamEx<Integer> sieve(StreamEx<Integer> input, IntPredicate isPrime) {
    return input.headTail((head, tail) -> isPrime.test(head) 
            ? sieve(tail, isPrime.and(n -> n % head != 0)).prepend(head)
            : sieve(tail, isPrime));
}

sieve(StreamEx.iterate(2, x -> x+1), i -> true).limit(1000).forEach(System.out::println);

Интересно сравнить рекурсивные решения: сколько простых чисел они способны сгенерировать.

@Джон МакКлин решение ( StreamUtils)

Решения Джона МакКлина не ленивы: вы не можете кормить их бесконечным потоком. Таким образом, я просто нашел методом проб и ошибок максимально допустимую верхнюю границу ( 17793) (после этого возникает StackOverflowError):

public void sieveTest(){
    sieve(IntStream.range(2, 17793).boxed()).forEach(System.out::println);
}

@Джон МакКлин решение ( Streamable)

public void sieveTest2(){
    sieve(Streamable.range(2, 39990)).forEach(System.out::println);
}

Увеличение верхнего предела выше 39990приводит к StackOverflowError.

@frhack решение ( LazySeq)

LazySeq<Integer> ints = integers(2);
LazySeq primes = sieve(ints); // sieve method from @frhack answer
primes.forEach(p -> System.out.println(p));

Результат: застрять после простого числа = 53327с огромным распределением кучи и сборкой мусора, занимающей более 90%. Прошло несколько минут, чтобы продвинуться с 53323 до 53327, поэтому ждать больше кажется нецелесообразным.

@vidi решение

Prime.stream().forEach(System.out::println);

Результат: StackOverflowError после простого числа = 134417.

Мое решение (StreamEx)

sieve(StreamEx.iterate(2, x -> x+1)).forEach(System.out::println);

Результат: StackOverflowError после простого числа = 236167.

@frhack решение ( rxjava)

Observable<Integer> primes = Observable.from(()->primesStream.iterator());
primes.forEach((x) -> System.out.println(x.toString()));            

Результат: StackOverflowError после простого числа = 367663.

Решение @Holger

IntStream primes=from(2).filter(i->p.test(i)).peek(i->p=p.and(v->v%i!=0));
primes.forEach(System.out::println);

Результат: StackOverflowError после простого числа = 368089.

Мое решение (StreamEx с конкатенацией предикатов)

sieve(StreamEx.iterate(2, x -> x+1), i -> true).forEach(System.out::println);

Результат: StackOverflowError после простого числа = 368287.


Таким образом, три решения, включающие конкатенацию предикатов, выигрывают, потому что каждое новое условие добавляет только 2 кадра стека. Я думаю, что разница между ними незначительна и не должна рассматриваться для определения победителя. Однако мне больше нравится мое первое решение StreamEx, так как оно больше похоже на код Scala.

Автор: Tagir Valeev Размещён: 19.01.2016 10:33

-1 плюса

908 Репутация автора

Если вы хотите получить голову потока, просто:

IntStream.range(1, 5).first();

Если вы хотите получить хвост потока, просто:

IntStream.range(1, 5).skip(1);

Если вы хотите получить как голову, так и хвост, просто:

IntStream s = IntStream.range(1, 5);
int head = s.head();
IntStream tail = s.tail();

Если вы хотите найти простое число, просто:

LongStream.range(2, n)
   .filter(i -> LongStream.range(2, (long) Math.sqrt(i) + 1).noneMatch(j -> i % j == 0))
   .forEach(N::println);

Если вы хотите узнать больше, перейдите, чтобы получить AbacusUtil

Декларация: я разработчик AbacusUtil.

Автор: user_3380739 Размещён: 01.12.2016 07:43

0 плюса

766 Репутация автора

Здесь представлено много интересных предложений, но если кому-то нужно решение без зависимостей от сторонних библиотек, я придумаю следующее:

    import java.util.AbstractMap;
    import java.util.Optional;
    import java.util.Spliterators;
    import java.util.stream.StreamSupport;

    /**
     * Splits a stream in the head element and a tail stream.
     * Parallel streams are not supported.
     * 
     * @param stream Stream to split.
     * @param <T> Type of the input stream.
     * @return A map entry where {@link Map.Entry#getKey()} contains an
     *    optional with the first element (head) of the original stream
     *    and {@link Map.Entry#getValue()} the tail of the original stream.
     * @throws IllegalArgumentException for parallel streams.
     */
    public static <T> Map.Entry<Optional<T>, Stream<T>> headAndTail(final Stream<T> stream) {
        if (stream.isParallel()) {
            throw new IllegalArgumentException("parallel streams are not supported");
        }
        final Iterator<T> iterator = stream.iterator();
        return new AbstractMap.SimpleImmutableEntry<>(
                iterator.hasNext() ? Optional.of(iterator.next()) : Optional.empty(),
                StreamSupport.stream(Spliterators.spliteratorUnknownSize(iterator, 0), false)
        );
    }
Автор: Peter Размещён: 11.11.2018 12:22
Вопросы из категории :
32x32