Przeszukiwanie kolekcji w .net core

Chciałbym Ci przedstawić moje testy wydajnościowe przeszukiwania kolekcji. W C# mamy kilka możliwości przeszukania kolekcji. Możemy użyć LINQ, pętle for czy foreach. Pewnie znajdzie się ktoś kto przeszukuje pętlą while. Ja skupię się tylko na LINQ oraz pętlach for i foreach.

Do testów użyję BenchmarkDotNet a do zapewnienia losowości danych użyję Bogus. W tym artykule nie zamierzam szerzej omawiać tych bibliotek. Jeśli ich nie znasz to zachęcam do zapoznania się z nimi. Zwłaszcza z BenchmarkDotNet.

Testy

Co prawda większość z nas wie, że najszybsza będzi pętla for. No ale sprawdźmy 🙂 Zamierzam uruchomić testy dla listy zawierającej następującą ilość elementów:

• 10
• 100
• 1000
• 10000
• 100000
• 1000000
• 10000000

Klasa, która zawiera wszystkie nasze testy wygląda następująco:

using System;
using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;
using Bogus;

namespace LinqPerformanceTester
{
    [SimpleJob(targetCount: 5)]
    [MemoryDiagnoser]
    public class CollectionFinderTest
    {
        private IList<Item> _items;

        [Params(10, 100, 1000, 10000, 100000, 1000000, 10000000)]
        public int N;

        [GlobalSetup]
        public void Setup()
        {
            var idx = 0;
            var random = new Bogus.Randomizer();
            _items = new Faker<Item>()
                .RuleFor(x => x.Id, f => idx++)
                .RuleFor(x => x.Name, f => f.Lorem.Word())
                .Generate(N);
        }

        [Benchmark]
        public void ForLoopFindString()
        {
            for (var i = 0; i < _items.Count; i++)
            {
                if (_items[i].Name.Contains("aaa"))
                {
                    return;
                }
            }
        }

        [Benchmark]
        public void ForLoopFindInt()
        {
            for (var i = 0; i < _items.Count; i++)
            {
                if (_items[i].Id == _items.Count - 1)
                {
                    return;
                }
            }
        }

        [Benchmark]
        public void ForEachLoopFindString()
        {
            foreach (var item in _items)
            {
                if (item.Name.Contains("aaa"))
                {
                    return;
                }
            }
        }

        [Benchmark]
        public void ForEachLoopFindInt()
        {
            foreach (var item in _items)
            {
                if (item.Id == _items.Count - 1)
                {
                    return;
                }
            }
        }

        [Benchmark]
        public void LinqFirstOrDefaultFindString()
        {
            _items.FirstOrDefault(x => x.Name.Contains("aaa"));
        }

        [Benchmark]
        public void LinqFirstOrDefaultFindInt()
        {
            _items.FirstOrDefault(x => x.Id == _items.Count - 1);
        }
    }
}

Jak można zauważyć mamy listę obiektów (_items) klasy Item:

public class Item
{
    public int Id { get; set; }
    public string Name { get; set; }
}

Będziemy szukać stringa (Name) lub inta (Id). Nie chodzi mi tutaj o to żeby coś znaleźć ale żeby szukać 🙂 Myślę, że nazwy metod są wystarczającym opisem tego co sprawdzamy w danej metodzie.

Wyniki

Wyniki dla przeszukiwania tablicy po Id:

Wyniki dla przeszukiwania tablicy po Name:

Wnioski

Czas wyszukiwania oraz ilość zaalokowanej pamięci różni się dla poszczególnych metod. Różnice te są mniejsze lub większe w zaleźności od liczby elementów. Tak jak można zauważyć pętla for jest najszybsza i alokuje najmniej pamięci.

Kod źródłowy znajduje się na github https://github.com/letyshub/PerformanceTests