为什么字典比列表快得多？ [英] Why is dictionary so much faster than list?

问题描述

我正在测试从Dictionary VS列表获取数据的速度。

我已使用以下代码进行测试：

I am testing the speed of getting data from Dictionary VS list.
I've used this code to test :

    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。

第一种方法是尝试在机器上花费将近7秒的时间在列表上使用LINQ查找学生的成绩，另一种方法是先将List转换为字典，然后使用键从字典中查找学生的成绩不到一秒钟的时间。

There is list of students and grades in memory they have StudentId in common.
In first way I tried to find Grade of a student using LINQ on a list that takes near 7 seconds on my machine and in another way first I converted List into dictionary then finding grades of student from dictionary using key that takes less than a second .

推荐答案

执行此操作时：

student.Grade = grades.Single（x => x.StudentId == student.Id）.Value;

如所写，它必须枚举整个 List ，直到在列表中找到具有正确的StudentId的条目（条目0是否匹配lambda？否...条目1是否匹配lambda？否...等等）。这是O（n）。既然您对每个学生都做一次，那么它就是O（n ^ 2）。

As written it has to enumerate the entire List until it finds the entry in the List that has the correct studentId (does entry 0 match the lambda? No... Does entry 1 match the lambda? No... etc etc). This is O(n). Since you do it once for every student, it is O(n^2).

但是什么时候这样做：

student.Grade = dic [student.Id];

如果要查找某个通过按字典中的元素，它可以立即跳到字典中的位置-这是O（1）。为每个学生做的O（n）。 （如果您想知道这是怎么做的，Dictionary会对键进行数学运算，将其转换为一个值，该值在Dictionary内的位置，与插入键时的位置相同）

If you want to find a certain element by key in a dictionary, it can instantly jump to where it is in the dictionary - this is O(1). O(n) for doing it for every student. (If you want to know how this is done - Dictionary runs a mathematical operation on the key, which turns it into a value that is a place inside the dictionary, which is the same place it put it when it was inserted)

因此，字典速度更快，因为您使用了更好的算法。

So, dictionary is faster because you used a better algorithm.

这篇关于为什么字典比列表快得多？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！