cref - remarks c#

C#: ¿Por qué el diccionario es mucho más rápido que la lista?

Question

Estoy probando la velocidad de obtención de datos de la lista Dictionary VS.
He usado este código para probar:

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

Hay una lista de estudiantes y calificaciones en memoria que tienen en común StudentId.
Intenté encontrar el grado de un estudiante que utilizaba LINQ en una lista que lleva cerca de 7 segundos en mi máquina y de otra manera primero convertí la Lista en diccionario y luego encontré las calificaciones de los alumnos del diccionario usando una clave que toma menos de un segundo.

Answer 1

Cuando haces esto:

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

Tal como está escrito, tiene que enumerar toda la List hasta que encuentre la entrada en la Lista que tiene el ID de alumno correcto (¿la entrada 0 coincide con la lambda? No ... ¿La entrada 1 coincide con la lambda? No ... etc.). Esto es O (n). Como lo haces una vez por cada alumno, es O (n ^ 2).

Sin embargo, cuando haces esto:

student.Grade = dic[student.Id];

Si desea encontrar un elemento determinado por clave en un diccionario, puede saltar instantáneamente a donde está en el diccionario, esto es O (1). O (n) por hacerlo para cada estudiante. (Si desea saber cómo se hace esto, Dictionary ejecuta una operación matemática en la clave, que lo convierte en un valor que es un lugar dentro del diccionario, que es el mismo lugar donde lo puso cuando se insertó)

Entonces, el diccionario es más rápido porque usaste un mejor algoritmo.

Answer 2

Cuando usa Dictionary está utilizando una clave para recuperar su información, lo que le permite encontrarla de manera más eficiente, con List está utilizando la expresión Single Linq, que como es una lista, no tiene otra opción que no sea buscar en toda la lista de quería el artículo.

Answer 3

El diccionario se basa en una tabla hash que es un algoritmo bastante eficiente para buscar cosas. En una lista, debe ir elemento por elemento para encontrar algo.

Todo es una cuestión de organización de datos ...

Answer 4

El diccionario usa hash para buscar los datos. Cada elemento en el diccionario se almacena en cubos de elementos que contienen el mismo hash. Es mucho más rápido.

Intenta ordenar tu lista, será un poco más rápido entonces.

Answer 5

La razón es porque un diccionario es una búsqueda, mientras que una lista es una iteración.

Dictionary utiliza una búsqueda hash, mientras que su lista requiere recorrer la lista hasta que encuentre el resultado desde el principio hasta el resultado cada vez.

para decirlo de otra manera. La lista será más rápida que el diccionario en el primer elemento, porque no hay nada que buscar. es el primer elemento, boom ... ya está hecho. pero la segunda vez la lista debe mirar el primer elemento, luego el segundo. La tercera vez debe mirar el primer elemento, luego el segundo, luego el tercer elemento ... etc.

Entonces cada iteración la búsqueda toma más y más tiempo. Cuanto más grande es la lista, más tiempo lleva. Mientras que el diccionario siempre es un tiempo de búsqueda más o menos fijo (también aumenta a medida que el diccionario se hace más grande, pero a un ritmo mucho más lento, por lo que, en comparación, es casi fijo).

Answer 6

Cuando se trata de búsqueda de datos, una colección con clave siempre es más rápida que una colección sin clave. Esto se debe a que una colección sin clave tendrá que enumerar sus elementos para encontrar lo que está buscando. Mientras que en una colección con clave puede acceder al elemento directamente a través de la clave.

Estos son algunos artículos agradables para comparar la lista al diccionario.

Aquí . Y este.

Answer 7

Un diccionario utiliza una tabla hash , es una gran estructura de datos, ya que asigna una entrada a un resultado correspondiente casi instantáneamente, tiene una complejidad de O (1) como ya se señaló, lo que significa una recuperación más o menos inmediata.

El inconveniente es que, por el bien del rendimiento, se necesita mucho espacio por adelantado (dependiendo de la implementación, ya sea un encadenamiento separado o un sondeo lineal / cuadrático, puede necesitar al menos tanto como lo que planea almacenar, probablemente el doble en el último caso) y necesita un buen algoritmo hash que asigne exclusivamente su entrada ( "John Smith" ) a una salida correspondiente, como una posición en una matriz ( hash_array[34521] ).

También enumerar las entradas en un orden ordenado es un problema. Si puedo citar Wikipedia:

Enumerar todas las n entradas en un orden específico generalmente requiere un paso de clasificación por separado, cuyo costo es proporcional al registro (n) por entrada.

Lea sobre exploración lineal y encadenamiento separado para obtener más detalles :)