Utilisation de Predicate d'une classe pour la recherche Liste générique - Plus rapide que la boucle?

Question

Disons que nous avons une liste générique de Class1, ayant généralement ~ 100 objets pour une session donnée. Je voudrais voir si la liste a un objet particulier. ASP.NET 2.0 me permet de faire ceci:

Dim objResult as Class1 = objList.Find(objSearch) 

Comment ce taux d'approche par rapport à une traditionnelle boucle For, regardant une perspective de performance?

Comment cela pourrait-il varier avec l'augmentation ou la diminution de la longueur de la liste?

Answer 1

Vous pouvez facilement voir comment .Net List implémente la méthode Find utilisant réflecteur:

Public Function Find(ByVal match As Predicate(Of T)) As T 
    If (match Is Nothing) Then 
     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match) 
    End If 
    Dim i As Integer 
    For i = 0 To Me._size - 1 
     If match.Invoke(Me._items(i)) Then 
      Return Me._items(i) 
     End If 
    Next i 
    Return CType(Nothing, T) 
End Function 

La seule différence entre les deux est que les implémentations Find nécessite un appel à match au lieu d'avoir cette logique inline dans la boucle.

Fait intéressant, cette simple performance:

var persons = new List<Person>(); 
for (int i = 0; i < 100; i++) 
{ 
    persons.Add(new Person { ID = i }); 
} 

GC.Collect(); 
var sw = Stopwatch.StartNew(); 
for (int i = 0; i < 10000000; i++) 
{ 
    persons.Find(person => person.ID == i % 100); 

} 
sw.Stop(); 
Console.WriteLine(sw.Elapsed); 

GC.Collect(); 
sw = Stopwatch.StartNew(); 
for (int i = 0; i < 10000000; i++) 
{ 
    for (int j = 0; j < 100; j++) 
    { 
     if (persons[j].ID == i % 100) 
     { 
      break; 
     } 
    } 
} 
sw.Stop(); 
Console.WriteLine(sw.Elapsed); 

montre que:
Temps total requis pour interroger la liste à l'aide Trouver est 05.7990078 secondes.
Temps total requis pour interroger la liste en utilisant boucle est 06.3551074 secondes.

Ce résultat semble cohérent dans plusieurs exécutions.

Modifier - explication trouvée pour l'avantage de Find:
Find fonctionne plus rapidement car il accède directement au tableau sous-jacent à chaque itération. L'accès à la boucle à travers le List indexeur, ce qui nécessite pour chaque vérification de l'indice d'accès:

Public Default Property Item(ByVal index As Integer) As T 
    Get 
     If (index >= Me._size) Then 
      ThrowHelper.ThrowArgumentOutOfRangeException 
     End If 
     Return Me._items(index) // _items is the underlying array. 
    End Get 

Answer 2

C'est exactement la même chose que le bouclage - c'est ce qu'il fait en interne.

Si votre liste est triée et que vous cherchez une valeur particulière, vous pouvez potentiellement utiliser BinarySearch à la place - mais si vous y pensez, si vous ne savez rien sur le prédicat ou l'ordre des données, a pour parcourir chaque élément jusqu'à ce qu'il trouve une correspondance. Comme il arrive, Find est spécifié pour retourner le premier article dans la liste ... donc il regarde juste dans l'ordre évident. Ceci sera linéaire avec la taille de la liste, c'est-à-dire qu'en moyenne, la recherche d'une liste 10 fois plus grande prendra 10 fois plus de temps. Bien sûr, cela dépend si et où une correspondance est trouvée; Si le premier élément correspond dans tous les cas, il finira dans le même temps quelle que soit la taille de la liste :)

Pour être honnête, avec seulement 100 objets, il semble très peu probable qu'il y ait un goulot d'étranglement.