Trouver () contre énumération sur des listes

Question

Je travaille avec une base de code dans laquelle les listes doivent être fréquemment recherchées pour un seul élément.

Est-il plus rapide d'utiliser un prédicat et une recherche () que d'effectuer manuellement une énumération sur la liste?

par exemple:

string needle = "example";
FooObj result = _list.Find(delegate(FooObj foo) {
    return foo.Name == needle;
});

vs.

string needle = "example";
foreach (FooObj foo in _list)
{
    if (foo.Name == needle)
        return foo;
}

Même si leurs fonctionnalités sont équivalentes, leur performance est-elle équivalente?

Answer 1

Ils ne sont pas équivalents en performance. La méthode Find () nécessite une invocation de méthode (dans ce cas, déléguée) pour chaque élément de la liste. L'invocation de méthode n'est pas gratuite et est relativement onéreuse par rapport à une comparaison en ligne. La version foreach ne nécessite aucune invocation de méthode supplémentaire par objet.

Cela étant dit, je ne choisirais ni l'un ni l'autre en fonction des performances tant que je n'aurais pas réellement profilé mon code et constaté qu'il s'agissait d'un problème. Je n'ai pas encore trouvé les frais généraux de ce scénario comme étant un "chemin chaud". problème pour le code que j’ai écrit et j’utilise beaucoup ce motif avec Find et d’autres méthodes similaires.

Answer 2

Si la recherche dans votre liste est trop lente en l'état, vous pouvez probablement faire mieux qu'une recherche linéaire. Si vous pouvez conserver la liste triée, vous pouvez utiliser une recherche binaire pour trouver l’élément en temps O (lg n).

Si vous recherchez un ensemble , envisagez de remplacer cette liste par un dictionnaire pour indexer vos objets par nom.

Answer 3

Techniquement, les performances d'exécution de la version avec délégué seront légèrement moins bonnes que celles de l'autre version, mais dans la plupart des cas, il vous serait difficile de percevoir la moindre différence.

Le plus important (IHMO) est la performance en termes de temps de code permettant d’écrire ce que vous voulez, plutôt que de la façon dont vous le souhaitez. Cela fait une grande différence en termes de maintenabilité.

Ce code original:

string needle = "example";
foreach (FooObj foo in _list)
{
    if (foo.Name == needle)        
        return foo;
}

demande à tout responsable de lire le code et de comprendre que vous recherchez un élément en particulier.

Ce code

string needle = "example";
return _list.Find(
    delegate(FooObj foo) 
    {
        return foo.Name == needle;
    });

indique clairement que vous recherchez un élément en particulier - plus rapide à comprendre.

Enfin, ce code, utilisant les fonctionnalités de C # 3.0:

string needle = "example";
return _list.Find( foo => foo.Name == needle);

fait exactement la même chose, mais sur une ligne encore plus rapide à lire et à comprendre (enfin, une fois que vous avez compris expressions lambda , en tout cas).

En résumé, étant donné que les performances des alternatives sont presque égales, choisissez celle qui facilite la lecture et la maintenance du code.

Answer 4

"Je travaille avec une base de code dans laquelle les listes doivent être recherchées fréquemment pour un seul élément"

".

Il est préférable de modifier votre structure de données en Dictionnaire au lieu de Liste pour obtenir de meilleures performances

Answer 5

Une question similaire a été posée pour List.ForEach contre foreach-iteration ( foreach contre someList.Foreach () {} ).

Dans ce cas, List.ForEach était un peu plus rapide.

Answer 6

Comme Jared l’a souligné, il existe des différences.

Mais, comme toujours, ne vous inquiétez pas, sauf si vous savez que c'est un goulot d'étranglement. Et si c'est un goulot d'étranglement, c'est probablement parce que les listes sont grandes, auquel cas vous devriez envisager d'utiliser une recherche plus rapide - une table de hachage ou une arborescence binaire, ou même simplement de trier la liste et d'effectuer une recherche binaire vous donnera log (n) des performances qui auront bien plus d'impact que de peaufiner votre cas linéaire.