番石榴的 Streams::findLast 实现

Question

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

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

本质上，老实说，实现并没有那么复杂，但这里有一些我觉得有点奇怪的事情（如果这个问题被关闭为“基于意见的”，我会在这里承担责任，我知道这可能会发生） .

---

首先是创建OptionalState类，这可以用单个元素的数组替换：

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

并使用简单如下：

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

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

1) 当已知某个 Spliterator 为空时：

if (spliterator.getExactSizeIfKnown() == 0) 

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

2) 那么如果已知 Spliterator 是SUBSIZED. 这是“happy-path”场景；在这种情况下，我们可以将其拆分，直到到达最后一个元素。基本上实现说：拆分直到prefix是null或者它为空（在这种情况下使用“正确”拆分器），或者如果拆分后“正确”拆分器已知为空，则使用prefix一个。这是通过以下方式完成的：

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

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

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

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

3）该方法的这个部分是当Spliterator已知不是SUBSIZED，在这种情况下，它不具有已知的尺寸; 因此它依赖于来自源的 Spliterator 是如何实现的，在这种情况下实际上findLast没有什么意义......例如 a Spliteratorfrom aHashSet将返回最后一个条目在最后一个桶中的任何内容......

Answer 1

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

   令我感到奇怪的是，这个仅用作 的本地类Consumer没有实现，Consumer但需要通过 进行绑定state::set。

2. 考虑

   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而不是仅仅进行拆分并检查结果是否具有已知大小时，这看起来很奇怪。毕竟，当特征不存在时，代码无论如何都会在替代分支中进行拆分。在我的旧答案中，我做了预测试以避免分配数据结构，但在这里，ArrayDeque总是创建和使用。但我认为，即使是我的旧答案也可以简化。

3. 我不确定你的目标是什么。当 aSpliterator具有ORDERED特征时，遍历和分裂的顺序是明确定义的。由于HashSet不是有序的，术语“last”是没有意义的。如果您是激进的，您可以优化操作以仅返回无序流的第一个元素；这是有效的，而且速度要快得多。

   奇怪的是，这个条件是：

   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"))，它将回退到遍历，因为第一个前缀的已知大小为零。