74

我正在测试从 Dictionary VS list 获取数据的速度。
我用这段代码来测试：

    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 转换为字典，然后使用不到一秒的键从字典中查找学生的成绩。 在此处输入图像描述

4

8 回答 8

137

当你这样做时：

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) 为每个学生做这件事。（如果您想知道这是如何完成的 - 字典对键运行数学运算，将其转换为字典内的一个位置的值，与插入时放置的位置相同）

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

于 2013-06-07T06:38:26.730 回答
17

原因是字典是查找，而列表是迭代。

字典使用哈希查找，而您的列表需要遍历列表，直到每次都从开始到结果找到结果。

换一种方式。该列表将比第一项上的字典更快，因为没有什么可查找的。这是第一个项目，繁荣..它完成了。但第二次列表必须查看第一项，然后是第二项。第三次通过它必须查看第一项，然后是第二项，然后是第三项..等等。

所以每次迭代查找需要越来越多的时间。列表越大，所需的时间就越长。虽然字典总是或多或少固定的查找时间（它也会随着字典变大而增加，但速度要慢得多，因此相比之下它几乎是固定的）。

于 2013-06-07T06:43:08.603 回答
11

使用 Dictionary 时，您正在使用一个键来检索您的信息，这使其能够更有效地找到它，而 List 您正在使用Linq 表达式，因为它是一个列表，除了在整个列表中查找想要的Single之外别无选择该项目。

于 2013-06-07T06:37:07.087 回答
9

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

尝试对您的列表进行排序，这样会更快一些。

于 2013-06-07T06:38:10.420 回答
8

字典使用哈希表，它是一个很好的数据结构，因为它几乎可以瞬间将输入映射到相应的输出，它的复杂度为 O(1)，正如已经指出的那样，这意味着或多或少的立即检索。

它的缺点是，为了提高性能，您需要提前大量空间（取决于实现，无论是单独的链接还是线性/二次探测，您可能至少需要与您计划存储的一样多，可能会加倍后一种情况）并且您需要一个良好的散列算法，将您的输入（ ）唯一地映射"John Smith"到相应的输出，例如数组中的位置（hash_array[34521]）。

以排序顺序列出条目也是一个问题。如果我可以引用维基百科：

以某种特定顺序列出所有 n 个条目通常需要一个单独的排序步骤，其成本与每个条目的 log(n) 成正比。

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

于 2013-06-07T12:13:25.353 回答
3

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

这都是数据组织的问题...

于 2013-06-07T06:38:29.043 回答
2

在查找数据时，键控集合总是比非键控集合快。这是因为无键集合必须枚举其元素才能找到您要查找的内容。在键控集合中，您可以直接通过键访问元素。

这些是比较列表和字典的一些不错的文章。

在这里。而这个。

于 2013-06-07T07:00:13.653 回答
0

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

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

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

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

于 2018-08-16T12:32:33.053 回答