Измерение времени поиска в List и SortedDictionary?

Question

[FreeCam]

Здравствуйте, объясните пожалуйста, почему такая разница во времени поиска по списку и по словарю. Что я сделал не так? Данные на картинке при 5000 элементах в коллекции

Comments

[Василий Банников]

Код не смотрел, тк картинки.
Подозреваю, что ты криво измерял.

[oleg_ods]

Попробуй провести измерения с помощью Benchmark.Net

Answer 1

[oleg_ods]

Прогнал тест через BenchmarkDotNet:

public class TestClass
    {
        public static List<int> list = new(Enumerable.Range(0, 1_000_000));
        public static Dictionary<int, int> dict = Enumerable.Range(0, 1_000_000).ToDictionary(x => x, x => x);
        public static SortedDictionary<int, int> sorted = new(Enumerable.Range(0, 1_000_000).ToDictionary(x => x, x => x));

        [Benchmark]
        public void List_First()
        {
            list.Contains(0);
        }

        [Benchmark]
        public void List_Middle()
        {
            list.Contains(500_000);
        }

        [Benchmark]
        public void List_Last()
        {
            list.Contains(1_000_000);
        }

        [Benchmark]
        public void List_NoMatch()
        {
            list.Contains(-1);
        }

        [Benchmark]
        public void Dictionary_First()
        {
            dict.ContainsKey(0);
        }

        [Benchmark]
        public void Dictionary_Middle()
        {
            dict.ContainsKey(500_000);
        }

        [Benchmark]
        public void Dictionary_Last()
        {
            dict.ContainsKey(1_000_000);
        }

        [Benchmark]
        public void Dictionary_NoMatch()
        {
            dict.ContainsKey(-1);
        }

        [Benchmark]
        public void Sorted_First()
        {
            sorted.ContainsKey(0);
        }

        [Benchmark]
        public void Sorted_Middle()
        {
            sorted.ContainsKey(500_000);
        }

        [Benchmark]
        public void Sorted_Last()
        {
            sorted.ContainsKey(1_000_000);
        }

        [Benchmark]
        public void Sorted_NoMatch()
        {
            sorted.ContainsKey(-1);
        }
    }

Результаты:


С List все понятно - используется линейный поиск. Чем дальше в списке находится элемент - тем дольше он ищется. Результат тестов это подтверждает.

Dictionary Source Code.
Если посмотреть реализацию метода ContainsKey видим, что поиск ключа идет по HashCode. То есть обычный Dictionary использует для хранения ключей структуру Хэш-таблица поиск по которой осуществляется очень быстро. В тесте видим, что Dictionary является бесспорным лидером.

SortedDictionary Sorce Code.

Если посмотреть реализацию метода ContainsKey здесь видим, что SortedDictionary хранит ключи с структуре SortedSet.
SortedSet в свою очередь основан на бинарном дереве, то есть для поиска элемента используется алгоритм Бинарного поиска, который работает быстрее чем Линейный, но уступает Хэш-Таблице. Что и подтверждают тесты.

Вывод:
Если нужен быстрый поиск по ключу эффективнее всего использовать коллекцию Dictionary.