并行流上的 iterator() 方法是否保证遇到元素的顺序？

Question

Stream.of(a, b, c).parallel().map(Object::toString).iterator();

返回的迭代器是否保证以 a、b、c 的顺序提供值？

我知道 toArray() 和 collect() 保证了按正确顺序收集的集合。同时，我不是在询问如何从迭代器创建流。

- David Leston

---

我知道toArray()和collect()保证了值按正确顺序排列的集合。你在哪里看到的？许多集合甚至没有排序的概念。 - shmosel

好的，我在 副作用 部分找到了以下引用：*IntStream.range(0,5).parallel().map(x -> x*2).toArray() 必须生成 [0, 2, 4, 6, 8]*。奇怪的是文档没有更清晰地说明哪些操作尊重遭遇顺序，特别是考虑到 forEach()、forEachOrdered() 的区别。 - shmosel

有些关联：我之前关于 Stream.max() 如何处理相等的问题，Holger 掘出了 Brian Goetz 的以下评论："如果流是有序的（例如从数组或 List 获取的流），则在存在多个最大元素的情况下，它返回第一个最大元素；只有当流是无序的时才允许选择任意一个元素。" - Hulk

这段内容与顺序和并行无关，但我认为这是确认所有未明确说明它们删除排序或明确不确定性的Stream操作都需要保持遭遇顺序。 - Hulk

Answer 1

这是规范中的一个疏漏。如果流具有定义的相遇顺序，那么其迭代器应按相遇顺序产生元素。如果流没有定义的相遇顺序，则迭代器当然会按某种顺序产生元素，但该顺序不会被定义。

我已提交错误JDK-8194952来跟踪规范的更改。

看起来其他人已经足够地了解实现，以显示它确实会按相遇顺序产生元素。此外，我们的流测试依赖于此属性。例如，对于toList收集器的测试断言列表中的元素按与从流的迭代器获取的顺序相同的顺序出现。因此，即使尚未正式指定此行为，您可能可以放心依赖此行为。

- Stuart Marks

---

是的，其他操作也需要澄清，即使是 map 和 filter 也没有指定任何内容。或者只需添加一个明确的语句，说明操作保持遇到的顺序（如果有的话），除非另有说明。如果我们在这方面，对于有序流而言，max() 和 min() 在平局情况下返回第一个元素，例如 reduce((a,b)->a) 返回第一个元素，reduce((a,b)->b) 返回最后一个元素也仅仅是隐含的。而且，如果只有一个输入是无序的，则 Stream.concat 是无序的，例如 concat(range(0, 10), empty())，这是显式的，但是这是一个可怕的决定... - Holger

经过测试，.iterator()似乎可以将并行流转换为顺序流，这使得这个问题无关紧要。 - David Leston

Answer 2

Stream.of方法可用于从其他未关联的值创建流，返回一个顺序有序的流。

返回一个其元素为指定值的顺序有序流。

根据java.util.stream包的Javadocs中的副作用部分：

IntStream.range(0,5).parallel().map(x -> x*2).toArray()必须产生[0, 2, 4, 6, 8]

这意味着parallel()和map()会保留流是否是顺序/有序的信息。

我已经追踪了Stream.of创建的Stream的实现到一个名为ReferencePipeline的类。

@Override
public final Iterator<P_OUT> iterator() {
    return Spliterators.iterator(spliterator());
}

该实现的iterator()方法调用Spliterator.iterator()，其代码通过简单地依赖于Spliterator的tryAdvance方法来适配Iterator接口，并且不会更改任何流特征：

public static<T> Iterator<T> iterator(Spliterator<? extends T> 
    spliterator) {
    Objects.requireNonNull(spliterator);
    class Adapter implements Iterator<T>, Consumer<T> {
        boolean valueReady = false;
        T nextElement;

        @Override
        public void accept(T t) {
            valueReady = true;
            nextElement = t;
        }

        @Override
        public boolean hasNext() {
            if (!valueReady)
                spliterator.tryAdvance(this);
            return valueReady;
        }

        @Override
        public T next() {
            if (!valueReady && !hasNext())
                throw new NoSuchElementException();
            else {
                valueReady = false;
                return nextElement;
            }
        }
    }

    return new Adapter();
}

