为什么Java流是一次性的？

Question

对终端操作的任何调用都会关闭流，使其无法使用。这个‘特性’带走了很多权力。

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

编辑：为了演示我所讲的内容，请考虑以下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));
}

Answer 1

我对Streams API早期设计的一些回忆可能会对设计原理有所帮助。

早在2012年，我们就在该语言中添加了lambdas，我们希望使用lambdas编程的面向集合或“批量数据”的操作集，以促进并行性。懒洋洋地将操作连在一起的想法在这一点上得到了很好的确立。我们也不希望中间操作存储结果。

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

现有工作对设计有许多影响。其中比较有影响力的是Google的Guava库和Scala collections库。（如果有人对番石榴的影响感到惊讶，请注意番石榴的首席开发人员Kevin Bourrillion是JSR-335 Lambda专家组的成员。）关于Scala集合，我们发现Martin Odersky的这篇演讲特别有趣：未来可防Scala集合：从可变到持久到并行。（斯坦福EE380，2011年6月1日。）

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

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

现在，如果源代码是一次性的，就像从文件中读取行一样，怎么办？也许第一个迭代器应该获得所有的值，但是第二个和后续的迭代器应该是空的。也许这些值应该在迭代器之间交错。或者每个迭代器应该得到所有相同的值。那么，如果有两个迭代器，其中一个比另一个更早呢？有人必须在第二个迭代器中缓冲这些值，直到它们被读取为止。更糟的是，如果您获得一个迭代器并读取所有值，然后才获得第二个迭代器，那会怎么样。现在的价值观从何而来？是否需要将它们全部缓冲起来，以防有人需要第二个迭代器？

显然，允许多个迭代器访问一个一次性源代码会引发很多问题。我们没有给他们好的答案。如果您调用iterator()两次，那么我们需要一致的、可预测的行为。这促使我们不允许多次穿越，使管道一次性通过。

我们还注意到其他国家也遇到了这些问题。在JDK中，大多数迭代都是集合或类似集合的对象，它们允许多次遍历。它没有指定在任何地方，但似乎有一个不成文的期望，即迭代允许多次遍历。一个显著的例外是NIO DirectoryStream接口。它的规范包括这个有趣的警告：

[原文加粗]

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

大约在这个时候，Bruce Eckel的一篇文章出现了，描述了他在Scala上遇到的一个麻烦。他写了这样的代码：

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

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

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

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

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

这里最大的担忧是太多的操作会变成昂贵的线性时间命题。如果您希望筛选列表并返回列表，而不仅仅是集合或迭代，那么您可以使用immutableList.copyof(iterables.filter(list,predicate))，它“预先说明”它在做什么以及它的开销。

举一个具体的例子，在列表上使用get(0)或size()的代价是什么？对于像arraylist这样的常用类，它们是O(1)。但是如果在一个懒散过滤的列表上调用其中的一个，它必须在备份列表上运行过滤器，突然之间这些操作都是O(n)。更糟的是，它必须在每次操作时遍历支持列表。

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

Paul Sandoz在建议不允许非线性或“不可重用”流时描述了允许它们的潜在后果，即产生“意想不到的或令人困惑的结果”。他还提到并行执行会让事情变得更加棘手。最后，我要补充一点，如果一个带有副作用的流水线操作意外地执行了多次，或者至少执行了不同于程序员预期的次数，那么该操作将导致困难和晦涩的bug。（但是Java程序员不会写带有副作用的lambda表达式，是吗？是吗？？）

这就是Java8Streams API设计的基本原理，它允许一次性遍历，并且需要严格线性（无分支）的管道。它提供了跨多个不同流源的一致行为，它清楚地区分了lazy操作和eager操作，并且它提供了一个简单的执行模型。

关于IEnumerable，我远不是C#和.NET方面的专家，因此如果我得出了任何不正确的结论，我希望得到（温和的）纠正。但是,IEnumerable似乎允许多次遍历以不同的方式处理不同的源；并且它允许嵌套的IEnumerable操作的分支结构，这可能导致一些重大的重新计算。虽然我知道不同的系统会做出不同的权衡，但这是我们在设计Java8Streams API时试图避免的两个特性。

OP给出的quicksort示例很有趣，令人费解，很抱歉，有点恐怖。调用quicksort将使用IEnumerable并返回IEnumerable，因此在遍历最后的IEnumerable之前，实际上不会进行排序。但是，该调用所做的似乎是构建IEnumerables的树结构，该结构反映了quicksort将要进行的分区，而实际上并没有进行分区。（这毕竟是懒惰的计算。）如果源有N个元素，那么树的最宽处将有N个元素宽，并且它将有lg(N)级深。

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

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

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

（这是对的吗？我简直不敢相信。谁来帮我查一下这个。）