C #: perché il dizionario è molto più veloce della lista?

Sto testando la velocità di ottenere dati dalla lista VS del dizionario.
Ho usato questo codice per testare:

internal class Program { private static void Main(string[] args) { var stopwatch = new Stopwatch(); List grades = Grade.GetData().ToList(); List 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 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 ListOfIds=new List(); 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 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 GetStudents() { for (int i = 0; i < 10000; i++) { yield return new Student { Id = GuidHelper.ListOfIds[i], Name = "Name " + i }; } } } 

C’è una lista di studenti e voti in memoria che hanno StudentId in comune.
Nel primo modo ho cercato di trovare il grado di uno studente che utilizza LINQ in una lista che impiega circa 7 secondi sulla mia macchina e in un altro modo ho prima convertito la lista in dizionario e poi trovato i voti degli studenti dal dizionario usando una chiave che impiega meno di un secondo. inserisci la descrizione dell'immagine qui

Quando lo fai:

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

Come scritto, deve enumerare l’intero List finché non trova la voce nella Lista che ha lo studenteId corretto (la voce 0 corrisponde al lambda? No … La voce 1 corrisponde al lambda? No … ecc. Ecc.). Questo è O (n). Dal momento che lo fai una volta per ogni studente, è O (n ^ 2).

Tuttavia quando lo fai:

student.Grade = dic[student.Id];

Se vuoi trovare un determinato elemento per chiave in un dizionario, puoi saltare immediatamente a dove si trova nel dizionario – questo è O (1). O (n) per farlo per ogni studente. (Se vuoi sapere come si fa – Il dizionario esegue un’operazione matematica sulla chiave, che la trasforma in un valore che è una posizione all’interno del dizionario, che è lo stesso posto in cui è stata inserita quando è stata inserita)

Quindi, il dizionario è più veloce perché hai usato un algoritmo migliore.

Quando si utilizza Dizionario si utilizza una chiave per recuperare le informazioni, che consente di trovarla in modo più efficiente, con Elenco si sta utilizzando l’espressione Single Linq, che poiché è un elenco, non ha altra scelta se non quella di cercare l’intero elenco per volevo l’object.

Il motivo è perché un dizionario è una ricerca, mentre una lista è un’iterazione.

Il dizionario usa una ricerca hash, mentre il tuo elenco richiede di scorrere l’elenco fino a quando trova il risultato dall’inizio al risultato ogni volta.

per dirla in un altro modo L’elenco sarà più veloce del dizionario sul primo elemento, perché non c’è nulla da cercare. è il primo object, boom … è fatto. ma la seconda volta la lista deve guardare attraverso il primo object, quindi il secondo elemento. La terza volta deve guardare attraverso il primo object, quindi il secondo elemento, quindi il terzo elemento .. ecc.

Quindi, per ogni iterazione, la ricerca richiede sempre più tempo. Più grande è l’elenco, più tempo è necessario. Mentre il dizionario è sempre un tempo di ricerca più o meno fisso (aumenta anche quando il dizionario diventa più grande, ma a un ritmo molto più lento, quindi al confronto è quasi corretto).

Il dizionario usa l’hashing per cercare i dati. Ogni elemento nel dizionario è memorizzato in contenitori di articoli che contengono lo stesso hash. È molto più veloce.

Prova a ordinare la tua lista, sarà un po ‘più veloce allora.

Un dizionario usa una tabella hash , è una grande struttura dati in quanto mappa un input per un output corrispondente quasi istantaneamente, ha una complessità di O (1) come già sottolineato, il che significa più o meno immediato recupero.

Lo svantaggio è che, per motivi di prestazioni, hai bisogno di molto spazio in anticipo (a seconda dell’implementazione che si tratti di concatenazione separata o sondaggio lineare / quadratico di cui potresti avere bisogno almeno quanto hai intenzione di archiviare, probabilmente raddoppiare il secondo caso) e hai bisogno di un buon algoritmo di hash che mappi in modo univoco il tuo input ( "John Smith" ) su un output corrispondente come una posizione in un array ( hash_array[34521] ).

Anche elencare le voci in un ordine ordinato è un problema. Se posso citare Wikipedia:

L’elencazione di tutte le n voci in un ordine specifico richiede generalmente un passo di ordinamento separato, il cui costo è proporzionale al log (n) per voce.

Dai un’occhiata al sondaggio lineare e al concatenamento separato per alcuni dettagli più ghier 🙂

Il dizionario è basato su una tabella hash che è un algoritmo piuttosto efficiente per cercare le cose. In una lista devi andare elemento per elemento per trovare qualcosa.

È tutta una questione di organizzazione dei dati …

Quando si tratta di cercare i dati, una collezione con chiave è sempre più veloce di una raccolta senza chiave. Questo perché una raccolta non codificata dovrà enumerarne gli elementi per trovare quello che stai cercando. Mentre sei in una collezione con chiave puoi semplicemente accedere all’elemento direttamente tramite la chiave.

Questi sono alcuni buoni articoli per confrontare la lista al dizionario.

Qui E questo.

Da MSDN – Il dizionario parla di O (1) ma penso che dipenda dai tipi coinvolti.

La class generica Dictionary (TKey, TValue) fornisce una mapping da un insieme di chiavi a un insieme di valori. Ogni aggiunta al dizionario consiste in un valore e la sua chiave associata. Recuperare un valore usando la sua chiave è molto veloce, vicino a O (1), perché la class Dictionary è implementata come tabella hash.

Nota: la velocità di recupero dipende dalla qualità dell’algoritmo di hashing del tipo specificato per TKey.

List (TValue) non implementa una ricerca hash, quindi è sequenziale e la performance è O (n). Dipende anche dai tipi coinvolti e dal boxing / unboxing deve essere considerato.