我有一些关于Streams API早期设计的回忆，可能会对设计原理有所启发。
早在2012年，我们将lambdas添加到语言中，我们想要一个面向集合或“批量数据”的操作集，使用lambdas编程，这将促进并行性。在这一点上，懒惰地将操作链接在一起的想法已经很好地确立了。我们也不希望中间操作存储结果。
我们需要确定的主要问题是API中链中的对象是什么样子的，以及它们如何连接到数据源。源通常是集合，但我们也希望支持来自文件或网络的数据，或动态生成的数据，例如，来自随机数生成器。
现有的工作对设计有很多影响。其中更有影响力的是谷歌的Guava库和Scala collections库。(如果有人对Guava的影响感到惊讶，请注意Guava的首席开发人员Kevin Bourrillion是JSR-335 Lambda专家组的成员。)关于Scala集合，我们发现Martin Odersky的演讲特别有趣:面向未来的Scala集合:从可变到持久再到并行。(斯坦福EE380, 2011年6月1日。)
我们当时的原型设计是基于Iterable。熟悉的操作过滤器、映射等等都是Iterable上的扩展(默认)方法。调用一个Iterable会向链中添加一个操作，并返回另一个Iterable。像count这样的终端操作将沿着链向上调用iterator()直到源，并且这些操作在每个阶段的iterator中实现。
因为这些都是Iterables，所以可以多次调用iterator()方法。那么会发生什么呢?
如果源是一个集合，这在大多数情况下工作正常。集合是可迭代的，每次调用iterator()都会产生一个独立于任何其他活动实例的iterator实例，并且每次调用都独立地遍历集合。太好了。
Now what if the source is one-shot, like reading lines from a file? Maybe the first Iterator should get all the values but the second and subsequent ones should be empty. Maybe the values should be interleaved among the Iterators. Or maybe each Iterator should get all the same values. Then, what if you have two iterators and one gets farther ahead of the other? Somebody will have to buffer up the values in the second Iterator until they're read. Worse, what if you get one Iterator and read all the values, and only then get a second Iterator. Where do the values come from now? Is there a requirement for them all to be buffered up just in case somebody wants a second Iterator?
显然，在一个一次性源上允许多个迭代器会引发很多问题。我们没有很好的答案。对于两次调用iterator()所发生的情况，我们希望有一致的、可预测的行为。这促使我们禁止多次遍历，使管道成为一次性的。
我们还观察到其他人也遇到了这些问题。在JDK中，大多数Iterables是集合或类似集合的对象，它们允许多次遍历。它没有在任何地方指定，但似乎有一个不成文的期望，即Iterables允许多次遍历。一个明显的例外是NIO DirectoryStream接口。它的规范包括这个有趣的警告:
虽然DirectoryStream扩展了Iterable，但它不是一个通用的Iterable，因为它只支持一个迭代器;调用迭代器方法来获取第二个或后续迭代器会抛出IllegalStateException异常。
[原文加粗]
这看起来很不寻常，也很令人不愉快，以至于我们不想创建一大堆可能只有一次的新Iterables。这使得我们不再使用Iterable。
大约在这个时候，Bruce Eckel发表了一篇文章，描述了他在使用Scala时遇到的一些问题。他写了这样的代码:
// Scala
val lines = fromString(data).getLines
val registrants = lines.map(Registrant)
registrants.foreach(println)
registrants.foreach(println)
这很简单。它将文本行解析为Registrant对象，并将它们打印两次。只不过它实际上只打印一次。结果他认为registrants是一个集合，而实际上它是一个迭代器。对foreach的第二次调用遇到一个空迭代器，其中所有值都已耗尽，因此它什么也不打印。
这种经验使我们相信，如果尝试多次遍历，那么获得清晰可预测的结果是非常重要的。它还强调了区分惰性管道式结构与存储数据的实际集合的重要性。这反过来推动了将惰性管道操作分离到新的Stream接口中，并直接在Collections上只保留急切的、可变的操作。Brian Goetz解释了其中的基本原理。
如果允许对基于集合的管道进行多次遍历，而不允许对非基于集合的管道进行多次遍历，会怎么样呢?这是不一致的，但它是合理的。如果从网络读取值，当然不能再次遍历它们。如果要多次遍历它们，则必须显式地将它们拉入一个集合。
但是让我们探索一下允许从基于集合的管道进行多次遍历。假设你是这样做的:
Iterable<?> it = source.filter(...).map(...).filter(...).map(...);
it.into(dest1);
it.into(dest2);
into操作现在拼写为collect(toList())。
如果source是一个集合，那么第一个into()调用将创建一个返回到源的iterator链，执行管道操作，并将结果发送到目标。对into()的第二次调用将创建另一个迭代器链，并再次执行管道操作。这显然不是错误的，但它确实会对每个元素执行第二次所有筛选和映射操作。我认为许多程序员会对这种行为感到惊讶。
正如我上面提到的，我们一直在与Guava开发者进行交流。他们有一个很酷的东西是Idea Graveyard，在那里他们描述了他们决定不实现的功能以及原因。惰性集合的想法听起来很酷，但下面是他们对它的看法。考虑一个返回List的List.filter()操作:
这里最大的问题是太多的操作会变成昂贵的线性时间命题。如果你想过滤一个列表并返回一个列表，而不仅仅是一个Collection或Iterable，你可以使用immutabllist . copyof (Iterables. copyof)。Filter (list, predicate))，它“预先声明”它正在做什么以及它的开销是多少。
举个具体的例子，get(0)或size()在List上的代价是多少?对于像ArrayList这样常用的类，它们是O(1)。但如果你在一个惰性过滤的列表中调用其中的一个，它必须在支持列表上运行过滤器，突然这些操作都是O(n)。更糟糕的是，它必须在每个操作上遍历备份列表。
在我们看来，这太懒惰了。设置一些操作并推迟实际执行直到你“开始”是一回事。另一种方法是隐藏大量的重新计算。
In proposing to disallow non-linear or "no-reuse" streams, Paul Sandoz described the potential consequences of allowing them as giving rise to "unexpected or confusing results." He also mentioned that parallel execution would make things even trickier. Finally, I'd add that a pipeline operation with side effects would lead to difficult and obscure bugs if the operation were unexpectedly executed multiple times, or at least a different number of times than the programmer expected. (But Java programmers don't write lambda expressions with side effects, do they? DO THEY??)
这就是Java 8 Streams API设计的基本原理，它允许一次遍历，并且需要一个严格的线性(无分支)管道。它提供了跨多个不同流源的一致行为，它清晰地将惰性操作与急切操作区分开来，并且它提供了一个简单的执行模型。
With regard to IEnumerable, I am far from an expert on C# and .NET, so I would appreciate being corrected (gently) if I draw any incorrect conclusions. It does appear, however, that IEnumerable permits multiple traversal to behave differently with different sources; and it permits a branching structure of nested IEnumerable operations, which may result in some significant recomputation. While I appreciate that different systems make different tradeoffs, these are two characteristics that we sought to avoid in the design of the Java 8 Streams API.
The quicksort example given by the OP is interesting, puzzling, and I'm sorry to say, somewhat horrifying. Calling QuickSort takes an IEnumerable and returns an IEnumerable, so no sorting is actually done until the final IEnumerable is traversed. What the call seems to do, though, is build up a tree structure of IEnumerables that reflects the partitioning that quicksort would do, without actually doing it. (This is lazy computation, after all.) If the source has N elements, the tree will be N elements wide at its widest, and it will be lg(N) levels deep.
It seems to me -- and once again, I'm not a C# or .NET expert -- that this will cause certain innocuous-looking calls, such as pivot selection via ints.First(), to be more expensive than they look. At the first level, of course, it's O(1). But consider a partition deep in the tree, at the right-hand edge. To compute the first element of this partition, the entire source has to be traversed, an O(N) operation. But since the partitions above are lazy, they must be recomputed, requiring O(lg N) comparisons. So selecting the pivot would be an O(N lg N) operation, which is as expensive as an entire sort.
但是直到遍历返回的IEnumerable，我们才真正进行排序。在标准的快速排序算法中，每一级分区都使分区的数量翻倍。每个分区只有一半大小，因此每个级别的复杂度保持在O(N)。分区树的高度是O(lgn)所以总的功是O(nlgn)
对于惰性IEnumerables树，树的底部有N个分区。计算每个分区需要遍历N个元素，每一个都需要lg(N)次比较。为了计算树底部的所有分区，需要O(N^2 lgn)次比较。
(对吗?我简直不敢相信。谁来帮我检查一下。)
在任何情况下，IEnumerable可以通过这种方式来构建复杂的计算结构，这确实很酷。但是如果它确实像我认为的那样增加了计算的复杂性，那么这种编程方式似乎是应该避免的，除非你非常小心。
