背景

虽然这个问题看起来很简单，但实际的答案需要一些背景知识才能理解。如果你想跳到结论，向下滚动…

选择你的比较点-基本功能

使用基本概念，c#的IEnumerable概念与Java的Iterable更接近，后者可以创建任意数量的迭代器。IEnumerables创建ienumerator。Java的Iterable创建迭代器

这两个概念的历史是相似的，因为IEnumerable和Iterable都有一个基本动机，即允许在数据集合的成员上进行“for-each”风格的循环。这是一种过度简化，因为他们都允许更多的东西，而且他们也是通过不同的进程到达这个阶段的，但无论如何这是一个重要的共同特征。

让我们比较一下这个特性:在两种语言中，如果一个类实现了IEnumerable/Iterable，那么这个类必须至少实现一个方法(对于c#，它是GetEnumerator，对于Java，它是iterator())。在每种情况下，返回的实例(IEnumerator/Iterator)允许您访问数据的当前成员和后续成员。该特性用于for-each语言语法。

选择您的比较点-增强功能

c#中的IEnumerable已经被扩展到允许许多其他语言特性(主要与Linq相关)。添加的功能包括选择、投影、聚合等。这些扩展在集合论中有很强的使用动机，类似于SQL和关系数据库的概念。

Java 8还增加了一些功能，可以使用Streams和Lambdas进行一定程度的函数式编程。注意，Java 8流主要不是由集合论驱动的，而是由函数式编程驱动的。无论如何，两者有很多相似之处。

这是第二点。对c#的增强是作为对IEnumerable概念的增强来实现的。然而，在Java中，所做的增强是通过创建Lambdas和Streams的新基本概念来实现的，然后还创建了一种相对简单的方法来从迭代器和可迭代对象转换为Streams，反之亦然。

因此，比较IEnumerable和Java的Stream概念是不完整的。您需要将其与Java中的组合流和集合API进行比较。

在Java中，流与可迭代对象或迭代器不同

流不像迭代器那样被设计来解决问题:

迭代器是一种描述数据序列的方法。 流是描述数据转换序列的一种方式。

使用Iterator，您可以获得一个数据值，处理它，然后获得另一个数据值。

使用Streams，您将一个函数序列链接在一起，然后向流提供一个输入值，并从组合的序列获得输出值。注意，在Java术语中，每个函数都封装在一个Stream实例中。Streams API允许您以链接转换表达式序列的方式链接Stream实例序列。

为了完成流的概念，您需要一个数据源来提供流，以及一个使用流的终端函数。

你向流中提供值的方式实际上可能来自一个Iterable，但流序列本身不是一个Iterable，它是一个复合函数。

流也被认为是懒惰的，在某种意义上，它只在你向它请求一个值时才工作。

请注意Streams的这些重要假设和特性:

A Stream in Java is a transformation engine, it transforms a data item in one state, to being in another state. streams have no concept of the data order or position, the simply transform whatever they are asked to. streams can be supplied with data from many sources, including other streams, Iterators, Iterables, Collections, you cannot "reset" a stream, that would be like "reprogramming the transformation". Resetting the data source is probably what you want. there is logically only 1 data item 'in flight' in the stream at any time (unless the stream is a parallel stream, at which point, there is 1 item per thread). This is independent of the data source which may have more than the current items 'ready' to be supplied to the stream, or the stream collector which may need to aggregate and reduce multiple values. Streams can be unbound (infinite), limited only by the data source, or collector (which can be infinite too). Streams are 'chainable', the output of filtering one stream, is another stream. Values input to and transformed by a stream can in turn be supplied to another stream which does a different transformation. The data, in its transformed state flows from one stream to the next. You do not need to intervene and pull the data from one stream and plug it in to the next.

c#的比较

当您认为Java流只是供应、流和收集系统的一部分，并且流和迭代器经常与集合一起使用时，那么就难怪很难将几乎全部嵌入到c#中的单个IEnumerable概念中的相同概念联系起来。

IEnumerable的某些部分(以及密切相关的概念)在所有Java Iterator、Iterable、Lambda和Stream概念中都很明显。

Java概念可以做的一些小事情在IEnumerable中比较困难，反之亦然。

---

结论

这里没有设计问题，只是语言之间的概念匹配问题。 流以不同的方式解决问题 流为Java添加了功能(它们添加了一种不同的做事方式，而不是将功能带走)

添加流可以让你在解决问题时有更多选择，这可以被公平地归类为“增强力量”，而不是“减少”、“带走”或“限制”。

为什么Java流是一次性的?

这个问题是错误的，因为流是函数序列，而不是数据。根据提供流的数据源，您可以重置数据源，并提供相同或不同的流。

不像c#的IEnumerable，一个执行管道可以被我们想执行多少次就执行多少次，在Java中一个流只能被“迭代”一次。

比较IEnumerable和Stream是错误的。你用来说明IEnumerable可以被你想执行多少次就可以执行多少次的上下文，与Java Iterables相比是最好的，后者可以被你想迭代多少次。Java流代表IEnumerable概念的子集，而不是提供数据的子集，因此不能“重新运行”。

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

从某种意义上说，第一个说法是正确的。“剥夺权力”的说法则不然。你仍然在比较Streams和IEnumerables。流中的终端操作类似于for循环中的“break”子句。如果您愿意，并且可以重新提供所需的数据，您总是可以自由地拥有另一个流。同样，如果你认为IEnumerable更像一个Iterable，对于这条语句，Java做得很好。

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

原因是技术上的，原因很简单，流是思想的子集。流子集不控制数据供应，因此您应该重置供应，而不是流。在这种情况下，这并不奇怪。

快速排序的例子

您的快速排序示例具有签名:

IEnumerable<int> QuickSort(IEnumerable<int> ints)

你将输入IEnumerable作为数据源:

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

此外，返回值也是IEnumerable，这是一个数据供应，由于这是一个Sort操作，该供应的顺序很重要。如果你认为Java Iterable类是合适的匹配，特别是Iterable的List专门化，因为List是一个有保证顺序或迭代的数据供应，那么与你的代码等效的Java代码将是:

Stream<Integer> quickSort(List<Integer> ints) {
    // Using a stream to access the data, instead of the simpler ints.isEmpty()
    if (!ints.stream().findAny().isPresent()) {
        return Stream.of();
    }

    // treating the ints as a data collection, just like the C#
    final Integer pivot = ints.get(0);

    // Using streams to get the two partitions
    List<Integer> lt = ints.stream().filter(i -> i < pivot).collect(Collectors.toList());
    List<Integer> gt = ints.stream().filter(i -> i > pivot).collect(Collectors.toList());

    return Stream.concat(Stream.concat(quickSort(lt), Stream.of(pivot)),quickSort(gt));
}    

注意有一个错误(我已经复制)，在排序不处理重复值优雅，这是一个'唯一值'排序。

还要注意Java代码是如何在不同的地方使用数据源(List)和流概念的，而在c#中，这两种“个性”可以用IEnumerable来表示。此外，虽然我已经使用List作为基类型，但我可以使用更通用的Collection，并且通过一个小的迭代器到流的转换，我可以使用更通用的Iterable

我认为当你仔细观察时，两者之间几乎没有什么区别。

从表面上看，IEnumerable确实是一个可重用的结构:

IEnumerable<int> numbers = new int[] { 1, 2, 3, 4, 5 };

foreach (var n in numbers) {
    Console.WriteLine(n);
}

然而，编译器实际上做了一些工作来帮助我们;它生成以下代码:

IEnumerable<int> numbers = new int[] { 1, 2, 3, 4, 5 };

IEnumerator<int> enumerator = numbers.GetEnumerator();
while (enumerator.MoveNext()) {
    Console.WriteLine(enumerator.Current);
}

每次迭代枚举对象时，编译器都会创建一个枚举对象。枚举数不可重用;进一步调用MoveNext将返回false，并且没有办法将其重置到开始。如果希望再次遍历这些数字，则需要创建另一个枚举器实例。

---

为了更好地说明IEnumerable具有(可以具有)与Java流相同的“特性”，可以考虑一个数字源不是静态集合的enumerable。例如，我们可以创建一个可枚举对象，它生成一个由5个随机数组成的序列:

class Generator : IEnumerator<int> {
    Random _r;
    int _current;
    int _count = 0;

    public Generator(Random r) {
        _r = r;
    }

    public bool MoveNext() {
        _current= _r.Next();
        _count++;
        return _count <= 5;
    }

    public int Current {
        get { return _current; }
    }
 }

class RandomNumberStream : IEnumerable<int> {
    Random _r = new Random();
    public IEnumerator<int> GetEnumerator() {
        return new Generator(_r);
    }
    public IEnumerator IEnumerable.GetEnumerator() {
        return this.GetEnumerator();
    }
}

现在我们有了与之前基于数组的enumerable非常相似的代码，但是对数字进行了第二次迭代:

IEnumerable<int> numbers = new RandomNumberStream();

foreach (var n in numbers) {
    Console.WriteLine(n);
}
foreach (var n in numbers) {
    Console.WriteLine(n);
}

第二次对数字进行迭代时，我们将得到一个不同的数字序列，这在同一意义上不是可重用的。或者，我们可以编写RandomNumberStream来抛出一个异常，如果您尝试多次遍历它，使可枚举对象实际上不可用(就像Java流)。

同样，当应用于RandomNumberStream时，基于枚举的快速排序意味着什么?

---

结论

因此，最大的区别是。net允许你在需要访问序列中的元素时在后台隐式地创建一个新的IEnumerator来重用IEnumerable。

这种隐式行为通常是有用的(正如你所说的“强大”)，因为我们可以重复迭代一个集合。

但有时，这种内隐行为实际上会导致问题。如果你的数据源不是静态的，或者访问成本很高(比如数据库或网站)，那么很多关于IEnumerable的假设必须被丢弃;重用并不是那么简单

流是围绕spliterator构建的，spliterator是有状态的、可变的对象。它们没有“重置”操作，事实上，要求支持这样的倒带操作会“消耗很多能量”。random .int()应该如何处理这样的请求?

另一方面，对于具有可追溯起源的流，很容易构造一个等价的流来再次使用。只需将构造Stream的步骤放到可重用方法中。请记住，重复这些步骤并不是一个昂贵的操作，因为所有这些步骤都是惰性操作;实际的工作从终端操作开始，根据实际的终端操作，可能会执行完全不同的代码。

这将由这种方法的作者来指定两次调用该方法意味着什么:它是否会像为未修改的数组或集合创建的流那样完全复制相同的序列，或者它是否会生成具有类似语义但元素不同的流，例如随机整数流或控制台输入行流，等等。

---

顺便说一下，为了避免混淆，终端操作消耗的是流，而不是像在流上调用close()那样关闭流(这对于具有关联资源的流来说是必需的，例如由Files.lines()产生)。

---

It seems that a lot of confusion stems from misguiding comparison of IEnumerable with Stream. An IEnumerable represents the ability to provide an actual IEnumerator, so its like an Iterable in Java. In contrast, a Stream is a kind of iterator and comparable to an IEnumerator so it’s wrong to claim that this kind of data type can be used multiple times in .NET, the support for IEnumerator.Reset is optional. The examples discussed here rather use the fact that an IEnumerable can be used to fetch new IEnumerators and that works with Java’s Collections as well; you can get a new Stream. If the Java developers decided to add the Stream operations to Iterable directly, with intermediate operations returning another Iterable, it was really comparable and it could work the same way.

However, the developers decided against it and the decision is discussed in this question. The biggest point is the confusion about eager Collection operations and lazy Stream operations. By looking at the .NET API, I (yes, personally) find it justified. While it looks reasonable looking at IEnumerable alone, a particular Collection will have lots of methods manipulating the Collection directly and lots of methods returning a lazy IEnumerable, while the particular nature of a method isn’t always intuitively recognizable. The worst example I found (within the few minutes I looked at it) is List.Reverse() whose name matches exactly the name of the inherited (is this the right terminus for extension methods?) Enumerable.Reverse() while having an entirely contradicting behavior.

---

当然，这是两个截然不同的决定。第一个是使Stream成为一种不同于Iterable/Collection的类型，第二个是使Stream成为一种一次性迭代器而不是另一种迭代器。但这些决定是一起做出的，可能从来没有考虑过把这两个决定分开。它在创建时并没有考虑到与. net的可比性。

实际的API设计决策是添加一种改进的迭代器类型，即Spliterator。分离器可以由旧的Iterables提供(这是它们被改造的方式)，也可以由全新的实现提供。然后，Stream作为高级前端添加到相当低级的Spliterators中。就是这样。你可能会讨论不同的设计是否会更好，但这并没有什么成效，考虑到它们现在的设计方式，它不会改变。

There is another implementation aspect you have to consider. Streams are not immutable data structures. Each intermediate operation may return a new Stream instance encapsulating the old one but it may also manipulate its own instance instead and return itself (that doesn’t preclude doing even both for the same operation). Commonly known examples are operations like parallel or unordered which do not add another step but manipulate the entire pipeline). Having such a mutable data structure and attempts to reuse (or even worse, using it multiple times at the same time) doesn’t play well…

