[优化此]：慢速LINQ to Objects查询

Question

我有一个查询正在困扰着我；它被封装为一个新的查询操作符，我创建了它的两个版本，试图看看哪一个执行得更好。两者的表现都很糟糕。

第一次尝试；声明式风格

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerable<α> source, int length)
{
    return source.Any()
        ? source.Take(length).Cons(source.Skip(length).Section(length))
        : Enumerable.Empty<IEnumerable<α>>();
}

第二次尝试:命令式的“收益回报”风格

public static IEnumerable<IEnumerable<α>> Section<α>(this IEnumerable<α> source, int length)
{
    var fst = source.Take(length);
    var rst = source.Skip(length);

    yield return fst;

    if (rst.Any())
        foreach (var section in rst.Section(length))
            yield return section;
}

事实上，第二次尝试在可读性、可组合性和速度方面都更差。

关于如何优化这一点有什么线索吗？

Answer 1

我怀疑您遇到的问题与枚举最终结果至少是一个O(n^2)操作有关，甚至可能更糟；我还没有在脑海中解决所有的问题。

为什么会这样呢？好吧，假设你有1，2，3，4，5，6，你把它分成你认为的{{ 1，2 }，{3，4}，{5，6} }

这不是你所做的。实际上，你已经将其拆分成{取前两个，取前两个并丢弃它们，然后取下两个，取前两个并丢弃，然后取下两个并丢弃它们，然后取第三个两个}

注意到每一步是如何重新计算结果的吗？这是因为数组可能会在对枚举的调用之间发生变化。LINQ被设计为总是让您获得最新的结果；您编写了一个意味着“跳过前四个，迭代下两个”的查询，这就是您得到的结果--一个在枚举代码时执行该代码的查询。

原始序列是否足够小和足够快，以至于您可以将整个序列读取到内存中，并一次性将其拆分，而不是尝试懒惰地执行此操作？或者，序列是可索引的吗？如果您得到的只是对序列的前向访问，并且它太大或太慢而不能一次全部读取到内存中，那么在这里您可以做的事情就不多了。但如果你有这两个属性中的一个或两个，那么你可以使它至少是线性的。

Answer 2

如果我没理解错的话，您正在尝试构建一个枚举器的惰性实现，该实现将较大的项集合划分为较小的可枚举项集合。

例如，一个一百万个数字的序列可以被分成“部分”，每个部分只产生100个数字，而你想要所有的数字都懒惰地完成，即。不要在生产前将100个项目收集到一个列表中。

首先，您的尝试将多次重复遍历集合，这是不好的，因此会出现性能问题。

如果你正在尝试构建一个纯粹的惰性实现，你应该考虑以下问题：

• 您只想迭代基础集合一次
• 您应该返回重用基础枚举器的枚举对象
• 您需要处理您返回的节没有被完全枚举(例如，调用代码只需要这100项中的前50项)。

编辑：在我进入我的简单解决方案之前，这里有一些关于它的警告：

• 你不能保存每个部分以备后用，例如。您不能这样做:获取sections.
• You数组的collection.Sequence(10).ToArray()不能多次枚举每个节，因为当您这样做时，它会更改隐藏的基础数据结构。

基本上:我的解决方案不是通用的。如果你需要的话，你应该使用@LBushkin关于MoreLinq Batch的评论，我会犹豫是否把我的代码放到一个类库中，它必须放在需要它的地方，或者重命名为清楚地警告你与它相关的问题的东西。

这是一个简单的实现，我非常肯定这里有bug，所以你可能想要考虑为edgecases实现大量的单元测试：

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

namespace ConsoleApplication20
{
    class SectionEnumerable<T> : IEnumerable<T>
    {
        private readonly IEnumerator<T> _Enumerator;

        public SectionEnumerable(IEnumerator<T> enumerator, int sectionSize)
        {
            _Enumerator = enumerator;
            Left = sectionSize;
        }

        public IEnumerator<T> GetEnumerator()
        {
            while (Left > 0)
            {
                Left--;
                yield return _Enumerator.Current;
                if (Left > 0)
                    if (!_Enumerator.MoveNext())
                        break;
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public int Left { get; private set; }
    }

    static class SequenceExtensions
    {
        public static IEnumerable<IEnumerable<T>> Section<T>(this IEnumerable<T> collection, int sectionSize)
        {
            if (collection == null)
                throw new ArgumentNullException("collection");
            if (sectionSize < 1)
                throw new ArgumentOutOfRangeException("sectionSize");

            using (IEnumerator<T> enumerator = collection.GetEnumerator())
            {
                while (enumerator.MoveNext())
                {
                    SectionEnumerable<T> enumerable = new SectionEnumerable<T>(enumerator, sectionSize);
                    yield return enumerable;
                    for (int index = 0; index < enumerable.Left; index++)
                        if (!enumerator.MoveNext())
                            yield break;
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var sequence = Enumerable.Range(0, 100);
            var sections = sequence.Section(10);
            foreach (var section in sections)
            {
                Console.WriteLine(
                    String.Join(", ",
                    section.Take(5).ToArray().Select(i => i.ToString()).ToArray()));
            }
            Console.ReadLine();
        }
    }
}

输出：

0, 1, 2, 3, 4
10, 11, 12, 13, 14
20, 21, 22, 23, 24
30, 31, 32, 33, 34
40, 41, 42, 43, 44
50, 51, 52, 53, 54
60, 61, 62, 63, 64
70, 71, 72, 73, 74
80, 81, 82, 83, 84
90, 91, 92, 93, 94

你应该进行单元测试的事情：

• 空输入集合不生成节
• 具有正确数量元素的集合仅生成一个节
• 包含多个节大小元素的集合(即.10、20、30等)，则不会在所有预期的元素之后生成空节(
• 表示它实际上是惰性的)，如果您枚举了第一个包含10个元素的部分，但只枚举了第二个部分的前5个元素，则在

上仅枚举基础集合的前15个元素

Answer 3

在任何可能的情况下，我都会尝试在操作符中只遍历源一次。如果源代码类似于Reverse()运算符的结果，则调用Any、Take和Skip可能会导致很多糟糕的性能。

不完全清楚你的操作员想要做什么，但是如果你可以在不多次阅读源代码的情况下做到这一点，那可能会很有帮助--尽管这在很大程度上取决于输入是什么。