找到流的最小元素，但如果 <= N 则尽早退出

Question

我想求一个大的（上亿个元素）IntStream的最小元素，但是我只能用>N的结果，所以我想一找到元素就跳槽<= N。我希望大多数时候最小值 <= N。

IntStream.min() 不会短路，所以我会卡住处理所有元素。一般IntStream.reduce也不短路

IntStream.noneMatch(x -> x <= N) 将确保最小元素 > N，如果不是，则短路，但实际上并没有告诉我最小值。我必须在谓词中维护状态（并添加同步或限于顺序流）以记住实际的最小值。或者，我可以递增 N 并重试，可能会在 N 的可能范围内进行某种二进制搜索，但这听起来既缓慢又复杂。

如何找到 IntStream 的最小值，一旦已知 <= N 就短路？

Answer 1

您可以使用 anyMatch 作弊。注意，这是未经测试的，有点粗略。请注意，尽管它有副作用，但内部 lambda 对于流显然不是有状态的。

final AtomicInteger min=new AtomicInteger(Integer.MAX_VALUE);
final int minLimit=?;
boolean isValid=!stream.anyMatch(i->{
    if(i<=minLimit){
        return true;
    }
    min.getAndAccumulate(i, Math::min);
    return false;
});

这是通过利用 anyMatch 的短路来实现的。

事实上，如果不将状态存储在 lambda 之外，可能无法做到这一点。这是因为为了做到这一点，我们必须是有状态的，以存储到目前为止的最小值，短路，并具有用户定义的行为。 docs 声明 IntStream 上没有这样的运算符。（只有限制是有状态的和短路的）。这似乎是关于 blocking/parallelism.

的问题

--更新-- 找到官方source对并行度的评论：

“除了标识为明确不确定的操作，例如 findAny()，流是顺序执行还是并行执行不应改变计算结果。

大多数流操作接受描述用户指定行为的参数，这些参数通常是 lambda 表达式。为了保持正确的行为，这些行为参数必须是无干扰的，并且在大多数情况下必须是无状态的。此类参数始终是功能接口（如 Function）的实例，并且通常是 lambda 表达式或方法引用。"

看起来问题是用户提供的行为，而不是短路。

Answer 2

我的第一个想法是使用 findAny 但后来我重新阅读了这个问题。 :-)

区别当然是findAny（或findFirst）一找到匹配的元素就短路。如果找到一个不匹配的元素，你想短路，然后减少或累积其余部分。

虽然积累是变异的一种形式并且被 FP 纯粹主义者所反对，但它有时确实派上用场。 Java 8 有一些很好的添加，例如 LongAccumulator，它们以低争用的方式累积原始值，使它们适合并行处理。可以把累加步骤放到peek流操作中。

不幸的是没有 "IntAccumulator" 所以你必须使用 long 值进行处理。您可以将源代码转换为 LongStream 或将 int 值映射为 long 值。

完成后，使用 allMatch 处理短路可能是最直接的方法。自然地，如果 allMatch returns false，则发生短路并且累加器实际上没有最小值。但它应该有迄今为止检查过的最小值，可能是触发短路的那个。

放在一起看起来像这样：

IntStream istream = ... 
LongAccumulator acc = new LongAccumulator(Long::min, Long.MAX_VALUE);

if (istream.mapToLong(i -> i).peek(acc::accumulate).allMatch(i -> i > N)) {
    System.out.println("min was " + acc.get());
} else {
    System.out.println("a value was <= " + N);
}

找到流的最小元素，但如果 <= N 则尽早退出

Find the minimum element of a stream, but bail out early if it's <= N

java

java-8

java-stream