java - 为什么 Java Streams 是一次性的？

Question

不像 C# 的 IEnumerable ，其中一个执行管道可以根据需要执行多次，而在 Java 中，一个流只能“迭代”一次。

对终端操作的任何调用都会关闭流，使其无法使用。
这个“功能”带走了很多力量。

我想这不是技术原因。这个奇怪的限制背后的设计考虑是什么？

编辑:为了演示我在说什么，请考虑以下 C# 中快速排序的实现:

IEnumerable<int> QuickSort(IEnumerable<int> ints)
{
  if (!ints.Any()) {
    return Enumerable.Empty<int>();
  }

  int pivot = ints.First();

  IEnumerable<int> lt = ints.Where(i => i < pivot);
  IEnumerable<int> gt = ints.Where(i => i > pivot);

  return QuickSort(lt).Concat(new int[] { pivot }).Concat(QuickSort(gt));
}

现在可以肯定的是，我并不是在提倡这是快速排序的一个很好的实现!然而，它是 lambda 表达式与流操作相结合的表现力的一个很好的例子。

它不能在Java中完成!
我什至不能在不使其无法使用的情况下询问流是否为空。

Answer 1

我对 Streams API 的早期设计有一些记忆，这些记忆可能会阐明设计原理。

早在 2012 年，我们就在语言中添加了 lambda，我们想要一个面向集合或“批量数据”的操作集，使用 lambda 进行编程，以促进并行性。在这一点上，懒惰地将操作链接在一起的想法已经很好地建立了。我们也不希望中间操作存储结果。

我们需要决定的主要问题是链中的对象在 API 中的样子以及它们如何连接到数据源。来源通常是集合，但我们也希望支持来自文件或网络的数据，或者即时生成的数据，例如来自随机数生成器。

现有工作对设计有很多影响。其中比较有影响的是谷歌的 Guava 库和 Scala 集合库。 (如果有人对 Guava 的影响感到惊讶，请注意 Guava 首席开发人员 Kevin Bourrillion 是 JSR-335 Lambda 专家组的成员。)在 Scala 集合上，我们发现 Martin Odersky 的这个演讲特别有趣:Future-Proofing Scala Collections: from Mutable to Persistent to Parallel。 (斯坦福 EE380，2011 年 6 月 1 日。)

我们当时的原型(prototype)设计基于 Iterable 。熟悉的操作 filter 、 map 等是 Iterable 上的扩展(默认)方法。调用一个向链中添加了一个操作并返回另一个 Iterable 。像 count 这样的终端操作会调用 iterator() 沿着链向上到达源，并且这些操作在每个阶段的迭代器中实现。

由于这些是可迭代对象，您可以多次调用 iterator() 方法。那应该怎么办？

如果源是一个集合，这通常可以正常工作。集合是可迭代的，每次调用 iterator() 都会产生一个独立于任何其他 Activity 实例的独特 Iterator 实例，并且每个实例都独立地遍历集合。伟大的。

现在如果源是一次性的，比如从文件中读取行怎么办？也许第一个迭代器应该得到所有的值，但第二个和后续的应该是空的。也许这些值应该在迭代器之间交错。或者也许每个迭代器都应该获得所有相同的值。那么，如果你有两个迭代器并且一个比另一个更早呢？有人将不得不缓冲第二个迭代器中的值，直到它们被读取。更糟糕的是，如果您获得一个 Iterator 并读取所有值，然后才获得第二个 Iterator，该怎么办？值(value)从何而来？是否需要将它们全部缓冲以防万一有人想要第二个迭代器？

显然，在一次性源上允许多个迭代器会引发很多问题。我们没有给他们很好的答案。如果您两次调用 iterator() 会发生什么，我们想要一致的、可预测的行为。这促使我们禁止多次遍历，使管道一次性。

我们还观察到其他人遇到了这些问题。在 JDK 中，大多数 Iterable 都是集合或类集合对象，允许多次遍历。它没有在任何地方指定，但似乎有一个不成文的期望，即 Iterables 允许多次遍历。一个值得注意的异常(exception)是 NIO DirectoryStream 接口(interface)。它的规范包括这个有趣的警告:

While DirectoryStream extends Iterable, it is not a general-purpose Iterable as it supports only a single Iterator; invoking the iterator method to obtain a second or subsequent iterator throws IllegalStateException.

【原文加粗】

这看起来很不寻常和令人不快，以至于我们不想创建一大堆可能只有一次的新 Iterable。这促使我们远离使用 Iterable。

大约在这个时候，出现了一个 article by Bruce Eckel，描述了他在使用 Scala 时遇到的问题。他写了这样的代码:

// Scala
val lines = fromString(data).getLines
val registrants = lines.map(Registrant)
registrants.foreach(println)
registrants.foreach(println)

这很简单。它将文本行解析为 Registrant 个对象并将它们打印两次。除了它实际上只打印一次。结果他认为 registrants 是一个集合，而实际上它是一个迭代器。对 foreach 的第二次调用遇到一个空迭代器，其中的所有值都已耗尽，因此它什么也不打印。

这种经验使我们确信，如果尝试多次遍历，获得清晰可预测的结果是非常重要的。它还强调了将类似惰性管道的结构与存储数据的实际集合区分开来的重要性。这反过来又插入了将惰性管道操作分离到新的 Stream 接口(interface)中，并仅在集合上直接保留急切的、可变的操作。 Brian Goetz has explained 这样做的理由。

