1,349 次浏览

最佳实践：根据条件获取集合的部分结果

Posted on by nista

很多场景下，我们需要根据一个条件判定某一集合中是否存在或从中选取部分符合条件的元素用于后续操作。我们有很多方式可以实现这种需求，比如 纯手工对集合进行遍历，yield return，Any()，Count() 或 Count 属性，那么，这些实现方式对效率的影响如何？哪种实现效率较优呢？

我们来做一次实验。

首先我们定义一个类，并初始化包含有 1 万个该类型实例的集合。

    public class Item
    {
        public Guid Id { get; set; }
        public string Name { get; set; }
        public bool Gender { get; set; }
        public int Age { get; set; }
        public DateTime Birthday { get; set; }
        public string Address { get; set; }
        public string Email { get; set; }
    }


        private static Random random = new Random(DateTime.Now.Second);
        private static List<Item> targetDataSource;
        private static int TotalNum = 10000;

        static InitialDataSource()
        {
            targetDataSource = new List<Item>();

            for (var i = 0; i < TotalNum; i++)
            {
                targetDataSource.Add(new Item
                {
                    Id = Guid.NewGuid(),
                    Name = $"Charles {random.Next()} Judson",
                    Age = random.Next(),
                    Gender = true,
                    Birthday = DateTime.UtcNow,
                    Address = $"Home #{random.Next()} streets, ABC City.",
                    Email = $"{random.Next()}@test.com"
                });
            }
        }

随后，我们构建两个方法，一个是新建一个空集合，并遍历包含 1 万条数据的集合，将所有符合 Name.Contains(“66”) && Age > 1000L 条件的元素添加到空集合中，另一个方法则采用 yield return 完成相同的实现，我们对两种方法分别用 stopwatch 计时。

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace YieldReturnPerformance
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var timer = new Stopwatch();

            timer.Start();
            var result1 = StartTestConvention();
            timer.Stop();
            Console.WriteLine($"Time usage: {timer.ElapsedMilliseconds} ms");

            timer.Reset();

            timer.Start();
            var result2 = StartTestYieldReturn();
            timer.Stop();
            Console.WriteLine($"Time usage: {timer.ElapsedMilliseconds} ms");

            Console.ReadKey(true);
        }

        public static IEnumerable<Item> StartTestConvention()
        {
            var result = new List<Item>();
            foreach (var i in targetDataSource)
            {
                if (i.Name.Contains("66") && i.Age > 1000L)
                {
                    result.Add(i);
                }
            }
            return result;
        }

        public static IEnumerable<Item> StartTestYieldReturn()
        {
            foreach (var i in targetDataSource)
            {
                if (i.Name.Contains("66") || i.Age > 1000L)
                {
                    yield return i;
                }
            }
        }
    }
}

执行结果为：10000 条数据时，

方式 用时
新建集合并遍历的方式 4 ms
yield return 实现 0 ms

第二种方式 0 ms？难道是我们的数据量不够大？我们将初始构建的数据从 10000 条更改为 100000 条，结果依旧为：

方式 用时
新建集合并遍历的方式 43 ms
yield return 实现 0 ms

为什么是 0 ms? —— LINQ 方法的延迟执行

yield 关键字的应用使我们对集合的具体查询被延迟到真正有调用方去访问这个结果时执行，yield 只能出现在迭代器块中，迭代器块就是一个返回类型为 IEnumerable<TSource> 的方法，也就是我们例子中的
StartTestConvention() 和 StartTestYieldReturn() 方法。迭代器是 LINQ 查询中延迟执行行为的基础。

yield return 语句会使元素在下一个元素之前立即返回给调用方。尽管我们是通过方法的形式编写迭代器，但编译器会将其转换为一个实际上是状态机的嵌套类。只要调用方的 foreach 循环继续进行，此类就会跟踪迭代器的位置。下次调用迭代器时将从此位置重新开始执行。我们可以通过 ILDASM 工具查看这个由编译器自动实现的嵌套类。添加一个方法用于调用迭代器块：

        public static void Test()
        {
            foreach (var item in StartTestYieldReturn())
            {
                Console.WriteLine(item.Name);
            }
        }