总的来说，是的，顺序是有保障的，因为Stream.of创建了一个“顺序有序流”，而你上面使用的parallel、map或iterator操作都不会改变这些特征。实际上，iterator使用底层的Stream Spliterator来迭代流元素。

- rgettman

---

通过展示实现来证明规范是不可行的。 - shmosel

我仍然认为Javadoc在OP情况下并不“保证”顺序。在Javadoc中没有任何地方说明iterator方法总是会遵守遇到的顺序。 - tsolakp

这段代码证明了Iterator不会改变Spliterator的顺序，因此你只是把问题转化为“并行流上的spliterator()是否保证遇到顺序？” - Holger

Answer 3

到目前为止，我找到的最接近保证的陈述是java.util.stream的包文档中以下声明：

“除了被明确标识为非确定性的操作（例如findAny()），流以顺序执行还是并行执行不应更改计算的结果。”

可以说，iterator()生成按不同顺序迭代的Iterator与生成按不同顺序包含元素的collect()的List一样，都会导致“结果的变化”。

- Hulk

Answer 4

是的，它会。这是因为终端操作（除非在文档中另有说明，例如forEach - 明确指定为非确定性而不是forEachOrdered）会保留遇到的顺序。而你的Stream.of确实返回一个有序的流；这个顺序没有被任何地方打破（例如通过unordered或sorted/distinct）。

- Eugene

---

你有证据证明终端操作会尊重遇到的顺序，除非另有规定吗？ - shmosel

@shmosel 我记得读过这个话题，如果我没记错的话是 Stuart Marks（或者 Holger？）说的。等我找到了会更新。 - Eugene

@shmosel 对于这个策略，没有明确的陈述并非一个好情况，但事实上维护顺序并没有明确说明。举例来说，像 filter 或 map 这样的简单操作甚至都没有关于保持顺序的说明。即使对于 reduce 和 collect，您也只能从函数必须结合但不需要交换律这一事实中推导出维护顺序的规则。 - Holger

@shmosel 看看我刚才发布的回答。简单来说，这是一个规格错误。我不认为我在其他任何地方讨论过这个问题，但有可能我已经忘记了。 - Stuart Marks

@Holger 请看我上面的评论。 - Stuart Marks

Answer 5

考虑到文档中所述的Stream.of返回有序流，以及您展示的任何中间操作都不会改变这种行为，因此我们可以说，在枚举时，保证返回的iterator按顺序提供值2, 3, 4，因为在有序流或序列（例如List实现）上调用iterator终端操作应该按照那个顺序产生元素。

因此，只要我们有一个有序源、中间操作和终端操作，它们遵守这个顺序，无论代码是按顺序还是并行执行，顺序都应该得到维护。

- Ousmane D.

---

你说 iterator() 遵循遇到顺序的依据是什么？ - shmosel

@shmosel并不是说这适用于每种情况。但就所提供的示例而言，它应该遵守遭遇顺序，因为流保持有序。 - Ousmane D.

这是一个自我重言。仅因为流是有序的，并不意味着每个操作都会尊重它的顺序。forEach()不会，许多收集器也不会。 - shmosel

@shmosel 对的，那就是 forEach... 但是如果一个流或源有指定的顺序（保留顺序），那么使用 Iterator 枚举元素时应该按照该顺序检索元素。 - Ousmane D.

@shmosel 请注意，正如我在答案中提到的那样，如果源和中间操作以及终端操作遵守相遇顺序，那么流是否并行执行都无关紧要，因为我们应该保持相遇顺序。所以我不是仅仅说“只因一个流是有序的”。至于迭代器，在枚举元素时检索的顺序取决于我们处理的是哪种类型的集合或流。 - Ousmane D.