Why is dictionary so much faster than list?

Unforgiven

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 . enter image description here

Patashu

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.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

Why items method for dictionary is so much faster than a straightforward iteration?

From Dev

Why is a list comprehension so much faster than appending to a list?

From Java

Why is sum so much faster than inject(:+)?

From Dev

why < is much faster than !=?

From Dev

Why is this recursion so much faster than equivalent iteration?

From Dev

Android: why is native code so much faster than Java code

From Dev

Why is memcmp so much faster than a for loop check?

From Dev

Why is my computation so much faster in C# than Python

From Dev

Why is batch mode so much faster than parfor?

From Dev

Why is copying a file in C so much faster than C++?

From Dev

Why is strcmp so much faster than my function?

From Dev

Why is Eigens mean() method so much faster than sum()?

From Dev

Why is linear search so much faster than binary search?

From Dev

Torch: Why is this collate function so much faster than this other one?

From Dev

Why does SSH feel so much faster than HTTP?

From Dev

Why is strcmp so much faster than my function?

From Dev

Why is memcmp so much faster than a for loop check?

From Dev

Why is async code considered so much faster than synchronous?

From Dev

Why is fio seq_writes so much faster than dd?

From Dev

Why list comprehension is much faster than numpy for multiplying arrays?

From Dev

Why list comprehension is much faster than numpy for multiplying arrays?

From Java

Why is [] faster than list()?

From Dev

How is updatedb so much faster than find?

From Dev

Is it faster to search in a dictionary than in a list?

From Dev

Why StringBuilder is much faster than String

From Dev

Why PreparedStatement is much faster than Statement?

From Dev

Why is MacVim much faster than Vim in the Terminal?

From Dev

Why is subplot much faster than figure?

From Dev

Why is `if` so much faster when checked before a statement than after a statement?

Related Related

  1. 1

    Why items method for dictionary is so much faster than a straightforward iteration?

  2. 2

    Why is a list comprehension so much faster than appending to a list?

  3. 3

    Why is sum so much faster than inject(:+)?

  4. 4

    why < is much faster than !=?

  5. 5

    Why is this recursion so much faster than equivalent iteration?

  6. 6

    Android: why is native code so much faster than Java code

  7. 7

    Why is memcmp so much faster than a for loop check?

  8. 8

    Why is my computation so much faster in C# than Python

  9. 9

    Why is batch mode so much faster than parfor?

  10. 10

    Why is copying a file in C so much faster than C++?

  11. 11

    Why is strcmp so much faster than my function?

  12. 12

    Why is Eigens mean() method so much faster than sum()?

  13. 13

    Why is linear search so much faster than binary search?

  14. 14

    Torch: Why is this collate function so much faster than this other one?

  15. 15

    Why does SSH feel so much faster than HTTP?

  16. 16

    Why is strcmp so much faster than my function?

  17. 17

    Why is memcmp so much faster than a for loop check?

  18. 18

    Why is async code considered so much faster than synchronous?

  19. 19

    Why is fio seq_writes so much faster than dd?

  20. 20

    Why list comprehension is much faster than numpy for multiplying arrays?

  21. 21

    Why list comprehension is much faster than numpy for multiplying arrays?

  22. 22

    Why is [] faster than list()?

  23. 23

    How is updatedb so much faster than find?

  24. 24

    Is it faster to search in a dictionary than in a list?

  25. 25

    Why StringBuilder is much faster than String

  26. 26

    Why PreparedStatement is much faster than Statement?

  27. 27

    Why is MacVim much faster than Vim in the Terminal?

  28. 28

    Why is subplot much faster than figure?

  29. 29

    Why is `if` so much faster when checked before a statement than after a statement?

HotTag

Archive