查看这个方法的 IL 代码，会发现，代码在调用 item 的属性时，其实被包含一个自动生成的迭代器的 get_Current() 方法和 MoveNext() 方法包裹。这个自动实现的嵌套类的轮廓如下图所示。

综上所述，为了完成我们对两种实现效率上的比较，我们需要对返回的结果集合调用一个具体的后续方法。这里我们假设调用 Any() 方法，来判定是否查找到了符合条件的元素。

timer.Start();
var result1 = StartTestConvention();
bool hasData1 = result1.Any();
timer.Stop();
Console.WriteLine($"Time usage: {timer.ElapsedMilliseconds} ms");

timer.Reset();

timer.Start();
var result2 = StartTestYieldReturn();
bool hasData2 = result2.Any();
Console.WriteLine($"Time usage: {timer.ElapsedMilliseconds} ms");

这一次，我们使结果查询得以真正执行，针对 10 万条数据结果为：

方式 用时
新建集合并遍历的方式 43 ms
yield return 实现 1 ms

由此，我们可以充分的发现，通过 yield return 的延迟执行机制，可以大量节省提前执行的遍历逻辑及创建临时结果集合的开销。

我们来扩展一下，探讨两个相关的问题。

为什么要使用 Any() 方法来判定是否集合中存在元素，而不是 Count() 方法或 Count 属性呢？

由于 yield 关键字只允许在迭代器块中进行使用，方法的返回类型需要为 IEnumerable<Item>，这使我们无法直接获得 Count 属性的值。我们将 Any() 方法修改为 Count() 方法，运行的用时如下：

方式 用时
新建集合并遍历的方式 40 ms
yield return 实现 45 ms

为什么 Count() 会比 Any() 慢 44 毫秒？

查看 .NET 类库的源代码，我们就可以发现其中的原因。以下是 Count() 方法的实现。

        public static int Count<TSource>(this IEnumerable<TSource> source) {
            if (source == null) throw Error.ArgumentNull("source");
            ICollection<TSource> collectionoft = source as ICollection<TSource>;
            if (collectionoft != null) return collectionoft.Count;
            ICollection collection = source as ICollection;
            if (collection != null) return collection.Count;
            int count = 0;
            using (IEnumerator<TSource> e = source.GetEnumerator()) {
                checked {
                    while (e.MoveNext()) count++;
                }
            }
            return count;
        }

以下是 Any() 方法的实现。

        public static bool Any<TSource>(this IEnumerable<TSource> source) {
            if (source == null) throw Error.ArgumentNull("source");
            using (IEnumerator<TSource> e = source.GetEnumerator()) {
                if (e.MoveNext()) return true;
            }
            return false;
        }

可以发现，如果我们所操作的目标集合类型，没有实现 ICollection<TSource> 或 ICollection 接口，Count() 方法则会遍历集合以进行计数（可以发现，我们这里的返回类型是 IEnumerable<Item>，而不是 List<Item>，虽然 List<T> 实现了 ICollection 接口，但是代码在此处由于延迟执行并没有具体的结果，无法进行隐式的类型转换，更无法直接得到 Count 属性的值）。而 Any() 方法只是尝试调用一次迭代指针，如果发现可以指向下一个元素，则直接返回 true。

我们的方法为什么要返回一个 IEnumerable<TSource> 而不是具体集合类型呢？

首先，不要觉得返回接口就是最佳实践，返回类型的抽象级别，展现了被调用方希望调用方所抽象的高度。当我们向调用方返回一个集合类型的对象时，一定要看具体的调用场景，根据实际的调用方需求，决定返回类型。虽然 List 和 IEnumerable 之间可以任意的转换，但是关键的点在于性能，假如你的方法得到了一个 IEnumerable 结果，因为受到了返回类型的限制，而去主动地执行 ToList() 方法，这就执行了一次遍历！如果调用者根本不需要 List 对象，而是只需要一个迭代器，而调用者却执行了 List 的迭代器，这就又发生了一次遍历！所以，如果调用方需要对集合进行直接的具体操作，我们应该返回具体类型，防止类似 ToList() 这类重复操纵，如果被调用方是提供查询或较高层次的返回，则可以选择 IEnumerable 类型保持抽象，遵循最小接口原则（客户端不应该依赖它不需要的接口）。总之，抽象应该尽量做到恰到好处，并在实际的需求中动态地进行不断的重构。