---

为了完整起见，下面是翻译成Java流API的快速排序示例。这表明它并没有真正“带走太多的能量”。

static Stream<Integer> quickSort(Supplier<Stream<Integer>> ints) {

  final Optional<Integer> optPivot = ints.get().findAny();
  if(!optPivot.isPresent()) return Stream.empty();

  final int pivot = optPivot.get();

  Supplier<Stream<Integer>> lt = ()->ints.get().filter(i -> i < pivot);
  Supplier<Stream<Integer>> gt = ()->ints.get().filter(i -> i > pivot);

  return Stream.of(quickSort(lt), Stream.of(pivot), quickSort(gt)).flatMap(s->s);
}

它可以像这样使用

List<Integer> l=new Random().ints(100, 0, 1000).boxed().collect(Collectors.toList());
System.out.println(l);
System.out.println(quickSort(l::stream)
    .map(Object::toString).collect(Collectors.joining(", ")));

你可以把它写得更紧凑

static Stream<Integer> quickSort(Supplier<Stream<Integer>> ints) {
    return ints.get().findAny().map(pivot ->
         Stream.of(
                   quickSort(()->ints.get().filter(i -> i < pivot)),
                   Stream.of(pivot),
                   quickSort(()->ints.get().filter(i -> i > pivot)))
        .flatMap(s->s)).orElse(Stream.empty());
}

