Performances du dictionnaire (Of String, SomeReferenceType) dans VB.NET

Question

Comment les performances de lecture/ajout de valeurs de/à Dictionary (Of String, SomeReferenceType) dépendent-elles du nombre d'enregistrements déjà entrés? Je veux dire, le temps augmente-t-il en tant que O (1), O (log n), O (n) quand n devient grand, ou d'une autre manière?

Dim index As New Dictionary(Of String, SomeReferenceType) 

' N entries added in a loop 
' ... 

Dim id As Integer = 123456789 ' 9-digit number 
Dim key As String = id.ToString() 
Dim value As New SomeReferenceType 

index(key) = value ' Need to estimate this 
value = index.TryGetValue(key) ' and this operations depending on N (for large N) 

De plus, que se passe-t-il en cas de manque de mémoire? Devrions-nous définir la capacité du dictionnaire avant d'entrer des éléments pour éviter de le copier au cas où il n'y aurait pas assez d'espace mémoire? Combien de temps dure cette opération (copier le dictionnaire à un nouvel endroit si nécessaire) en fonction de N?

Answer 1

Les performances d'obtention d'un article à partir d'un Dictionary sont très peu affectées par le nombre d'articles. Les éléments sont divisés en compartiments correspondant à leur code de hachage, de sorte qu'il n'y a généralement qu'un seul ou très peu d'éléments dans chaque compartiment. L'opération est proche d'une opération O (1). L'ajout d'éléments est également proche d'une opération O (1). Si la capacité doit être augmentée, vous obtiendrez un coup de performance, mais en moyenne, c'est très petit. Comme la capacité double à chaque fois, la quantité de données déplacées lors de l'augmentation de la capacité n'est vraiment pas énorme. Les données sont en moyenne déplacées 1,3 fois plus, donc le travail supplémentaire moyen pour chaque ajout revient à déplacer environ 16 octets.

Si vous connaissez la taille que le Dictionary obtiendra, ou si vous avez juste une estimation décente, vous devriez l'utiliser lorsque vous le créez, pour réduire ou éliminer le besoin d'augmenter la capacité.

Answer 2

Dictionary est implémenté avec Hastables - O (1).

SortedDictionary est mis en oeuvre avec des arbres binaires (rouge/noir) - Ainsi O (log n)

SortedList est implémenté avec des listes + binaires de recherche - Ainsi O (n)

Tous les dictionnaires augmenter leur taille automatiquement (performance est O (n) ici mais cela n'arrive pas souvent car la taille est précalculée intelligemment, donc la performance approximative est O (1) de toute façon - Voir this)

Il suffit de les parcourir et de regarder dans la documentation de Microsoft.