为什么C# LINQ Distinct方法更快

6tdlim6h 于 2023-07-31 发布在 C#

关注(0)|答案(1)|浏览(174)

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

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}");

字符串
结果：外循环开始：2020/6/20 4：15：31 PM外循环结束：2020/6/20 4：15：31 PM嵌套循环开始：2020/6/20 4：15：32 PM嵌套循环结束：2020/6/20 4：15：46 PM
Outerloop只需要1秒，但嵌套循环需要14秒。在foreach中，Distinct比使用“Any”函数快多少？

linq

来源：https://stackoverflow.com/questions/62488467/why-c-sharp-linq-distinct-method-is-faster

1条答案

按热度按时间

brccelvz1#

首先，它更快，因为Distinct实际上几乎什么都不做-uniqueIds不是物化的IEnumerable<int>（例如，您可以在ids和.Distinct()之间添加.Select(c => {Console.WriteLine(c);return c;})），将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 |

型
最后是“为什么”。
Distinct在内部使用DistinctIterator，而DistinctIterator又使用内部的Set类，描述为A lightweight hash set，据我所知，在搜索Big-O复杂度方面应该与hashtable相当，在最佳/平均情况下导致constant search time，而List的搜索（!oids.Any）复杂度为O（n）。

赞(0）回复(0）举报 2023-07-31

我来回答

为什么C# LINQ Distinct方法更快

1条答案

相关问题

热门标签

最新问答