Cyclisme à travers un SortedList - Pourquoi est-ce plus rapide?

Question

Liste1 dans l'exemple suivant est un SortedList (de MyClass) et contient 251 membres.

Les deux premiers codeblocks exécutent en 15,5 secondes.

 For cnt As Integer = 1 To 1000000
        For Each TempDE In List1
            Dim F As String = TempDE.Key
            TempDE.Value.x1 = 444
        Next
    Next

    For cnt As Integer = 1 To 1000000
        For Each TempDE As KeyValuePair(Of String, phatob) In List2
            Dim F As String = TempDE.Key
            TempDE.Value.x1 = 444
        Next
    Next

Celui-ci exécute en 5,6 secondes.

    For cnt As Integer = 0 To 999999
        For cnt2 As Integer = 0 To 250
            Dim F As String = List1.Keys(cnt2)
            List1.Values(cnt2).x1 = 444
        Next

    Next

Pourquoi les deux premiers codeblocks tellement plus lent?

Answer 1

Le SortedList étend une collection en mettant en œuvre IComparer pour fournir la fonctionnalité de tri. En interne, il met en œuvre 2 tableaux pour stocker les éléments de la liste - un tableau pour la clé et une pour les valeurs. Le tableau .NET est optimisé pour rapidement dans l'ordre et un accès rapide au hasard.

Je soupçonne pourquoi les 2 premiers sont lents parce que l'instruction foreach dans un SortedList est une enveloppe autour du recenseur. foreach appelant interrogera le recenseur, appelez MoveNext et actuel. En outre, bien que la liste va générique peut potentiellement impliquer la boxe et unboxing que vous traversez la liste, et peut créer des frais généraux de performance que vous ne feriez pas normalement obtenir en accédant par Index.

Answer 2

J'ai essayé de regarder autour de la documentation sur exactement comment se comporte For Each, mais je ne pouvais pas le trouver.

Ma théorie est que l'utilisation des déclarations de copies For Each l'objet dans la liste à un autre endroit en mémoire puis copie de nouveau dans la liste lorsque chaque itération de la boucle se termine.

Une autre possibilité est qu'il appelle le constructeur au début de chaque itération et déconstruit alors et appelle le constructeur à nouveau pour réinitialiser la prochaine itération.

Je ne suis pas sûr de l'une de ces théories, mais la différence majeure entre 3 et (1 ou 2) est le manque de For Each.

EDIT:. Trouvé la documentation MSDN

Voici un extrait:

  

Lors de l'exécution de la boucle For Each ... Next commence, Visual Basic vérifie que le groupe fait référence à un objet de collection valide. Dans le cas contraire, il jette une exception. Dans le cas contraire, il appelle la méthode MoveNext et la propriété actuelle de l'objet recenseur pour renvoyer le premier élément. Si MoveNext indique qu'il n'y a pas d'élément suivant, à savoir, si la collection est vide, la boucle For Each et se termine le contrôle passe à l'instruction suivant l'instruction suivante. Dans le cas contraire, l'élément fixe Visual Basic au premier élément et exécute le bloc d'instructions.

Donc dans l'ensemble il semble que For Each est plus « géré » et fait beaucoup de frais généraux pour vous assurer que tout correspond en place. Par conséquent, il est plus lent.

Answer 3

Je pense que le compilateur peut mieux optimiser le bloc 3 en raison de la plage de boucle fixe. Dans les blocs 2 et un compilateur ne saurez pas ce que la limite supérieure de la boucle est jusqu'à ce qu'il évalue la liste permettant ainsi plus lent.

Answer 4

Je pense au hasard: List1 contient ~ 750 éléments (et non seulement 250). Votre troisième cas est plus rapide, car il n'itérer pas sur chaque élément qui a Liste1.