关于高效使用 LINQ 扩展方法的注意事项

Matt T Heffron

4.98/5 (34投票s)

2014年6月2日

CPOL

12分钟阅读

33034

202

除非您仔细处理，否则 IEnumerable 上的 LINQ 扩展方法可能会导致实现效率低下

下载源代码: EfficientUseOfLinqExtMethods.zip - 9.4 KB

引言

LINQ 提供的 IEnumerable<T> 上的扩展方法可以使序列或集合上的某些操作的实现变得相当简单。但是，如果您不小心，实现可能会非常低效。我见过一些关于实现各种操作的技巧和文章，它们看起来很巧妙，但隐藏了重大的低效率。

尽管我在本文中使用 C#，但这些问题和考虑因素适用于所有 .NET 语言。

背景

System.Linq.Enumerable 类提供了许多作用于实现 IEnumerable<T> 的枚举的扩展方法，以支持 LINQ to Objects。这些扩展方法也可以直接使用。其中许多方法会返回新的枚举。

例如，Where() 方法将源枚举的元素过滤到一个新的枚举中。

        int[] numbers = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        IEnumerable<int> odds = numbers.Where(n => (n & 1) == 1);
        foreach (int o in odds)
          Console.WriteLine(o.ToString());

此时，odds 是一个提供

但是，如果我们更改 numbers 数组中的一个值并再次打印枚举的元素，

        int[] numbers = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        IEnumerable<int> odds = numbers.Where(n => (n & 1) == 1);
        foreach (int o in odds)
          Console.WriteLine(o.ToString());
        numbers[0] = 21;
        foreach (int o in odds)
          Console.WriteLine(o.ToString());

第二次遍历时，odds 枚举器提供

Where() 方法 **不** 返回一个其值基于 `Where()` 方法执行时 numbers 数组内容的枚举。该枚举的操作是 **惰性** 的，因为它实际上 *不* 进行过滤。相反，它返回一个类的实例，该类将在程序实际迭代枚举时 *执行* 过滤。这种惰性评估是容易被误导导致重大低效率的地方。

简单使我们走上歧途

所以现在我将转向导致我思考整个问题的简单问题。问题是将一个枚举分区（分块）为一系列较小的枚举（块），每个块的最大长度为某个值。其直接实现（作为泛型扩展方法本身）是

    public static IEnumerable<IEnumerable<T>> Chunkify0<T>(this IEnumerable<T> source, 
                                                           int chunkSize)
    {
      while (source.Any())
      {
        yield return source.Take(chunkSize);
        source = source.Skip(chunkSize);
      }
    }

这只是一个循环，检查 source 枚举是否还有元素。如果有，则 yield return 枚举，该枚举是 source 的前 chunkSize 个元素，然后将 source 替换为跳过自身前 chunkSize 个元素的枚举。然后它会检查 *新* 的 source 枚举是否还有元素。

那么它是如何工作的呢？如果我们有一个包含 12 个元素的枚举，并使用 chunkSize 为 3 调用它，然后我们对返回的 4 个长度为 3 的 IEnumerable<T> 中的每一个迭代一次，那么我们期望每个元素会被 *触碰*（调用 .MoveNext()）两次，总的触碰次数大约为 24。但是，总的触碰次数是 65。如果起始枚举有 13 个元素，那么而不是大约 26 次触碰，总次数是 93！

旁注：如何计算 MoveNext()？

我决定需要计算这些枚举实际上调用“完整”枚举的 MoveNext() 的次数，因为这似乎是分块实现复杂度的最佳估计。所以我编写了一个枚举方法，它使用一个 static 字段来计算枚举返回值的次数，并计算枚举结束的条件。

    // These are in the Program class of a Console Application  
    // so they are static in order to be accessible from the static Main
    static int SECount = 0;
    static IEnumerable<char> SE(int len)
    {
      char c = 'A';
      for (int i = 1; i <= len; ++i)
      {
        ++SECount;
        Console.WriteLine("SE: {0} Count: {1}", c, SECount);
        yield return c++;
      }
      ++SECount;
      Console.WriteLine("SE: (past end) Count: {0}", SECount);
    }