The reason is that you can create streams from things that can only be used once by definition, such as an Iterator or a BufferedReader. You can think of a Stream as being consumed the same way as having used a BufferedReader to read a text file to its end. Once you reach the end of the file, the BufferedReader doesn't stop existing, but it just become useless as you can't get anything out of it anymore. If you want to read the file again, you have to create a new reader. The same goes for streams. If you want to process the source of the stream twice, you have to create two separate streams.

它可以绕过流API中的一些“运行一次”保护;例如，我们可以通过引用和重用Spliterator(而不是直接使用stream)来避免java.lang.IllegalStateException异常(带有“流已经被操作或关闭”的消息)。

例如，这段代码将运行而不抛出异常:

    Spliterator<String> split = Stream.of("hello","world")
                                      .map(s->"prefix-"+s)
                                      .spliterator();

    Stream<String> replayable1 = StreamSupport.stream(split,false);
    Stream<String> replayable2 = StreamSupport.stream(split,false);


    replayable1.forEach(System.out::println);
    replayable2.forEach(System.out::println);

然而，输出将限于

prefix-hello
prefix-world

而不是重复输出两次。这是因为用作Stream源的ArraySpliterator是有状态的，并且存储了它的当前位置。当我们重放这个流时，我们会在最后重新开始。

我们有许多选择来解决这一挑战:

