Guava 的 Streams::findLast 实现

Question

我正在研究 Guava 的 Streams::findLast 实现，在尝试理解它时，有几件事我根本无法理解。这是它的实现：

public static <T> java.util.Optional<T> findLast(Stream<T> stream) {
    class OptionalState {

        boolean set = false;
        T value = null;

        void set(@Nullable T value) {
            set = true;
            this.value = value;
        }

        T get() {
            checkState(set);
            return value;
        }
    }
    OptionalState state = new OptionalState();

    Deque<Spliterator<T>> splits = new ArrayDeque<>();
    splits.addLast(stream.spliterator());

    while (!splits.isEmpty()) {
        Spliterator<T> spliterator = splits.removeLast();

        if (spliterator.getExactSizeIfKnown() == 0) {
            continue; // drop this split
        }

        // Many spliterators will have trySplits that are SUBSIZED even if they are not themselves
        // SUBSIZED.
        if (spliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
            // we can drill down to exactly the smallest nonempty spliterator
            while (true) {
                Spliterator<T> prefix = spliterator.trySplit();
                if (prefix == null || prefix.getExactSizeIfKnown() == 0) {
                    break;
                } else if (spliterator.getExactSizeIfKnown() == 0) {
                    spliterator = prefix;
                    break;
                }
            }

            // spliterator is known to be nonempty now
            spliterator.forEachRemaining(state::set);
            return java.util.Optional.of(state.get());
        }

        Spliterator<T> prefix = spliterator.trySplit();
        if (prefix == null || prefix.getExactSizeIfKnown() == 0) {
            // we can't split this any further
            spliterator.forEachRemaining(state::set);
            if (state.set) {
                return java.util.Optional.of(state.get());
            }
            // fall back to the last split
            continue;
        }
        splits.addLast(prefix);
        splits.addLast(spliterator);
    }
    return java.util.Optional.empty();
}

从本质上讲，实现并没有那么复杂，但这里有一些我觉得有点奇怪的地方（如果这个问题被关闭为“基于意见”，我会在这里承担责任，我理解它可能会发生）。

首先是创建OptionalStateclass，这可以用单个元素的数组代替：

T[] state = (T[]) new Object[1];

并简单地用作：

spliterator.forEachRemaining(x -> state[0] = x);

那么整个方法可以拆分成3个部分：

当已知某个Spliterator为空时：

if (spliterator.getExactSizeIfKnown() == 0)

在这种情况下很容易 - 只需放下它即可。

那么如果已知 Spliterator 是 SUBSIZED。这是“幸福之路”的场景；在这种情况下，我们可以拆分它直到我们到达最后一个元素。基本上实现说：拆分直到 prefix 是 null 或者它是空的（在这种情况下消耗“右”拆分器）或者如果拆分后“右”拆分器已知为空，消耗 prefix 一个。这是通过以下方式完成的：

// 现在已知拆分器是非空的 spliterator.forEachRemaining(状态::设置); return java.util.Optional.of(state.get());

我的第二个问题实际上是关于这条评论的：

// Many spliterators will have trySplits that are SUBSIZED 
// even if they are not themselves SUBSIZED.

这很有趣，但我找不到这样的例子，如果有人能给我介绍一个，我将不胜感激。事实上，因为这个评论存在，下一个代码（方法的第 3 部分不能像第二个那样用 while(true) 完成），因为它假设在 trySplit 我们可以获得一个 Spliterator 即 SUBSIZED，即使我们最初的不是，所以它必须转到 findLast.

的最开始

方法的这一部分是当 Spliterator 不是是 SUBSIZED 并且在这种情况下它没有已知大小时；因此它依赖于源中的 Spliterator 是如何实现的，在这种情况下实际上 findLast 没有什么意义......例如 HashSet 中的 Spliterator 将 return无论最后一个条目在最后一个桶中...

Answer 1

当你迭代一个未知大小的Spliterator时，你必须跟踪是否遇到了一个元素。这可以通过调用 tryAdvance 并使用 return 值或通过使用 forEachRemaining 和记录是否遇到元素的 Consumer 来完成。当您走后一条路线时，专用 class 比数组更简单。一旦您有了专用的 class，为什么不将它也用于 SIZED 拆分器。

令我感到奇怪的是，这个本地 class，仅用作 Consumer，没有实现 Consumer，但需要通过 [= 绑定21=].

考虑

Stream.concat(
    Stream.of("foo").filter(s -> !s.isEmpty()),
    Stream.of("bar", "baz"))

表示整个流的Spliterator不能有SIZED特性。但是当分离出第一个大小未知的子流时，剩余的流具有已知大小。

测试代码：

Spliterator<String> sp = Stream.concat(
    Stream.of("foo").filter(s -> !s.isEmpty()),
    Stream.of("bar", "baz"))
    .spliterator();
do {
    System.out.println(
          "SIZED: "+sp.hasCharacteristics(Spliterator.SIZED)
        + ", SUBSIZED: "+sp.hasCharacteristics(Spliterator.SUBSIZED)
        + ", exact size if known: "+sp.getExactSizeIfKnown());
} while(sp.trySplit() != null);

结果：

SIZED: false, SUBSIZED: false, exact size if known: -1
SIZED: true, SUBSIZED: true, exact size if known: 2
SIZED: true, SUBSIZED: true, exact size if known: 1

但对我来说，当有人在评论中说知道分裂可以改变特征然后用 SUBSIZED 进行预测试而不是仅仅进行分裂并检查是否结果具有已知大小。毕竟，当特征不存在时，代码无论如何都会在替代分支中进行拆分。在my old answer中，我做了预测试以避免分配数据结构，但在这里，ArrayDeque总是被创建和使用。但我认为，即使是我的旧答案也可以简化。

我不知道你的目的是什么。当一个 Spliterator 具有 ORDERED 特性时，遍历和拆分的顺序是明确的。由于 HashSet 没有排序，所以术语“last”没有意义。如果你很激进，你可以将操作优化为 return 无序流的第一个元素；这是有效的，而且速度更快。

奇怪的是，这个条件是：
```
if (prefix == null || prefix.getExactSizeIfKnown() == 0) {
    // we can't split this any further
```
（以及 SUBSIZED 路径中类似的循环终止）

仅仅因为一个前缀碰巧有一个已知的零大小，并不意味着后缀不能进一步分裂。规范中没有这样说。

由于这种情况，Stream.concat(Stream.of("foo"), Stream.of("bar","baz")) 可以得到最佳处理，而对于 Stream.concat(Stream.of(), Stream.of("bar", "baz"))，它将回退到遍历，因为第一个前缀的已知大小为零。

Guava 的 Streams::findLast 实现

Guava's Streams::findLast implementation

java

guava

java-8

java-stream