(有一点有点欺骗性，一旦它进入“已过末尾”状态，就不再计算对 MoveNext() 的额外调用。我没有认为这是一个大缺点。)
我还想在 while 条件中添加一些跟踪输出，但 Console.WriteLine 的类型是 void，所以我用一个简单的方法调用 Console.WriteLine 然后返回 true。

    private static bool TrueWriteLine(string format, params object[] args)
    {
      Console.WriteLine(format, args);
      return true;
    }

您可以在下面看到它的用法。

发生了什么？

与上面的 Where() 示例一样，Take() 和更重要的 Skip() 方法实际上并不构建新的集合来迭代，它们只是获取它们接收到的枚举并返回实现 IEnumerable<T> 的类实例，这些实例会 Take 或 Skip 指定数量的元素。

我将修改实现，将单独的 *块* IEnumerable<T> 收集到一个 List 中。这将使解释稍微简单一些，并且不会改变结果。（随附的代码包含这两种实现，因此您可以验证它们的行为是可比较的。）

    public static IEnumerable<IEnumerable<T>> Chunkify0L<T>(this IEnumerable<T> initSource, 
                                                            int chunkSize)
    {
      IEnumerable<T> source = initSource; // this is to help clarify the explanation below.
      List<IEnumerable<T>> result = new List<IEnumerable<T>>();
      while (TrueWriteLine("while source.Any()") && source.Any())
      {
        Console.WriteLine("Take = {0}", chunkSize);
        IEnumerable<T> chunk = source.Take(chunkSize);
        result.Add(chunk);
        Console.WriteLine("skipping = {0}", chunkSize);
        source = source.Skip(chunkSize);
      }
      return result;
    }

(这将很快变得冗长，所以我将使用一个较小的起始枚举。)
当 initSource 中有 7 个元素时，while 循环执行 3 次，返回 2 个包含 3 个元素的枚举和一个包含 1 个元素的枚举。
第一次迭代如下：

source.Any() 对 source.GetEnumerator() 执行 MoveNext()，即 initSource.GetEnumerator().MoveNext()
chunk = source.Take(chunkSize) 将一个 .NET 内部类的实例分配给 chunk，该类捕获 chunkSize 和 source，并且其 GetEnumerator() 返回一个 IEnumerator<char>，它返回 source（此处实际为 initSource）的前 chunkSize 个元素。
此 chunk 被添加到 result 中。
source = source.Skip(chunkSize) 将一个内部类的实例分配给 source，该类捕获 chunkSize 和 source，并且其 GetEnumerator() 返回一个 IEnumerator<char>，它跳过 source（此处实际为 initSource）的前 chunkSize 个元素。

第二次迭代如下：

source.Any() 对 source.GetEnumerator() 执行 MoveNext()。但是 source 是一个将跳过 initSource 的前 3 个（chunkSize）元素的枚举，因此这会导致对 initSource.GetEnumerator() 调用 4 次 MoveNext()（3 次是因为跳过，1 次是因为实际检查（跳过后）的枚举是否为空）。
chunk = source.Take(chunkSize) 将一个 .NET 内部类的实例分配给 chunk，该类捕获 chunkSize 和 source，并且其 GetEnumerator() 返回一个 IEnumerator<char>，它返回 source 的前 chunkSize 个元素。但是，如上所述，source 是一个将跳过 initSource 前 3 个元素的枚举。因此，这等同于：
chunk = initSource.Skip(chunkSize).Take(chunkSize)
此 chunk 被添加到 result 中。
source = source.Skip(chunkSize) 将一个内部类的实例分配给 source，该类捕获 chunkSize 和 source，并且其 GetEnumerator() 返回一个 IEnumerator<char>，它跳过 source 的前 chunkSize 个元素。同样，source 是一个将跳过 initSource 前 3 个元素的枚举。因此，这等同于：
source = initSource.Skip(chunkSize).Skip(chunkSize)

