Vitesse de la fonction d'intersection de tableaux

Question

J'ai écrit une fonction courte pour l'intersection de tableaux et je voulais savoir pourquoi une fonction est plus rapide que l'autre.

1)

Dim list2() As String 'Assume it has values' 
Dim list2length As Integer = list2.length 

Function newintersect(ByRef list1() As String) As String() 
    Dim intersection As New ArrayList 
    If (list1.Length < list2length) Then 
     'use list2' 
     For Each thing As String In list2 
      If (Array.IndexOf(list1, thing) <> -1) Then 
       intersection.Add(thing) 
      End If 
     Next 
    Else 
     'use list1' 
     For Each thing As String In list1 
      If (Array.IndexOf(list2, thing) <> -1) Then 
       intersection.Add(thing) 
      End If 
     Next 
    End If 
    Return intersection 
End Function 

2)

Dim list2() As String 'Assume it has values' 
Dim list2length As Integer = list2.length 

Function newintersect(ByRef list1() As String) As String() 
    Dim intersection As New ArrayList 
    If (list1.Length > list2length) Then 'changed >' 
     'use list2' 
     For Each thing As String In list2 
      If (Array.IndexOf(list1, thing) <> -1) Then 
       intersection.Add(thing) 
      End If 
     Next 
    Else 
     'use list1' 
     For Each thing As String In list1 
      If (Array.IndexOf(list2, thing) <> -1) Then 
       intersection.Add(thing) 
      End If 
     Next 
    End If 
    Return intersection 
End Function 

3)

Dim list2() As String 'Assume it has values' 
Dim list2length As Integer = list2.length 

Function newintersect(ByRef list1() As String) As String() 
    For Each thing As String In list1 
     If (Array.IndexOf(list2, thing) <> -1) Then 
      intersection.Add(thing) 
     End If 
    Next 
    Return intersection 
End Function 

Donc, pour mon testcase, 1 prendre 65 secondes, 3 prend 63 secondes, tandis que 2 prend effectivement 75 secondes Quelqu'un sait pourquoi 3 est le plus rapide? Et pourquoi 1 est plus rapide que 2?

(Désolé pour la mauvaise mise en forme ... ne peut pas sembler coller à droite)

Answer 1

Ce n'est pas vraiment une différence. En outre, il ne semble pas que les méthodes produiraient le même résultat, donc il serait inutile de comparer la performance, non?

Quoi qu'il en soit, le Array.IndexOf n'est pas un moyen très efficace de trouver des articles, et ne se redimensionne pas bien. Vous devriez obtenir une amélioration spectaculaire si vous utilisez une collection basée sur des clés de hachage comme recherche au lieu, quelque chose comme ceci:

Function newintersect(ByRef list1 As String(), ByRef list2 As String()) As String() 
    Dim smaller As HashSet(Of String) 
    Dim larger As String() 
    If list1.Length < list2.Length Then 
    smaller = New HashSet(Of String)(list1) 
    larger = list2 
    Else 
    smaller = New HashSet(Of String)(list2) 
    larger = list1 
    End If 
    Dim intersection As New List(Of String) 
    For Each item As String In larger 
    If smaller.Contains(item) Then 
     intersection.Add(item) 
    End If 
    Next 
    Return intersection.ToArray() 
End Function 

Answer 2

Je vous attends trouveriez que des différents cas de test, vous pouvez inverser les résultats que vous aviez ci-dessus et d'atteindre un situation où 2 est le plus rapide et 1 & 3 sont plus lents.

Il est difficile de commenter sans connaître la composition du cas de test, cela dépendra de l'emplacement des éléments «croisés» dans les deux tableaux - s'ils ont tendance à se rapprocher de l'avant sur un réseau et plus proche à la fin de l'autre, l'ordre d'imbrication de l'itération du tableau/IndexOf aura des performances nettement différentes. BTW - il existe de meilleurs moyens d'effectuer une intersection - trier un ou l'autre tableau et effectuer un BinarySearch est un moyen - en utilisant un dictionnaire (Of String, ...) ou similaire est un autre - et soit se traduirait par loin meilleure performance.

Answer 3

Ceci est de la documentation MSDN

Dim id1() As Integer = {44, 26, 92, 30, 71, 38} 
    Dim id2() As Integer = {39, 59, 83, 47, 26, 4, 30} 

    ' Find the set intersection of the two arrays. 
    Dim intersection As IEnumerable(Of Integer) = id1.Intersect(id2) 

    For Each id As Integer In intersection 
     Debug.WriteLine(id.ToString) 
    Next