C#:为什么字典比列表快得多？

Question

我正在测试从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转换为字典,然后使用不到一秒的密钥从字典中查找学生成绩.

Answer 1

当你这样做:

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

如上所述,它必须枚举整个,List直到它在List中找到具有正确studentId的条目(条目0与lambda匹配？否......条目1是否匹配lambda？否......等等).这是O(n).既然你为每个学生做了一次,那就是O(n ^ 2).

但是当你这样做时:

student.Grade = dic[student.Id];

如果你想在字典中按键找到某个元素,它可以立即跳转到字典中的位置 - 这是O(1).O(n)为每个学生做这件事.(如果你想知道这是怎么做的 - Dictionary对键运行一个数学运算,它将它变成一个值,它是字典里面的一个位置,它与插入时的位置相同)

因此,字典更快,因为您使用了更好的算法.

Answer 2

当使用字典您使用的是钥匙才能检索所需信息,这使它能够更有效地找到它,用列表您使用SingleLINQ的表达,因为它是一个列表,具有比其他没有其他选择,以在整个列表寻找的希望这个项目.

Answer 3

原因是因为字典是查找,而列表是迭代.

Dictionary使用哈希查找,而您的列表需要遍历列表,直到每次从结果开始到结果为止.

换一种方式.该列表将比第一个项目上的字典更快,因为没有任何东西可以查找.这是第一项,热潮......它已经完成了.但第二次列表必须查看第一项,然后是第二项.第三次通过它必须查看第一项,然后第二项,然后第三项......等.

因此,每次迭代查找都会花费越来越多的时间.列表越大,所需的时间越长.虽然字典总是或多或少固定的查找时间(它也随着字典变大而增加,但速度要慢得多,所以通过比较它几乎是固定的).

Answer 4

Dictionary使用散列来搜索数据.字典中的每个项目都存储在包含相同哈希的项目桶中.它快得多.

尝试对列表进行排序,然后会更快一些.

Answer 5

字典使用哈希表,它是一个很好的数据结构,因为它几乎瞬间将输入映射到相应的输出,它具有已经指出的O(1)的复杂性,这意味着或多或少的立即检索.

它的缺点是,为了性能,你需要提前大量的空间(取决于实现,它是单独的链接或线性/二次探测,你可能需要至少与你计划存储的一样多,可能是两倍后一种情况)你需要一个好的散列算法,它将输入("John Smith")唯一映射到相应的输出,例如数组中的位置(hash_array[34521]).

同样按排序顺序列出条目是个问题.如果我引用维基百科:

按特定顺序列出所有n个条目通常需要单独的排序步骤,其成本与每个条目的log(n)成比例.

阅读有关线性探测和单独链接的一些gorier细节:)