够混乱了吗？还有第三次迭代：

source.Any() 对 source.GetEnumerator() 执行 MoveNext()。但是 source 是一个将跳过 initSource 前 3 个元素的前 3 个元素的枚举，因此这会导致对 initSource.GetEnumerator() 调用 7 次 MoveNext()（6 次是因为跳过，1 次是因为实际检查（跳过后）的枚举是否为空）。
chunk = source.Take(chunkSize) 将一个 .NET 内部类的实例分配给 chunk，该类捕获 chunkSize 和 source，并且其 GetEnumerator() 返回一个 IEnumerator<char>，它返回 source 的前 chunkSize 个元素。但是，如上所述，source 是一个将跳过 initSource 前 3 个元素的前 3 个元素的枚举。因此，这等同于 chunk = initSource.Skip(chunkSize).Skip(chunkSize).Take(chunkSize)
此 chunk 被添加到 result 中。
source = source.Skip(chunkSize) 将一个内部类的实例分配给 source，该类捕获 chunkSize 和 source，并且其 GetEnumerator() 返回一个 IEnumerator<char>，它跳过 source 的前 chunkSize 个元素。同样，source 是一个将跳过 initSource 前 3 个元素的前 3 个元素的枚举。因此，这等同于：
source = initSource.Skip(chunkSize).Skip(chunkSize).Skip(chunkSize)

第四次迭代失败，因为 source.Any() 返回 false，因为 source 中没有元素。source.Any() 导致对 initSource.GetEnumerator() 调用了 8 次 MoveNext()（7 次是因为跳过了 initSource 的所有元素，1 次是实际确定（跳过后）的枚举为空）。
使用以下代码执行此操作

    static void Main(string[] args)
    {
      Console.WriteLine("Before chunkifying");
      var theChunks = SE(7).Chunkify0L(3);
    }

产生以下输出：

Before chunkifying
while source.Any()
SE: A Count: 1
Take = 3
skipping = 3
while source.Any()
SE: A Count: 2
SE: B Count: 3
SE: C Count: 4
SE: D Count: 5
Take = 3
skipping = 3
while source.Any()
SE: A Count: 6
SE: B Count: 7
SE: C Count: 8
SE: D Count: 9
SE: E Count: 10
SE: F Count: 11
SE: G Count: 12
Take = 3
skipping = 3
while source.Any()
SE: A Count: 13
SE: B Count: 14
SE: C Count: 15
SE: D Count: 16
SE: E Count: 17
SE: F Count: 18
SE: G Count: 19
SE: (past end) Count: 20

所以此时 MoveNext() 已被调用 20 次！
请注意，“Take”和“skip”操作在此执行点不会导致 MoveNext() 的调用。
此外，现在 result 包含 3 个枚举（尚未迭代）。

initSource.Take(3)
initSource.Skip(3).Take(3)
initSource.Skip(3).Skip(3).Take(3)

您可能已经看到了惰性评估的后果。

迭代块的内容

迭代每个块的内容的一个简单方法是使用 LINQ 提供的 .ToList() 扩展方法将元素收集到 List<char> 中。所以我将扩展 Program.Main() 来做到这一点。

    static void Main(string[] args)
    {
      Console.WriteLine("Before chunkifying");
      var theChunks = SE(7).Chunkify0L(3);
      Console.WriteLine("Before iterating over the chunks");
      foreach (var chunk in theChunks)
      {
        Console.WriteLine("  Before chunk.ToList()");
        var chunkList = chunk.ToList();
        Console.WriteLine("  After chunk.ToList()");
        Console.WriteLine("  Iterating over the chunkList of length: {0}", chunkList.Count);
        foreach (var item in chunkList)
        {
          Console.WriteLine("    chunkList: {0}", item);
        }
      }
      Console.WriteLine("Total SE Count = {0}", SECount);
      Console.WriteLine("Enter to exit");
      Console.ReadLine();
    }

