Why is dictionary so much faster than list?

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.

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)