なぜ辞書はリストより速いのか？

疑問点

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を共通に持つ生徒と成績のリストがメモリ上に存在する。

最初の方法で私は私のマシン上で7秒近くかかるリスト上のLINQを使用して学生の成績を見つけることを試み、別の方法で私は最初にリストを辞書に変換し、1秒未満でかかるキーを使用して辞書から生徒の成績を見つけること。 <イグ

どのように解決するには？

こうすると

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

このように書くと、全体の List を列挙する必要があります (エントリ 0 はラムダと一致しますか? いいえ... エントリー1はラムダに一致しますか？いいえ...等々)。これはO(n)です。すべての生徒に対して一度だけ行うので、O(n^2)になります。

しかし、これを実行すると

student.Grade = dic[student.Id];

ある要素を辞書のキーで探したい場合、それが辞書のどこにあるか瞬時にジャンプすることができます - これは O(1) です。すべての生徒に対して行う場合はO(n)です。(これがどのように行われるかを知りたい場合、Dictionary はキーに対して数学的処理を実行し、それを辞書内の場所 (挿入されたときと同じ場所) である値に変えます)。

つまり、辞書が高速なのは、より優れたアルゴリズムを使用したためです。