这然后输出以下内容。（我将省略上面显示的输出，并从“在迭代块内容之前”行开始。）

Before iterating over the chunks
  Before chunk.ToList()
SE: A Count: 21
SE: B Count: 22
SE: C Count: 23
  After chunk.ToList()
  Iterating over the chunkList of length: 3
    chunkList: A
    chunkList: B
    chunkList: C
  Before chunk.ToList()
SE: A Count: 24
SE: B Count: 25
SE: C Count: 26
SE: D Count: 27
SE: E Count: 28
SE: F Count: 29
  After chunk.ToList()
  Iterating over the chunkList of length: 3
    chunkList: D
    chunkList: E
    chunkList: F
  Before chunk.ToList()
SE: A Count: 30
SE: B Count: 31
SE: C Count: 32
SE: D Count: 33
SE: E Count: 34
SE: F Count: 35
SE: G Count: 36
SE: (past end) Count: 37
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
Total SE Count = 37
Enter to exit

第一个 chunk.ToList() 的行为符合预期。它调用 MoveNext() 3 次，从原始枚举中获取 3 个元素。
第二个 chunk.ToList() *从* 原始枚举的开头 *重新开始*，调用 MoveNext() 6 次！请记住，第二个块仍然有延迟的（惰性的）Skip(3) 操作，因此它首先调用 MoveNext() 3 次来执行 Skip()，然后另外 3 次来获取 3 个元素。
同样，第三个 chunk.ToList() 从原始枚举的开头重新开始，调用 MoveNext() 8 次，这是由于连续的两个延迟 Skip(3) 操作。因此，有 6 次 MoveNext() 用于 Skip()，1 次用于获取枚举的第七个元素，1 次用于检测枚举已结束。

计算复杂度增长为 **O(n²)**（其中 **n** 是原始枚举的长度）。MoveNext() 调用次数的最大增量发生在 **n mod chunkSize == 1** 的长度处。（有关复杂性分析，请参见下文。）因此，对于短长度的源枚举（initSource），这不是什么大问题。但是，随着源枚举变长，情况会变得糟糕。很快！

那么有什么办法呢？

下一步似乎是提高效率。因此，摆脱串联的 Skip() 操作似乎是关键。

第一个新实现

我认为，如果我显式遍历源枚举的 IEnumerator<T>，然后在构建块的同时更新 IEnumerator<T>，应该可以工作。我仍然想避免为每个块构建新的内存集合。所以这是下一次迭代：

    public static IEnumerable<IEnumerable<T>> Chunkify1<T>(this IEnumerable<T> source, 
                                                           int chunkSize)
    {
      IEnumerator<T> e = source.GetEnumerator();
      Func<bool> mover = () => { Console.WriteLine("Chunkify MoveNext"); return e.MoveNext(); };
      while (mover())
      {
        yield return ChunkIterator(e, chunkSize);
      }
    }

    private static IEnumerable<T> ChunkIterator<T>(IEnumerator<T> e, 
                                                      int chunkSize)
    {
      Console.WriteLine("ChunkIterator = {0}", chunkSize);
      do
      {
        Console.WriteLine("CI[{1}]: {0}", e.Current, chunkSize);
        yield return e.Current;
      } while (--chunkSize > 0 && e.MoveNext());
    }

这似乎运行良好，将上面显示的 Program.Main() 中的 Chunkify0L(3) 更改为 Chunkify1(3)，我得到了：

Before chunkifying
Before iterating over the chunks
Chunkify MoveNext
SE: A Count: 1
  Before chunk.ToList()
ChunkIterator = 3
CI[3]: A
SE: B Count: 2
CI[2]: B
SE: C Count: 3
CI[1]: C
  After chunk.ToList()
  Iterating over the chunkList of length: 3
    chunkList: A
    chunkList: B
    chunkList: C
