LINQ-to-objects 中的 Enumerable.Where 是否保留顺序？

Question

var source = new List<string> { "A1", "A2", "B1", "B2" };
var filtered = source.Where(s => s.StartsWith("A"));

foreach (var s in filtered)
    Console.WriteLine(s);    // outputs first A1 and then A2

它似乎像Enumerable.Where 在有序 IEnumerable（例如 List 或 T[]）上使用时保留元素的原始顺序。情况总是如此吗？如果是，这在哪里记录？

Answer 1

Microsoft 实际上记录了 LINQ to Objects 保留顺序。该文件
http://msdn.microsoft.com/ en-us/library/dd460677%28v=vs.110%29.aspx 说

在 PLINQ 中，目标是在保持性能的同时最大化性能
正确性。查询应该尽可能快地运行，但仍会产生结果
正确的结果。在某些情况下，正确性需要以下顺序
要保留的源序列；但是，订购可以是
计算成本昂贵。因此，默认情况下，PLINQ 不会
保留源序列的顺序。对此，PLINQ
类似于 LINQ to SQL，但不同于 LINQ to Objects，后者
保留顺序。

正如 这篇 stackoverflow 文章 中提到的一些 LINQ 方法的 Microsoft 文档他们不维护秩序。例如，distinct 文档 提到此方法返回一个 无序序列。

Answer 2

使用 Enumerable.Where 方法保留顺序。

SO 上也提出了类似的问题，第一个答案详细说明了哪些方法保留顺序：

Preserving order with LINQ

Answer 3

Enumerable.Where 将保留 IEnumerable 的顺序。这没有记录，因此不能保证，但是，实现只是按顺序迭代 IEnumerable - 实际上，保留顺序 - 尽管该顺序依赖于底层 IEnumerable< 。 T> 的顺序。 （例如，Where on a HashSet不是有序的，但这是因为 HashSet 的可枚举性是无序的。）

但是，它确实包括处理某些类型（例如数组和 List）的特殊实现，因此在未来的某个时刻，特定的集合类型可能会返回如果这被认为是速度/性能/等方面的有价值的改进，则会导致不同的顺序。该文档从未明确给出订购保证。

Answer 4

Where 实现本质上如下，添加了一些额外的变量检查：

public static IEnumerable<T> Where(this IEnumerable<T> source, Funct<T, bool> predicate)
{
   foreach (T item in source)
       if (predicate(item))
           yield return item;
}

因此，假设yield 不是异步或并行完成的，它将保留顺序。如果您的源是 .AsParallel，则所有的赌注都取决于顺序。

Answer 5

这没有记录。 LINQ 运算符的文档在很多方面都严重缺乏，包括何时何地不保留顺序、何时何地不缓冲操作，或者复杂性保证是什么。

在这种情况下，我不介意依赖实现来保持顺序，因为这就是所有实际实现都会做的事情。

我建议阅读 Edulinq Jon Skeet 的系列文章，在实现功能之前，他解释了操作员应该做什么以及不应该做什么。

Answer 6

LINQ 的反编译如下：

private static IEnumerable<TSource> WhereIterator<TSource>(IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
{
    int num = -1;
    IEnumerator<TSource> getenumerator = source.GetEnumerator();
    while (getenumerator.MoveNext())
    {
        TSource current = getenumerator.Current;
        num++;
        if (predicate(current, num))
        {
            yield return current;
        }
    }
}

System.Collections.Generic.List.MoveNext() 的反编译有代码：

if (this.version == ts._version && this.index < ts._size)
{
    this.current = ts._items[this.index];
    this.index = this.index + 1;
    return true;
}

将这两者结合使用，您可以看到顺序将被保留。当然微软将来可能会改变它，但是基于.NET 4.0，List.Where将是有序的。

Answer 7

看起来它必须保持顺序，因为它能够在无限的 IEnumerable 上运行。

void Main() {
    foreach (var element in Count().Where (i => i%2 == 1)) {
        // do something with all odd numbers
    }
}

IEnumerable<int> Count() {
    int i = 0;
    while (true) yield return ++i;
}

但我在任何地方都找不到这个记录。

Answer 8

是的，它将根据迭代器进行排序。由于这不是 PLINQ，因此可枚举项按照可枚举项的元素位置顺序进行迭代 - 因此，如果您为类实现了某种自定义 IEnumerator，它将按该顺序返回。

Answer 9

Enumerable.Where 遵循通过在基础集合上调用 GetEnumerator 生成的枚举器返回的元素的顺序 - 查看 MSDN List 上的枚举器已记录为遵循索引 行为。

Answer 10

如果不提供显式的 OrderBy，Where 方法就无法保证顺序 - 否则，它会被记录为这样做的。