Подтвердить что ты не робот

С#: Почему словарь намного быстрее, чем список?

Я тестирую скорость получения данных из списка Dictionary VS.
Я использовал этот код для тестирования:

    internal class Program
{
    private static void Main(string[] args)
    {
        var stopwatch = new Stopwatch();
        List<Grade> grades = Grade.GetData().ToList();
        List<Student> students = Student.GetStudents().ToList();

        stopwatch.Start();
        foreach (Student student in students)
        {
            student.Grade = grades.Single(x => x.StudentId == student.Id).Value;
        }
        stopwatch.Stop();
        Console.WriteLine("Using list {0}", stopwatch.Elapsed);
        stopwatch.Reset();
        students = Student.GetStudents().ToList();
        stopwatch.Start();
        Dictionary<Guid, string> dic = Grade.GetData().ToDictionary(x => x.StudentId, x => x.Value);
        foreach (Student student in students)
        {
            student.Grade = dic[student.Id];
        }
        stopwatch.Stop();
        Console.WriteLine("Using dictionary {0}", stopwatch.Elapsed);
        Console.ReadKey();
    }
}

public class GuidHelper
{
    public static List<Guid> ListOfIds=new List<Guid>();

    static GuidHelper()
    {
        for (int i = 0; i < 10000; i++)
        {
            ListOfIds.Add(Guid.NewGuid());
        }
    }
}


public class Grade
{
    public Guid StudentId { get; set; }
    public string Value { get; set; }

    public static IEnumerable<Grade> GetData()
    {
        for (int i = 0; i < 10000; i++)
        {
            yield return new Grade
                             {
                                 StudentId = GuidHelper.ListOfIds[i], Value = "Value " + i
                             };
        }
    }
}

public class Student
{
    public Guid Id { get; set; }
    public string Name { get; set; }
    public string Grade { get; set; }

    public static IEnumerable<Student> GetStudents()
    {
        for (int i = 0; i < 10000; i++)
        {
            yield return new Student
                             {
                                 Id = GuidHelper.ListOfIds[i],
                                 Name = "Name " + i
                             };
        }
    }
}

В памяти есть список учеников и классов, в которых у них есть StudentId.
Сначала я попытался найти класс ученика, использующего LINQ, в списке, который занимает около 7 секунд на моей машине, а другим способом я сначала конвертировал List в словарь, а затем находил классы ученика из словаря, используя ключ, который занимает менее секунды. enter image description here

4b9b3361

Ответ 1

Когда вы это сделаете:

student.Grade = grades.Single(x => x.StudentId == student.Id).Value;

Как указано, он должен перечислить весь List, пока не найдет запись в списке, которая имеет правильный studentId (соответствует ли запись 0 лямбда? Нет... Входит ли запись 1 в лямбда? Нет... и т.д.). Это O (n). Поскольку вы делаете это один раз для каждого ученика, это O (n ^ 2).

Однако, когда вы это делаете:

student.Grade = dic[student.Id];

Если вы хотите найти определенный элемент по ключу в словаре, он может мгновенно перейти туда, где он находится в словаре - это O (1). O (n) для этого для каждого ученика. (Если вы хотите знать, как это делается, словарь выполняет математическую операцию над ключом, что превращает его в значение, которое является местом внутри словаря, которое является тем же местом, которое оно помещало, когда оно было вставлено)

Итак, словарь быстрее, потому что вы использовали лучший алгоритм.

Ответ 2

При использовании словаря вы используете клавишу для получения вашей информации, что позволяет ей находить ее более эффективно, при использовании List вы используете выражение Single Linq, которое, поскольку оно является списком, не имеет другого параметра, кроме просмотра всего списка для требуемого элемента.

Ответ 3

Причина в том, что словарь - это поиск, а список - итерация.

Словарь использует хэш-поиск, в то время как ваш список требует прохода по списку, пока он не найдет результат от начала до результата каждый раз.

чтобы сказать иначе. Список будет быстрее, чем словарь по первому элементу, потому что нечего искать. это первый пункт, бум.. это сделано. но во второй раз список должен просмотреть первый элемент, затем второй элемент. В третий раз через него нужно просмотреть первый элемент, затем второй элемент, затем третий элемент и т.д.

Таким образом, каждая итерация поиска занимает все больше времени. Чем больше список, тем дольше это требуется. Хотя словарь всегда является более или менее фиксированным временем поиска (он также увеличивается по мере увеличения словаря, но гораздо медленнее, поэтому при сравнении он почти фиксируется).

Ответ 4

Словарь использует хеширование для поиска данных. Каждый элемент в словаре хранится в ведрах элементов, которые содержат один и тот же хеш. Это намного быстрее.

Попробуйте отсортировать свой список, это будет немного быстрее.

Ответ 5

В словаре используется хеш-таблица, это отличная структура данных, так как она мгновенно отображает входной сигнал на соответствующий вывод, имеет сложность O (1), как уже указывалось, что означает более или менее непосредственный поиск.

Недостатки этого в том, что для производительности вам нужно много места заранее (в зависимости от реализации, будь то отдельная цепочка или линейное/квадратичное зондирование, вам может понадобиться как минимум столько, сколько вы планируете хранить, вероятно, двойной в последнем случае), и вам нужен хороший алгоритм хэширования, который однозначно отображает ваш вход ("John Smith") на соответствующий вывод, такой как позиция в массиве (hash_array[34521]).

Также перечисление записей в отсортированном порядке является проблемой. Если я могу процитировать Википедию:

Список всех n записей в определенном порядке обычно требует отдельный шаг сортировки, стоимость которого пропорциональна log (n) для каждой записи.

Прочитайте линейное исследование и отдельная цепочка для некоторых деталей gorier:)

Ответ 6

Словарь основан на хеш-таблице, которая является довольно эффективным алгоритмом для поиска вещей. В списке вам нужно пройти элемент за элементом, чтобы что-то найти.

Все дело в организации данных...

Ответ 7

Когда дело доходит до поиска данных, коллекция с ключом всегда быстрее, чем коллекция без ключа. Это связано с тем, что для неквалифицированной коллекции придется перечислить ее элементы, чтобы найти то, что вы ищете. Хотя в коллекции с ключом вы можете просто получить доступ к элементу напрямую с помощью ключа.

Вот несколько хороших статей для сравнения списка со словарем.

Здесь. И этот один.