Chunkify MoveNext
SE: D Count: 4
  Before chunk.ToList()
ChunkIterator = 3
CI[3]: D
SE: E Count: 5
CI[2]: E
SE: F Count: 6
CI[1]: F
  After chunk.ToList()
  Iterating over the chunkList of length: 3
    chunkList: D
    chunkList: E
    chunkList: F
Chunkify MoveNext
SE: G Count: 7
  Before chunk.ToList()
ChunkIterator = 3
CI[3]: G
SE: (past end) Count: 8
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
Chunkify MoveNext
Total SE Count = 8
Enter to exit

这看起来 *很棒*，MoveNext() 调用次数为 8。（原始枚举的 7 个元素中的每一个一个，以及 1 个用于确定它已完成。）

但是，如果结果块不在 theChunks 中出现的顺序中进行迭代会发生什么？我尝试按相反的顺序迭代块。

Before chunkifying
Before iterating over the chunks
Chunkify MoveNext
SE: A Count: 1
Chunkify MoveNext
SE: B Count: 2
Chunkify MoveNext
SE: C Count: 3
Chunkify MoveNext
SE: D Count: 4
Chunkify MoveNext
SE: E Count: 5
Chunkify MoveNext
SE: F Count: 6
Chunkify MoveNext
SE: G Count: 7
Chunkify MoveNext
SE: (past end) Count: 8
  Before chunk.ToList()
ChunkIterator = 3
CI[3]: G
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
  Before chunk.ToList()
ChunkIterator = 3
CI[3]: G
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
  Before chunk.ToList()
ChunkIterator = 3
CI[3]: G
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
  Before chunk.ToList()
ChunkIterator = 3
CI[3]: G
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
  Before chunk.ToList()
ChunkIterator = 3
CI[3]: G
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
  Before chunk.ToList()
ChunkIterator = 3
CI[3]: G
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
  Before chunk.ToList()
ChunkIterator = 3
CI[3]: G
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
Total SE Count = 8
Enter to exit

**哇！发生了什么？** 调用次数仍然是 8，但不再是两个长度为 3 的块和一个长度为 1 的块，而是七个长度为 1 的块，它们都包含原始源枚举的 *同一个* 第七个元素（“G”）。

同样，问题仍然是块和块内容的惰性枚举。它们都共享源枚举的同一个 IEnumerator<T>，所以如果它不是按我们期望的顺序使用，我们会得到无意义的结果。

如果您想知道“为什么不直接克隆 IEnumerator<T> 然后将其传递给 ChunkIterator()？”，这两种原因都行不通：

无法克隆 IEnumerator<T>。它是一个接口。它后面的对象可以是 *任何* 实现该接口的对象。
即使您可以制作 IEnumerator<T> 的副本，它也不会有帮助，因为这实际上 *依赖于* 共享状态在 ChunkIterator() 中更新，以便为 Chunkify1() 中的下一个块（或检测源的结束）做好准备。

所以，这工作 **但有一个 *警告***：块必须按照原始序列顺序完全迭代。

下一个新实现

虽然我想避免为每个块构建新的内存集合，但我认为做相反的事情，构建一个列表的列表，肯定可以防止我在上面的非顺序处理情况下看到的奇怪行为。所以，

    public static IEnumerable<IEnumerable<T>> Chunkify2<T>(this IEnumerable<T> source, 
                                                           int chunkSize)
    {
      List<IEnumerable<T>> allChunks = new List<IEnumerable<T>>();
      int count = 0;
      List<T> chunk = null;
      foreach (var item in source)
      {
        if (chunk == null)
        {
          Console.WriteLine("  New chunk");
          chunk = new List<T>(chunkSize);
          count = 0;
          allChunks.Add(chunk);
        }
        Console.WriteLine("  chunk[{0}]: {1}", count + 1, item);
        chunk.Add(item);
        if (++count == chunkSize)
        {
          chunk = null;
        }
      }
      return allChunks;
    }

