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

老实说，实际上实现并不那么复杂，但我发现有些事情有点奇怪（如果这个问题被归结为“基于意见”，我会承担责任，我明白可能会发生这种情况）。

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

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

并且使用简单到：

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

然后整个方法可以分成3个部分：

if (spliterator.getExactSizeIfKnown() == 0) 

// 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.

Answer 1

>

当您迭代大小未知的拆分器时，必须跟踪是否遇到了元素。这可以通过调用TryAdvance并使用返回值来实现，或者通过将ForeachRealment与记录是否遇到元素的使用者一起使用来实现。当您走后一条路时，专用类比数组简单。一旦有了一个专用类，为什么不将它用于大小的拆分器。

令我感到奇怪的是，这个本地类只作为使用者而存在，它不实现使用者，而是需要通过state::set绑定。

考虑

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

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

但对我来说，当有人在评论中告诉我知道拆分可以改变特征，然后用subsided进行预测试，而不是只进行拆分并检查结果是否有已知的大小时，这看起来很奇怪。毕竟，当特征不存在时，代码无论如何都在替代分支中执行拆分。在我以前的回答中，我做了预测试以避免分配数据结构，但这里总是创建和使用Arraydeque。但我想，即使是我以前的答案也可以简化。

我不确定你的目的是什么。当拆分器具有ordered特性时，遍历和拆分的顺序是定义良好的。由于hashset没有排序，所以术语“last”没有意义。如果您是激进的，您可以优化操作，只返回无序流的第一个元素；这是有效的，而且要快得多。

奇怪的是，这个条件是：

if (prefix == null || prefix.getExactSizeIfKnown() == 0) {
    // we can't split this any further

（以及subsided路径中类似的循环终止）

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

由于这种情况，stream.concat(stream.of（“foo”）,stream.of（“bar”,“baz”））可以最优地处理，而对于stream.concat(stream.of（）,stream.of（“bar”,“baz”）），它将回到遍历，因为第一个前缀的大小已知为零。