为什么 C# linq Distinct 方法更快

Question

我已经用 any 检查了嵌套循环的不同性能。但是 Distinct Method 比嵌套循环快得多。

var customers = new List<Customer>();

            for (var i = 1; i <= 100000; i++)
            {
                var id = (int)Math.Floor((decimal)i / 10);
                var customer = new Customer()
                {
                    FirstName = $"Name {i}",
                    ID = id,
                    LastName = $"Last {i}"
                };

                customers.Add(customer);
            }

            System.Console.WriteLine($"Outer Loop start :{DateTime.UtcNow}");

            var ids = new List<int>();

            customers.ForEach(_=> {
                ids.Add(_.ID);
            });

            var uniqueIds = ids.Distinct();

            System.Console.WriteLine($"Outer Loop End :{DateTime.UtcNow}");

            System.Console.WriteLine($"Nested Loop start :{DateTime.UtcNow}");

            var oids = new List<int>();

            customers.ForEach(_ => {
                if (!oids.Any(i => i == _.ID))
                {
                    oids.Add(_.ID);
                }
            });
            System.Console.WriteLine($"Nested Loop End :{DateTime.UtcNow}");

结果：外循环开始：6/20/2020 4:15:31 PM 外循环结束：6/20/2020 4:15:31 PM 嵌套循环开始：6/20/2020 4:15:32 PM 嵌套循环结束:6/20/2020 下午 4:15:46

Outerloop 只用了 1 秒，而嵌套循环用了 14 秒。Distinct 比在 foreach 中使用“Any”函数快得多？

Answer 1

首先它更快，因为Distinct实际上几乎什么都不做 -uniqueIds没有实现IEnumerable<int>（您可以检查它.Select(c => {Console.WriteLine(c);return c;})在ids和之间添加.Distinct()），将uniqueIds声明行更改为：

var uniqueIds = ids.Distinct().ToList();

次要进行适当的基准测试，我建议使用BenchmarkDotNet，对于您的情况，您可以编写以下基准测试（删除/重组一些代码，因为它与实际的基准测试内容无关）：

public class GetDistinctIds
{
    private static readonly List<int> CustomerIds = Enumerable.Range(0, 100_000)
       .Select(i => (int) Math.Floor((decimal) i / 10))
       .ToList();

    [Benchmark]
    public List<int> Distinct() => CustomerIds.Distinct().ToList();

    [Benchmark]
    // just for fun =)
    // returning object so BenchmarkDotNet won't complain, actually non-materialized IEnumerable<int>
    public object DistinctNoToList() => CustomerIds.Distinct();

    [Benchmark]
    public List<int> HashSet() => new HashSet<int>(CustomerIds).ToList();

    [Benchmark]
    public List<int> NestedLoops()
    {
        var oids = new List<int>();

        CustomerIds.ForEach(id =>
        {
            if (!oids.Any(i => i == id))
            {
                oids.Add(id);
            }
        });
        return oids;
    }
}

这在我的机器上给出了下一个结果：

|           Method |                Mean |             Error |            StdDev |
|----------------- |--------------------:|------------------:|------------------:|
|         Distinct |     1,842,519.98 ns |     16,088.362 ns |     17,882.171 ns |
| DistinctNoToList |            17.19 ns |          0.412 ns |          1.070 ns |
|          HashSet |     1,911,107.12 ns |     31,699.290 ns |     29,651.535 ns |
|      NestedLoops | 4,100,604,547.06 ns | 78,815,290.539 ns | 80,937,500.636 ns |

最后到“为什么”。

DistinctDistinctIterator在内部使用，它又使用内部Set类，描述为A lightweight hash set，据我所知，在搜索 Big-O 复杂性方面应该与hashtable相媲美，从而在最佳/平均情况下导致恒定的搜索时间，同时List将进行搜索（!oids.Any) 的复杂度为 O(n)。