这奏效了，在 Program.Main() 中将 Chunkify2(3) 更改为 Chunkify2(3) 会得到相同的调用次数 8，并且向前和向后行为都正确。

Forward
Before chunkifying
SE: A Count: 1
  New chunk
  chunk[1]: A
SE: B Count: 2
  chunk[2]: B
SE: C Count: 3
  chunk[3]: C
SE: D Count: 4
  New chunk
  chunk[1]: D
SE: E Count: 5
  chunk[2]: E
SE: F Count: 6
  chunk[3]: F
SE: G Count: 7
  New chunk
  chunk[1]: G
SE: (past end) Count: 8
Before iterating over the chunks
  Before chunk.ToList()
  After chunk.ToList()
  Iterating over the chunkList of length: 3
    chunkList: A
    chunkList: B
    chunkList: C
  Before chunk.ToList()
  After chunk.ToList()
  Iterating over the chunkList of length: 3
    chunkList: D
    chunkList: E
    chunkList: F
  Before chunk.ToList()
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
Total SE Count = 8
Enter to exit

Reverse
Before chunkifying
SE: A Count: 1
  New chunk
  chunk[1]: A
SE: B Count: 2
  chunk[2]: B
SE: C Count: 3
  chunk[3]: C
SE: D Count: 4
  New chunk
  chunk[1]: D
SE: E Count: 5
  chunk[2]: E
SE: F Count: 6
  chunk[3]: F
SE: G Count: 7
  New chunk
  chunk[1]: G
SE: (past end) Count: 8
Before iterating over the chunks
  Before chunk.ToList()
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
  Before chunk.ToList()
  After chunk.ToList()
  Iterating over the chunkList of length: 3
    chunkList: D
    chunkList: E
    chunkList: F
  Before chunk.ToList()
  After chunk.ToList()
  Iterating over the chunkList of length: 3
    chunkList: A
    chunkList: B
    chunkList: C
Total SE Count = 8
Enter to exit

这是符合预期的。一切都被组装成一个内存中的块集合，其中每个块本身被组装成一个内存中的集合。

但是，如果我们有一个源枚举，从中获取下一个元素相对较慢，那么一次获取 *所有* 源会非常慢；但是获取一个块的大小是可以的。或者，如果源枚举非常大，但块的大小合理？我们还能 *有点* 懒惰吗？

最终的新实现

此实现将每个块构建为 List<T>，但以惰性（*按需*）方式提供它们。

    public static IEnumerable<IEnumerable<T>> Chunkify<T>(this IEnumerable<T> source, 
                                                          int chunkSize)
    {
      IEnumerator<T> e = source.GetEnumerator();
      Func<bool> mover = () => { Console.WriteLine("Chunkify MoveNext"); return e.MoveNext(); };
      int count = 0;
      while (mover())
      {
        Console.WriteLine("  New chunk");
        List<T> chunk = new List<T>(chunkSize);
        do
        {
          Console.WriteLine("  chunk[{1}]: {0}", e.Current, count);
          chunk.Add(e.Current);
        } while (++count < chunkSize && e.MoveNext());
        yield return chunk;
        count = 0;
      }
    }

这的结果是：

Forward
Before chunkifying
Before iterating over the chunks
Chunkify MoveNext
SE: A Count: 1
  New chunk
  chunk[0]: A
SE: B Count: 2
  chunk[1]: B
SE: C Count: 3
  chunk[2]: C
  Before chunk.ToList()
  After chunk.ToList()
  Iterating over the chunkList of length: 3
    chunkList: A
    chunkList: B
    chunkList: C
Chunkify MoveNext
SE: D Count: 4
  New chunk
  chunk[0]: D
SE: E Count: 5
  chunk[1]: E
