C #: Pourquoi le dictionnaire est-il tellement plus rapide que la liste?

Question

Je suis en train de tester la rapidité de l'obtention des données de Dictionnaire VS liste.
J'ai utilisé ce code pour tester :

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

Il y a la liste des étudiants et des grades dans le mémoire qu'ils ont StudentId en commun.
Dans la première méthode, j'ai essayé de trouver de la catégorie d'un élève à l'aide de LINQ sur une liste qui prend près de 7 secondes sur ma machine et d'une autre manière j'ai d'abord convertie en Liste dans le dictionnaire puis la recherche de notes de l'étudiant à partir du dictionnaire à l'aide de la clé qui prend moins d'une seconde .

Answer 1

Lorsque vous faites cela:

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

Comme l'écrit qu'il a à énumérer l'ensemble de l' List jusqu'à ce qu'il trouve l'entrée dans la Liste qui a le bon studentId (ne entrée 0 match le lambda? Non... Ne entrée 1 match le lambda? Non... etc etc). Ce est O(n). Puisque vous le faites une fois pour chaque élève, il est O(n^2).

Cependant, quand vous faites cela:

student.Grade = dic[student.Id];

Si vous voulez trouver un certain élément clé dans un dictionnaire, il peut sauter à l'endroit où il est dans le dictionnaire - c'est O(1). O(n) pour le faire pour tous les élèves. (Si vous voulez savoir comment cela se fait - Dictionnaire exécute une opération mathématique sur la touche, ce qui en fait une valeur qui est un lieu à l'intérieur du dictionnaire, qui est le lieu même de il la mettre quand il a été inséré)

Ainsi, le dictionnaire est plus rapide parce que vous avez utilisé un meilleur algorithme.

Answer 2

La raison en est parce qu'un dictionnaire est une recherche, une liste est une itération.

Dictionnaire utilise un hachage de recherche, tandis que votre liste exige que la marche à travers la liste jusqu'à ce qu'il trouve le résultat à partir de début à la résultat à chaque fois.

pour le dire d'une autre façon. La liste sera plus rapide que le dictionnaire sur le premier élément, car il n'y a rien à regarder. c'est le premier élément, la rampe.. c'est fait. mais la deuxième fois que la liste a de regarder à travers le premier élément, puis le deuxième élément. La troisième fois à travers a de regarder à travers le premier élément, puis le deuxième élément, puis le troisième élément.. etc..

Donc, à chaque itération de la recherche prend de plus en plus de temps. Plus la liste est longue, plus il prend. Alors que le dictionnaire est toujours plus ou moins fixe recherche du temps (il augmente aussi que le dictionnaire devient plus grand, mais à un rythme beaucoup plus lent, donc, par comparaison, il est presque fixe).

Answer 3

Lorsque vous utilisez Dictionnaire, vous utilisez une clé pour extraire vos informations, ce qui lui permet de les retrouver plus efficacement. Avec List, vous utilisez l’expression Single Linq, qui, étant une liste, n’a pas d’autre option que rechercher dans la liste entière pour recherché l'élément.

Answer 4

Le dictionnaire utilise le hachage pour rechercher les données. Chaque élément du dictionnaire est stocké dans des compartiments contenant le même hachage. C'est beaucoup plus rapide.

Essayez de trier votre liste, ce sera un peu plus rapide alors.

Answer 5

Un dictionnaire utilise une table de hachage, c'est une grande structure de données comme les cartes d'une entrée à une sortie correspondante presque instantanément, il a une complexité de O(1) comme l'a déjà souligné ce qui signifie plus ou moins immédiate de la récupération.

Le contre, c'est que pour des raisons de performance, vous avez besoin de beaucoup d'espace à l'avance (en fonction de la mise en œuvre de la part de chaînage ou linéaire/quadratique de sondage vous pouvez avoir besoin d'au moins autant que vous avez l'intention de stocker, probablement le double dans le dernier cas) et vous avez besoin d'un bon algorithme de hachage cartes de manière unique votre entrée ("John Smith") à une sortie correspondante comme une position dans un tableau (hash_array[34521]).

Aussi la liste des entrées dans un ordre de tri est un problème. Si je peut citer Wikipedia:

Liste de tous les n entrées dans certains ordre spécifique nécessite généralement une tri sélectif étape, dont le coût est proportionnel à log(n) par entrée.

À lire sur le sondage linéaire et séparé de chaînage pour certains plus sanglant de détails :)