LINQ为什么"Enumerable = Enumerable.Skip(N)“很慢？

Question

我对LINQ查询的性能有一个问题，所以我创建了一个小的简化示例来演示下面的问题。该代码获取一个随机的小整数列表，并返回划分为几个较小列表的列表，每个列表的总数不超过10。

问题是(正如我写这篇文章时)，使用N的代码会花费指数级更长的时间，这只是一个O(N)问题。使用N=2500，代码在我的pc上运行需要10秒以上。

如果有人能解释一下发生了什么，我会很高兴的。谢谢，马克。

int N = 250;
Random r = new Random();
var work = Enumerable.Range(1,N).Select(x => r.Next(0, 6)).ToList();
var chunks = new List<List<int>>();

// work.Dump("All the work.");  // LINQPad Print
var workEnumerable = work.AsEnumerable();

Stopwatch sw = Stopwatch.StartNew();
while(workEnumerable.Any())  // or .FirstorDefault() != null
{
    int soFar = 0;
    var chunk = workEnumerable.TakeWhile( x => 
                          {
                              soFar += x;               
                              return  (soFar <= 10);
                          }).ToList();
    chunks.Add(chunk);          // Commented out makes no difference.
    workEnumerable = workEnumerable.Skip(chunk.Count); // <== SUSPECT
}
sw.Stop();

// chunks.Dump("Work Chunks.");   // LINQPad Print
sw.Elapsed.Dump("Time elapsed.");

Answer 1

.Skip()所做的是创建一个循环遍历源代码的新IEnumerable，并且只在第一个N元素之后才开始产生结果。你的链条，谁知道有多少这样的人在彼此之后。每次调用.Any()时，都需要再次循环遍历所有先前跳过的元素。

一般来说，在LINQ中设置非常复杂的运算符链并重复枚举它们是一个坏主意。此外，由于LINQ是一个查询API，当您试图实现的操作相当于修改数据结构时，像Skip()这样的方法不是一个好的选择。

Answer 2

您可以有效地将Skip()链接到同一个enumerable。在一个250个的列表中，最后一个块将从前面有大约25个'Skip‘枚举器类的惰性可枚举器创建。

如果你这样做了，你会发现事情变得更快了

workEnumerable = workEnumerable.Skip(chunk.Count).ToList();

然而，我认为整个方法都可以改变。

如何使用标准LINQ来实现相同的功能：

在上观看现场直播

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    private readonly static Random r = new Random();

    public static void Main(string[] args)
    {
        int N = 250;
        var work = Enumerable.Range(1,N).Select(x => r.Next(0, 6)).ToList();

        var chunks = work.Select((o,i) => new { Index=i, Obj=o })
            .GroupBy(e => e.Index / 10)
            .Select(group => group.Select(e => e.Obj).ToList())
            .ToList();

        foreach(var chunk in chunks)
            Console.WriteLine("Chunk: {0}", string.Join(", ", chunk.Select(i => i.ToString()).ToArray()));
    }
}

Answer 3

Skip()方法和其他类似方法基本上创建了一个实现IEnumerable的占位符对象，该对象引用其父enumerable并包含执行跳过的逻辑。因此，循环中的跳过是无效的，因为它们添加了一层新的逻辑层，当您实际需要跳过的所有元素之后的第一个元素时，就会延迟执行，而不是像您认为的那样丢弃可枚举的元素。

您可以通过调用ToList()或ToArray()来解决此问题。这会强制对Skip()方法进行“急切”求值，并且确实会删除要枚举的新集合中跳过的元素。这会增加内存开销，并要求所有元素都是已知的(因此，如果您在表示无穷级数的IEnumerable上运行此程序，祝您好运)。

第二种选择是不使用Linq，而是使用IEnumerable实现本身来获取和控制IEnumerator。然后，只需调用MoveNext()必要的次数，而不是Skip()。