사전이 목록보다 훨씬 빠른 이유는 무엇입니까?

사전이 목록보다 훨씬 빠른 이유는 무엇입니까?

---

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를 사전으로 변환 한 다음 1 초도 채 걸리지 않는 키를 사용하여 사전에서 학생의 등급을 찾습니다.

---

이렇게하면 :

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

작성된대로 ListList에서 올바른 studentId를 가진 항목을 찾을 때까지 전체를 열거해야합니다 (항목 0이 람다와 일치합니까? 아니요 ... 항목 1이 람다와 일치합니까? 아니요 ... 등). 이것은 O (n)입니다. 학생 한 명당 한 번씩하기 때문에 O (n ^ 2)입니다.

그러나 이렇게하면 :

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.

---

When using Dictionary you are using a key to retrieve your information, which enables it to find it more efficiently, with List you are using Single Linq expression, which since it is a list, has no other option other than to look in entire list for wanted the item.

---

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

---

Dictionary uses hashing to search for the data. Each item in the dictionary is stored in buckets of items that contain the same hash. It's a lot quicker.

Try sorting your list, it will be a a bit quicker then.

---

A dictionary uses a hash table, it is a great data structure as it maps an input to a corresponding output almost instantaneously, it has a complexity of O(1) as already pointed out which means more or less immediate retrieval.

The cons of it is that for the sake of performance you need lots of space in advance (depending on the implementation be it separate chaining or linear/quadratic probing you may need at least as much as you're planning to store, probably double in the latter case) and you need a good hashing algorithm that maps uniquely your input ("John Smith") to a corresponding output such as a position in an array (hash_array[34521]).

Also listing the entries in a sorted order is a problem. If I may quote Wikipedia:

Listing all n entries in some specific order generally requires a separate sorting step, whose cost is proportional to log(n) per entry.

Have a read on linear probing and separate chaining for some gorier details :)

---

Dictionary is based on a hash table which is a rather efficient algorithm to look up things. In a list you have to go element by element in order to find something.

It's all a matter of data organization...

---

When it comes to lookup of data, a keyed collection is always faster than a non-keyed collection. This is because a non-keyed collection will have to enumerate its elements to find what you are looking for. While in a keyed collection you can just access the element directly via the key.

These are some nice articles for comparing list to dictionary.

Here. And this one.

---

From MSDN - Dictionary mentions close to O(1) but I think it depends on the types involved.

The Dictionary(TKey,TValue) generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table.

Note: The speed of retrieval depends on the quality of the hashing algorithm of the type specified for TKey.

List(TValue) does not implement a hash lookup so it is sequential and the performance is O(n). It also depends on the types involved and boxing/unboxing needs to be considered.

참고URL : https://stackoverflow.com/questions/16977694/why-is-dictionary-so-much-faster-than-list