Java 8 流，获取头部和尾部

java scala java-8 java-stream sieve

2022-09-01 21:15:00

Java 8引入了一个类似于Scala的Stream的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 closedfindFirst()skip()Stream

我真的不必用两次流，因为我所需要的只是流中的第一个数字，其余的作为另一个流，即相当于Scala的和。Java 8 中是否有一种方法可以让我实现此目的？Stream.headStream.tailStream

谢谢。

答案 1

即使你没有问题，你不能拆分一个，你的代码也不起作用，因为你是递归而不是懒惰地调用你的方法。因此，在查询生成的流以获取第一个值之前，您有一个无穷大递归。IntStreamsieve

将 a 拆分为头和尾（尚未消耗）是可能的：IntStream sIntStream

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

在这个地方，你需要一个懒惰地在尾巴上调用的结构。没有提供; 期望现有的流实例作为参数，并且您不能使用 lambda 表达式懒惰地构造调用的流，因为延迟创建仅使用 lambda 表达式不支持的可变状态工作。如果没有隐藏可变状态的库实现，则必须使用可变对象。但是，一旦您接受了可变状态的要求，解决方案就可能比您的第一种方法更容易：sieveStreamconcatsieve

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);
}

这将以递归方式创建一个筛选器，但最终，无论你是创建 s 树还是 s 树都无关紧要（就像你的方法一样，如果它确实有效）。如果您不喜欢过滤器的可变实例字段，则可以将其隐藏在内部类中（但不能隐藏在 lambda 表达式中...）。IntPredicateIntStreamIntStream.concat

答案 2

我的 StreamEx 库现在有 headTail（） 操作，它解决了这个问题：

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

该方法采用在流终端操作执行期间最多执行一次的方法。所以这个实现是懒惰的：在遍历开始之前，它不会计算任何东西，并且只计算请求的质数。接收第一个流元素和其余元素的流，并可以以所需的任何方式修改。您可以将其与预定义的输入一起使用：headTailBiFunctionBiFunctionheadtailtail

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);

比较递归解决方案很有趣：它们能够生成多少素数。

@John McClean 解决方案（StreamUtils）

John McClean的解决方案并不懒惰：你不能用无限的流来喂养它们。所以我只是通过试错找到了最大允许上限（）（之后StackOverflowError发生）：17793

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

@John McClean 解决方案（可流式传输）

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

将上限提高到以上会导致 StackOverflowError。39990

@frhack解决方案（LazySeq）

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

结果：卡在素数之后 = 巨大的堆分配和垃圾回收占 90% 以上。从53323前进到53327花了几分钟，所以等待更多似乎不切实际。53327

@vidi解决方案

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

结果：堆栈溢出素数 = 之后的错误。134417

我的解决方案（StreamEx）

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

结果：堆栈溢出素数 = 之后的错误。236167

@frhack解决方案（rxjava）

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

结果：堆栈溢出素数 = 之后的错误。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);

结果：堆栈溢出素数 = 之后的错误。368089

我的解决方案（带谓词串联的 StreamEx）

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

结果：堆栈溢出素数 = 之后的错误。368287

因此，三个涉及谓词串联的解决方案获胜，因为每个新条件仅增加 2 个堆栈帧。我认为，它们之间的差异很小，不应该被视为定义赢家。然而，我更喜欢我的第一个StreamEx解决方案，因为它更类似于Scala代码。