为什么字典比列表快那么多？

Question

我正在测试从字典和列表获取数据的速度。
我使用了以下代码进行测试：

    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转换为字典，使用键从字典中查找学生的成绩，这只需要不到一秒钟。

- Unforgiven

---

你尝试过另一种方式吗？（先使用字典进行测试，然后再使用列表） - Fendy

@Fendy 是的。没有区别。 - Unforgiven

它被称为“Shlemiel the painter's algorithm”（舒列米尔画家算法）。答案解释了其中原因。 - user

了解简单数据结构对编程非常有帮助，建议你阅读一些相关信息。 - Alvin Wong

你知道LINQ的Single方法和Dictionary如何存储数据吗？如果不知道，可以在谷歌上搜索C# List.Single(在MSDN上查找Enumerable.Single)和wiki hash table(Dictionary在底层是一个哈希表)。 - Emperor Orionii

一个更合理的比较应该是字典（key）与列表（index）。 - GameKyuubi

Answer 1

当你这样做：

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

如上写法，它需要枚举整个List直到找到具有正确StudentId的条目（第0个条目是否匹配lambda？否则检查第1个条目是否匹配lambda？以此类推）。 这是O(n)的。 因为您要为每个学生执行一次，所以它是O(n²)。

然而，当你这样做：

student.Grade = dic[student.Id];

如果你想在字典中通过键找到某个元素，则它可以立即跳转到它在字典中的位置-这是O(1)。 为每个学生执行一次O(n)。（如果您想知道如何实现- 字典对键运行数学运算，将其转换为字典内部的一个值，该值与插入时放置在相同位置的值相同）

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

- Patashu

---

另外，因为使用了“Single”，它会持续迭代直到结尾，以确保只存在一个元素（或者找到一个就抛出异常）。 - DaveShaw

这是描述平衡树的一种晦涩的方式，还是这些是不同的算法？不确定是否会混淆问题，但B树意味着O(log n)而不是O(1)。 - Zsolt Szilagyi

在字典中查找元素不是O(1)，平均情况可能是O(log n)。 - Tim B

@TimB 一棵树的深度为log(n)，其中n是元素数量，因此它的时间复杂度是O(log(n))。在哈希表中，你只需要查找一次就能找到它，当然，如果出现拥挤的情况，可能需要检查第二个或第三个位置，但是'缺失'的数量并不取决于n，而是取决于你为哈希表分配了多少空间。 - Patashu

仅提供术语，哈希表的平均成本为O(1)。并非完全是O(1)，这是Patashu所给原因。 - im so confused

Answer 2

字典相对列表更快的原因在于，字典是通过哈希表进行查找，而列表则需要从头到尾逐个遍历查找结果。

换句话说，列表中第一个元素的查找速度要比字典快，因为没有需要查找的内容。也就是说，处理完第一个元素后，任务就完成了。但是，在查找第二个元素时，列表必须先查找第一个元素，再查找第二个元素。在查找第三个元素时，列表必须查找第一个、第二个和第三个元素……以此类推。

因此，每次遍历时，查找所需的时间越来越长。列表越大，花费的时间就越长。而字典始终具有固定的查找时间（虽然随着字典的增大而增加，但增加的速度非常慢，与列表相比几乎可以视为不变）。

- Erik Funkenbusch

Answer 3

使用Dictionary时，您使用键来检索信息，这使得它能够更有效地找到信息。而使用List时，您使用Single Linq表达式，由于它是列表，因此除了在整个列表中查找所需项之外别无选择。

- Ron.B.I

Answer 4

一个字典使用哈希表，它是一种优秀的数据结构，因为它能够将输入映射到相应的输出，几乎可以瞬间完成，它的复杂度已经被指出是O(1)，这意味着检索操作是即时的。

它的缺点在于，为了性能考虑，你需要提前占用大量的空间（取决于具体实现方式，无论是分离链接还是线性/二次探测，你可能需要至少与计划存储的数据量相同的空间，后一种情况可能需要双倍空间），并且你需要一个良好的哈希算法，将你的输入（"John Smith"）唯一地映射到相应的输出，例如数组中的一个位置（hash_array[34521]）。

此外，按排序顺序列出条目也是一个问题。引用维基百科:

按某个特定顺序列出所有n个条目通常需要单独进行排序步骤，其成本与每个条目成比例，即log(n)。

阅读一下线性探测和分离链接的一些更详细的内容 :)

- Nobilis

Answer 5

字典使用哈希搜索数据。字典中的每个项目都存储在包含相同哈希的项目桶中。这样可以更快地进行搜索。

尝试对列表进行排序，这样速度会稍微快一些。

- Quinton Bernhardt

---

你必须说一些关于如何排序列表只有在使用 List<T>.BinarySearch() 这样的东西才有帮助 ;-). (list[list.BinarySearch(new Grade { StudentId = student.Id, }, Comparer<Grade>.Create((a, b) => a.StudentId.CompareTo(b.StudentId)))]) - binki

Answer 6

字典是基于哈希表的，这是一种相当高效的算法来查找内容。在列表中，您必须逐个元素查找以查找内容。

这完全是数据组织的问题...

- JeffRSon

Answer 7

当涉及到数据查找时，键控集合总是比非键控集合更快。这是因为非键控集合将不得不枚举其元素以找到您要查找的内容。而在键控集合中，您可以直接通过键访问元素。

以下是一些比较列表和字典的好文章。 这里。还有这个。

- aiapatag

---

数组和列表也是“键集合”。索引是从[0，n>的键。字典键在域上具有更松散的约束。 - Emperor Orionii

@emperor：所以，如果我知道索引，那么从列表中检索数据的速度...与通过键从字典中检索数据的速度完全相同？ - mike

@mike 实际上它更快。要访问数组的第 105 个元素（列表在内部使用数组），CPU 只需将 (105-1)*元素大小 添加到第一个元素的地址中，就可以获得该元素在内存中的位置。对于字典，它必须计算键的哈希码，从中制作“桶”索引（哈希码％桶数量），并逐个检查桶中的元素以找到具有给定键的元素。字典将元素分配到桶中的方式会影响性能，但在平均情况下，这足以将相同项最小化。 - Emperor Orionii

@emperor：感谢您的澄清，这正是我所期望的；您之前的评论有点让我困惑;o) - mike

Answer 8

来自MSDN - 字典提到了接近O(1)，但我认为这取决于所涉及的类型。

Dictionary(TKey,TValue)泛型类提供了从一组键到一组值的映射。每次添加到字典中都包括一个值及其关联的键。通过使用其键检索值非常快，接近于O(1)，因为Dictionary类是作为哈希表实现的。

注意： 检索速度取决于为TKey指定的类型的哈希算法的质量。

List(TValue)不实现哈希查找，因此它是顺序的，性能为O(n)。它还取决于所涉及的类型和装箱/拆箱需要考虑。

- howserss