C＃：为什么字典那么多比单快？ [英] C# : Why is dictionary so much faster than list?

问题描述

我测试从字典VS列表中获取数据的速度。
我用这个code测试：

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共同的列表。
在第一种方式我试图找到使用LINQ列表，花费近7秒我的机器上，并以另一种方式对学生的成绩第一个我转换列表到字典中，然后使用密钥，需要不到一秒钟从字典查找学生的成绩。

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 =＆GT; x.StudentId == student.Id）.value的;

由于写它枚举整个列表，直到它找到具有正确studentId（列表中的条目不进入0匹配拉姆达？不...是否进入1场拉姆达？没有......等等等等）。这是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）做它为每一个学生。 （如果你想知道如何做到这一点 - 字典上运行的关键一数学运算，从而把它变成一个值，该值是字典，这是它把它插入时，它在同一个地方里面的地方）

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.

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