其次，如前所述，我们不能在一个返回类型是 List<Item> 的方法中使用 yield 关键字，它不是一个迭代器块，编写代码时我们会收到如下错误。

Any() 方法 包含一个重载，Any (Func<TSource, bool> predicate)

前文中，我们为了根据一个条件而去判定目标集合是否存在一类对象这种场景，如果改用 Any (Func<TSource, bool> predicate) 这个重载，执行效率会不会更快呢？

我们添加一个新的计时器

            timer.Start();
            targetDataSource.Any(e => e.Name.Contains("66") || e.Age > 1000L);
            Console.WriteLine($"Time usage: {timer.ElapsedMilliseconds} ms");

针对 10 万条数据，结果为，

方式 用时
新建集合并遍历的方式 43 ms
yield return 实现 1 ms
直接使用 Any (Func<TSource, bool> predicate) 0 ms

查看 .NET 类库 Enumerable 类的实现，可以发现这个重载方法是针对集合中的每一个元素都运行所指定的函数表达式，一旦找到第一个匹配结果就立即返回。

        public static bool Any<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
            if (source == null) throw Error.ArgumentNull("source");
            if (predicate == null) throw Error.ArgumentNull("predicate");
            foreach (TSource element in source) {
                if (predicate(element)) return true;
            }
            return false;
        }

如果我们不仅需要判定元素是否存在，还想获得所有符合条件的元素，除了自行根据逻辑采用 yield 关键字编写实现以外，还可以直接选择 Where() 方法进行实现，其源代码位于 System.Dynamic.Utils 命名空间的 CollectionExtensions 类下。

internal static IEnumerable<T> Where<T>(this IEnumerable<T> enumerable, Func<T, bool> where) {
    foreach (T t in enumerable) {
        if (where(t)) {
            return t;
        }
    }
}

Count 属性的速度如何？

微软的官方文档中明确的指出，“Retrieving the value of this property (List<T>.Count Property) is an O(1) operation.”，调用它的时间复杂度为 O(1) 直接寻址获得，不会发生重新计算，因此，在目标集合类型实现了 IEnumerable 接口的同时也实现了 ICollection 接口的情况下，应该首先选择 Count 属性。

例如，当我们编写一个扩展方法时，如果它只实现了 IEnumerable 接口

public static IsEmpty(this IEnumerable list)
{
    IEnumerator en = list.GetEnumerator();
    return !en.MoveNext();
}

如果实现了 ICollection 接口，则可以

public static bool IsNullOrEmpty<T>(this ICollection<T> source)
{
    return source == null || source.Count <= 0;
}

更多可参考，这里和这里。

结论

  • 判定集合是否存在元素时，一定优先选择使用 Any() 而非 Count() 方法
  • 如果集合的类型实现了 IEnumerable 接口的同时也实现了 ICollection 接口，则可以直接通过 Count 属性判定，它的时间复杂度是 O(1)，它不会发生重新计数的计算
  • 获得一个集合中所有满足条件的元素，应使用 Where() 方法，或者使用 yield return 的方式自行实现逻辑，而非手动遍历全体元素。要尽量做到根据需求确定集合类型和所要调用的方法，节约内存开销，减少不必要的类型转换和元素遍历。
  • 大家可以通过微软官方的这个网站查看 .NET 类库的源代码，学习更多类库背后的故事（对于 .NET Framework 类库的源代码则可以查看这里）。
微海报分享

About nista

THERE IS NO FATE BUT WHAT WE MAKE.

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注