Почему метод C# linq Distinct быстрее

Question

Я проверил отличную производительность по вложенным l oop с любым. Но Distinct Method намного быстрее, чем вложенный l oop.

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

Результат: Внешний L oop начало: 20.06.2020 16:15:31 Внешний L oop Конец: 6 / 20/2020 16:15:31 Вложенный L oop начало: 20.06.2020 16:15:32 Вложенный L oop Конец: 20.06.2020 16:15:46

Это заняло всего 1 секунду для Outerl oop и 14 секунд для вложенного l oop. Насколько Distinct намного быстрее, чем использование функции Any в foreach?

Answer 1

Во-первых, это быстрее, потому что Distinct на самом деле почти ничего не делает - uniqueIds не материализуется IEnumerable<int> (вы можете проверить это, добавив .Select(c => {Console.WriteLine(c);return c;}), например, между ids и .Distinct()), изменить uniqueIds строка объявления:

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

Вторичный для правильного тестирования Я бы рекомендовал использовать BenchmarkDo tNet, для вашего случая вы можете составить, например, следующий тест (удален / реорганизован некоторый код потому что это не имеет отношения к фактическому тестируемому материалу):

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, который, в свою очередь, использует внутренний класс Set, описанный как A lightweight hash set , который, как я понимаю, должен быть сопоставим по сложности поиска Big-O с хеш-таблицей , в результате чего постоянное время поиска в лучшем / среднем случае, а List будет иметь поиск (!oids.Any) сложность O (n).