We could make use of a stateless Stream creation method such as Stream#generate(). We would have to manage state externally in our own code and reset between Stream "replays": Spliterator<String> split = Stream.generate(this::nextValue) .map(s->"prefix-"+s) .spliterator(); Stream<String> replayable1 = StreamSupport.stream(split,false); Stream<String> replayable2 = StreamSupport.stream(split,false); replayable1.forEach(System.out::println); this.resetCounter(); replayable2.forEach(System.out::println); Another (slightly better but not perfect) solution to this is to write our own ArraySpliterator (or similar Stream source) that includes some capacity to reset the current counter. If we were to use it to generate the Stream we could potentially replay them successfully. MyArraySpliterator<String> arraySplit = new MyArraySpliterator("hello","world"); Spliterator<String> split = StreamSupport.stream(arraySplit,false) .map(s->"prefix-"+s) .spliterator(); Stream<String> replayable1 = StreamSupport.stream(split,false); Stream<String> replayable2 = StreamSupport.stream(split,false); replayable1.forEach(System.out::println); arraySplit.reset(); replayable2.forEach(System.out::println); The best solution to this problem (in my opinion) is to make a new copy of any stateful Spliterators used in the Stream pipeline when new operators are invoked on the Stream. This is more complex and involved to implement, but if you don't mind using third party libraries, cyclops-react has a Stream implementation that does exactly this. (Disclosure: I am the lead developer for this project.) Stream<String> replayableStream = ReactiveSeq.of("hello","world") .map(s->"prefix-"+s); replayableStream.forEach(System.out::println); replayableStream.forEach(System.out::println);

这将打印

prefix-hello
prefix-world
prefix-hello
prefix-world

像预期的那样。

我有一些关于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可以通过这种方式来构建复杂的计算结构，这确实很酷。但是如果它确实像我认为的那样增加了计算的复杂性，那么这种编程方式似乎是应该避免的，除非你非常小心。