SE: F Count: 6
  chunk[2]: F
  Before chunk.ToList()
  After chunk.ToList()
  Iterating over the chunkList of length: 3
    chunkList: D
    chunkList: E
    chunkList: F
Chunkify MoveNext
SE: G Count: 7
  New chunk
  chunk[0]: G
SE: (past end) Count: 8
  Before chunk.ToList()
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
Chunkify MoveNext
Total SE Count = 8
Enter to exit

Reverse
Before chunkifying
Before iterating over the chunks
Chunkify MoveNext
SE: A Count: 1
  New chunk
  chunk[0]: A
SE: B Count: 2
  chunk[1]: B
SE: C Count: 3
  chunk[2]: C
Chunkify MoveNext
SE: D Count: 4
  New chunk
  chunk[0]: D
SE: E Count: 5
  chunk[1]: E
SE: F Count: 6
  chunk[2]: F
Chunkify MoveNext
SE: G Count: 7
  New chunk
  chunk[0]: G
SE: (past end) Count: 8
Chunkify MoveNext
  Before chunk.ToList()
  After chunk.ToList()
  Iterating over the chunkList of length: 1
    chunkList: G
  Before chunk.ToList()
  After chunk.ToList()
  Iterating over the chunkList of length: 3
    chunkList: D
    chunkList: E
    chunkList: F
  Before chunk.ToList()
  After chunk.ToList()
  Iterating over the chunkList of length: 3
    chunkList: A
    chunkList: B
    chunkList: C
Total SE Count = 8
Enter to exit

反转 theChunks 会强制创建所有单独的块，因此如果 theChunks 在处理单个块之前被迭代，那么这与列表的列表相比没有多大优势。

随附的代码

我附上了本文的所有代码。它包括扩展方法实现的版本，这些版本不执行 Console.WriteLine() 输出。其中的实现还包括一些基本的参数检查，我在文章正文中省略了这些检查。随附代码中的 Visual Studio 项目文件来自 VS 2012，目标是 .NET 4，但代码应该可以在支持 LINQ 的早期 C#/.NET 版本中使用。

最后的想法

使用 LINQ 扩展方法可以非常强大，可以轻松实现某些操作，并且非常易读/可维护。但是，记住这些方法（以及大多数枚举器，总的来说）的惰性行为很重要，并仔细考虑事情将如何真正工作。

Chunkify0 的复杂性分析

为了分析 Chunkify0 的计算复杂性，我生成了 chunkSize 为 2 到 6 的 MoveNext() 计数，其序列长度是 chunkSize 的倍数，使用了 **length mod chunkSize == 1** 的长度，因为这些长度主导了复杂性增长。我使用了以下代码生成数据，我可以将其复制粘贴到 Octave（免费的 Matlab 等效软件）中，然后使用它将数据拟合到多项式。

      for (int chunkSize = 2; chunkSize <= 6; chunkSize++)
      {
        string delim = string.Empty;
        Debug.Write(string.Format("data{0} = [", chunkSize));
        for (int sequenceLengthFactor = 1; sequenceLengthFactor <= 5; sequenceLengthFactor++)
        {
          SECount = 0;
          var theChunks = SE(1 + sequenceLengthFactor * chunkSize).Chunkify0(chunkSize);
          foreach (var chunk in theChunks)
          {
            var chunklist = chunk.ToList();
          }
          Debug.Write(string.Format("{0}{1}, {2}", delim, 1 + sequenceLengthFactor * chunkSize, SECount));
          delim = "; ";
        }
        Debug.WriteLine("];");
      }

这非常完美地拟合了一组二次方程，其系数取决于 chunkSize，并且可以简化为：

${1 \over chunkSize} \times n^2 + (2 + {chunkSize - 1 \over chunkSize}) \times n + 2$

其中 n 是序列长度。

历史

2014 年 6 月 2 日 - 初始版本。
2014 年 6 月 5 日 - 添加了复杂性分析。