Why is dictionary so much faster than list?

Question

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                              };         }     } } 

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 .

Answer 1

When you do this:

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

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).

However when you do this:

student.Grade = dic[student.Id];

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.

Answer 2

The reason is because a dictionary is a lookup, while a list is an iteration.

Dictionary uses a hash lookup, while your list requires walking through the list until it finds the result from beginning to the result each time.

to put it another way. The list will be faster than the dictionary on the first item, because there's nothing to look up. it's the first item, boom.. it's done. but the second time the list has to look through the first item, then the second item. The third time through it has to look through the first item, then the second item, then the third item.. etc..

So each iteration the lookup takes more and more time. The larger the list, the longer it takes. While the dictionary is always a more or less fixed lookup time (it also increases as the dictionary gets larger, but at a much slower pace, so by comparison it's almost fixed).