允许对基于集合的管道进行多次遍历，但不允许对非基于集合的管道进行多次遍历呢？这是不一致的，但它是明智的。如果您正在从网络读取值，当然您不能再次遍历它们。如果您想多次遍历它们，则必须明确地将它们拉入一个集合中。

但是让我们探索允许从基于集合的管道进行多次遍历。假设你这样做了:

Iterable<?> it = source.filter(...).map(...).filter(...).map(...);
it.into(dest1);
it.into(dest2);

( into 操作现在拼写为 collect(toList()) 。)

如果源是一个集合，那么第一个 into() 调用将创建一个返回源的迭代器链，执行管道操作，并将结果发送到目标。第二次调用 into() 将创建另一个迭代器链，并再次执行管道操作 。这显然没有错，但它确实具有为每个元素第二次执行所有过滤器和映射操作的效果。我想很多程序员都会对这种行为感到惊讶。

正如我上面提到的，我们一直在与 Guava 开发人员交谈。他们拥有的一个很酷的东西是 Idea Graveyard，他们描述了他们决定 而不是 实现的功能以及原因。惰性集合的想法听起来很酷，但这是他们不得不说的。考虑一个返回 List.filter() 的 List 操作:

The biggest concern here is that too many operations become expensive, linear-time propositions. If you want to filter a list and get a list back, and not just a Collection or an Iterable, you can use ImmutableList.copyOf(Iterables.filter(list, predicate)), which "states up front" what it's doing and how expensive it is.

举一个具体的例子，列表上 get(0) 或 size() 的成本是多少？对于像 ArrayList 这样的常用类，它们是 O(1)。但是如果你在一个延迟过滤的列表上调用其中一个，它必须在支持列表上运行过滤器，突然这些操作是 O(n)。更糟糕的是，它必须在每次 操作时遍历 上的支持列表。

在我们看来，这太懒惰了。设置一些操作并将实际执行推迟到您“开始”之前是一回事。以隐藏大量重新计算的方式进行设置是另一种方式。

在提议禁止非线性或“不可重用”流时，Paul Sandoz 将允许它们的 potential consequences 描述为导致“意外或困惑的结果”。他还提到并行执行会使事情变得更加棘手。最后，我要补充一点，如果操作意外执行多次，或者至少与程序员预期的次数不同，那么带有副作用的管道操作将导致困难和模糊的错误。 (但 Java 程序员不会编写带有副作用的 lambda 表达式，是吗？他们会吗？？)

这就是 Java 8 Streams API 设计的基本原理，它允许一次性遍历并且需要严格的线性(无分支)管道。它在多个不同的流源之间提供一致的行为，它清楚地将惰性操作与急切操作区分开来，并且它提供了一个简单的执行模型。

关于 IEnumerable ，我远不是 C# 和 .NET 方面的专家，所以如果我得出任何不正确的结论，我希望得到纠正(温和地)。然而，似乎 IEnumerable 允许多次遍历对不同的源有不同的行为；它允许嵌套 IEnumerable 操作的分支结构，这可能会导致一些重要的重新计算。虽然我理解不同的系统会做出不同的权衡，但这是我们在 Java 8 Streams API 设计中试图避免的两个特征。

OP 给出的快速排序示例很有趣，令人费解，而且很抱歉，有点可怕。调用 QuickSort 需要一个 IEnumerable 并返回一个 IEnumerable ，因此在遍历最后一个 IEnumerable 之前实际上不会进行排序。然而，这个调用似乎在构建一个 IEnumerables 的树结构，它反射(reflect)了快速排序会做的分区，但实际上并没有这样做。 (毕竟这是惰性计算。)如果源有 N 个元素，则树的最宽将是 N 个元素宽，并且深度为 lg(N) 级。

在我看来 - 再一次，我不是 C# 或 .NET 专家 - 这将导致某些看起来无害的调用，例如通过 ints.First() 选择枢轴，比它们看起来更昂贵。在第一层，当然是 O(1)。但是考虑在树深处的右侧边缘的分区。要计算此分区的第一个元素，必须遍历整个源，这是一个 O(N) 操作。但是由于上面的分区是惰性的，它们必须重新计算，需要 O(lg N) 次比较。因此，选择主元将是一个 O(N lg N) 操作，这与整个排序一样昂贵。

但是在遍历返回的 IEnumerable 之前，我们实际上不会进行排序。在标准的快速排序算法中，每一级分区都会使分区数加倍。每个分区只有一半的大小，因此每个级别保持 O(N) 复杂度。分区树的高度为 O(lg N)，因此总工作量是 O(N lg N)。

对于惰性 IEnumerables 树，在树的底部有 N 个分区。计算每个分区需要遍历 N 个元素，每个元素都需要在树上进行 lg(N) 次比较。为了计算树底部的所有分区，需要 O(N^2 lg N) 次比较。

(这是对的吗？我简直不敢相信。请有人帮我检查一下。)

无论如何，以这种方式使用 IEnumerable 来构建复杂的计算结构确实很酷。但是，如果它确实像我认为的那样增加了计算复杂性，那么除非非常小心，否则似乎应该避免以这种方式编程。