Mauvaise implémentation de Enumerable.Single ?

Question

Je suis tombé sur cette implémentation dans Enumerable.cs par reflector.

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    //check parameters
    TSource local = default(TSource);
    long num = 0L;
    foreach (TSource local2 in source)
    {
        if (predicate(local2))
        {
            local = local2;
            num += 1L;
            //I think they should do something here like:
            //if (num >= 2L) throw Error.MoreThanOneMatch();
            //no necessary to continue
        }
    }
    //return different results by num's value
}

Je pense qu'ils devraient interrompre la boucle s'il y a plus de 2 éléments qui répondent à la condition, pourquoi ils bouclent toujours à travers la collection entière ? Dans le cas où le réflecteur désassemble la dll de manière incorrecte, j'ai écrit un test simple :

class DataItem
{
   private int _num;
   public DataItem(int num)
   {
      _num = num;
   }

   public int Num
   {
      get{ Console.WriteLine("getting "+_num); return _num;}
   }
} 
var source = Enumerable.Range(1,10).Select( x => new DataItem(x));
var result = source.Single(x => x.Num < 5);

Pour ce cas de test, je pense qu'il va imprimer "obtenir 0, obtenir 1" et ensuite lancer une exception. Mais en réalité, il affiche "obtenir 0... obtenir 10" et lève une exception. Y a-t-il une raison algorithmique pour laquelle cette méthode est implémentée de cette façon ?

EDIT Certains d'entre vous pensent que c'est à cause les effets secondaires de l'expression du prédicat Après une profonde réflexion et quelques cas d'essai, j'en suis arrivé à la conclusion que les effets secondaires n'ont pas d'importance dans ce cas . Veuillez fournir un exemple si vous n'êtes pas d'accord avec cette conclusion.

Answer 1

Oui, je trouve cela un peu étrange, notamment parce que la surcharge qui ne prend pas de prédicat (c'est-à-dire qui ne fonctionne que sur la séquence) fait semblent avoir l'"optimisation" du lancer rapide.

---

Cependant, pour la défense du BCL, je dirais que la L'exception InvalidOperation que Single lance est une exception stupide qui ne devrait normalement pas être utilisé pour le flux de contrôle. Il n'est pas nécessaire que de tels cas soient optimisés par la bibliothèque.

Le code qui utilise Single où zéro ou plusieurs correspondances sont parfaitement valide possibilité, comme par exemple :

try
{
     var item = source.Single(predicate);
     DoSomething(item);
}

catch(InvalidOperationException)
{
     DoSomethingElseUnexceptional();    
}

doit être refactorisé en code qui n'a pas utiliser l'exception pour le flux de contrôle, comme (seulement un échantillon ; ceci peut être implémenté plus efficacement) :

var firstTwo = source.Where(predicate).Take(2).ToArray();

if(firstTwo.Length == 1) 
{
    // Note that this won't fail. If it does, this code has a bug.
    DoSomething(firstTwo.Single()); 
}
else
{
    DoSomethingElseUnexceptional();
}

---

En d'autres termes, nous devrions laisser l'utilisation de Single aux cas où nous nous attendons à ce que la séquence contienne seulement un match. Il devrait se comporter de manière identique à First mais avec l'ajout de assertion d'exécution que la séquence ne contient pas de correspondances multiples. Comme toute autre assertion, l'échec, c'est-à-dire les cas où Single throws, doivent être utilisés pour représenter les bogues dans le programme (soit dans la méthode qui exécute la requête, soit dans les arguments qui lui sont passés par l'appelant).

Cela nous laisse avec deux cas :

1. L'assertion tient : Il y a une seule correspondance. Dans ce cas, nous voulons Single pour consommer la séquence entière de toute façon pour faire valoir nos droits. Il n'y a aucun avantage à "l'optimisation". En fait, on pourrait dire que l'exemple d'implémentation de l'"optimisation" fourni par le PO sera en fait plus lent à cause de la vérification à chaque itération de la boucle.
2. L'affirmation échoue : Il y a zéro ou plusieurs correspondances. Dans ce cas, nous faire jeter plus tard que nous pourrait mais ce n'est pas si grave puisque l'exception est stupide : c'est le signe d'un bug qui doit être corrigé.

En résumé, si la "mauvaise mise en œuvre" vous pénalise en termes de performances en production, soit.. :

1. Vous utilisez Single incorrectement.
2. Vous avez un bug dans votre programme. Une fois le bogue corrigé, ce problème de performance particulier disparaîtra.

EDIT : J'ai clarifié mon point de vue.

EDIT : Voici un valide l'utilisation de Single, où l'échec indique des bogues dans le en appelant code (mauvais argument) :

public static User GetUserById(this IEnumerable<User> users, string id)
{
     if(users == null)
        throw new ArgumentNullException("users");

     // Perfectly fine if documented that a failure in the query
     // is treated as an exceptional circumstance. Caller's job 
     // to guarantee pre-condition.        
     return users.Single(user => user.Id == id);    
}

Answer 2

Mise à jour :
J'ai reçu de très bons commentaires sur ma réponse, qui m'ont fait réfléchir. Je vais donc d'abord fournir la réponse qui expose mon "nouveau" point de vue ; vous pouvez toujours trouver ma réponse originale juste en dessous. Assurez-vous de lire les commentaires entre les deux pour comprendre où ma première réponse n'est pas pertinente.

Nouvelle réponse :

Supposons que Single doit lever une exception lorsque sa condition préalable n'est pas remplie, c'est-à-dire lorsque Single détecte que soit aucun, soit plus d'un élément de la collection correspond au prédicat.

Single ne peut réussir sans lever d'exception qu'en parcourant l'ensemble de la collection. Il doit s'assurer qu'il y a exactement un élément correspondant, il devra donc vérifier tous les éléments de la collection.

Cela signifie que le lancement précoce d'une exception (dès qu'il trouve un deuxième élément correspondant) est essentiellement une optimisation dont vous ne pouvez bénéficier que lorsque Single Si la condition préalable de l'utilisateur ne peut pas être remplie, une exception sera levée.

Comme le dit clairement l'utilisateur CodeInChaos dans un commentaire ci-dessous, l'optimisation ne serait pas mauvaise, mais elle n'a pas de sens, car on introduit généralement des optimisations qui profiteront à un code qui fonctionne correctement, et non des optimisations qui profiteront à un code qui fonctionne mal.

Ainsi, il est en fait correct que Single pourrait lever une exception prématurément, mais il n'est pas nécessaire de le faire, car il n'y a pratiquement aucun avantage supplémentaire.

---

Vieille réponse :

Je ne peux pas donner de raison technique por qué cette méthode est implémentée comme elle l'est, puisque je ne l'ai pas implémentée. Mais je peux affirmer ma compréhension de la Single de l'opérateur objectif et j'en tire la conclusion personnelle qu'il est effectivement mal mis en œuvre :

Ma compréhension de Single :

Quel est le but de Single et quelle est la différence avec, par exemple, l'utilisation d'une carte de crédit. First o Last ?

Utilisation de la Single exprime fondamentalement l'hypothèse que l'on doit retourner exactement un élément de la collection :

• Si vous ne spécifiez pas de prédicat, cela signifie que la collection doit contenir exactement un élément.

• Si vous spécifiez un prédicat, cela signifie qu'un seul élément de la collection doit satisfaire à cette condition. (L'utilisation d'un prédicat devrait avoir le même effet que items.Where(predicate).Single() .)

C'est ce qui rend Single différent d'autres opérateurs tels que First , Last o Take(1) . Aucun de ces opérateurs n'exige qu'il y ait exactement un article (correspondant).

Quand faut-il Single lancer une exception ?

En fait, lorsqu'il constate que votre hypothèse était erronée, c'est-à-dire lorsque la collection sous-jacente est no donnent exactement un élément (correspondant). C'est-à-dire lorsqu'il y a zéro ou plus d'un élément.

Quand faut-il Single être utilisé ?

L'utilisation de Single est approprié lorsque la logique de votre programme peut garantir que la collection donnera exactement un élément, et un seul. Si une exception est levée, cela signifie que la logique de votre programme contient un bug.

Si vous traitez des collections "peu fiables", telles que les entrées E/S, vous devez d'abord valider les entrées avant de les transmettre à l'application Single . Single ainsi qu'une exception catch bloc, est no approprié pour s'assurer que la collection n'a qu'un seul élément correspondant. Au moment où vous invoquez Single vous devriez déjà ont fait en sorte qu'il n'y ait qu'un seul article correspondant.

Conclusion :

Ce qui précède indique ma compréhension de la Single Opérateur LINQ. Si vous suivez et êtes d'accord avec cette compréhension, vous devriez arriver à la conclusion que Single devrait lever une exception le plus tôt possible . Il n'y a aucune raison d'attendre jusqu'à la fin de la collection (qui peut être très grande), car la pré-condition de Single est violée dès qu'elle détecte un deuxième élément (correspondant) dans la collection.

Answer 3

Lorsque l'on considère cette implémentation, il faut se rappeler qu'il s'agit de la BCL : un code général qui est censé fonctionner correctement. assez de dans toutes sortes de scénarios.

D'abord, prenez ces scénarios :

1. Itérer sur 10 nombres, où le premier et le second élément sont égaux.
2. Itérer sur 1.000.000 de nombres, où le premier et le troisième élément sont égaux.

L'algorithme original fonctionnera assez bien pour 10 éléments, mais 1M aura un sérieux gaspillage de cycles. Donc dans ces cas où nous savons qu'il y a deux ou plusieurs débuts de séquences, l'optimisation proposée aurait un bel effet.

Ensuite, examinez ces scénarios :

1. Itérer sur 10 nombres, où le premier et le dernier élément sont égaux.
2. Itérer sur 1.000.000 de nombres, où le premier et le dernier élément sont égaux.

Dans ces scénarios, l'algorithme doit toujours inspecter chaque élément des listes. Il n'y a pas de raccourci. L'algorithme original aura de bonnes performances assez de il remplit le contrat. Changer l'algorithme, introduire un if à chaque itération va en fait diminuer performance. Pour 10 articles, ce sera négligeable, mais pour 1M, ce sera un gros coup.

Selon moi, l'implémentation originale est la bonne, car elle est suffisante pour la plupart des scénarios. Connaissant l'implémentation de Single est cependant une bonne chose, car elle nous permet de prendre des décisions intelligentes sur la base de ce que nous savons des séquences sur lesquelles nous l'utilisons. Si les mesures de performance dans un scénario particulier montrent que Single est à l'origine d'un goulot d'étranglement, eh bien : nous pouvons alors mettre en œuvre notre propre variante qui fonctionne mieux dans ce scénario particulier .

Mise à jour : comme CodeInChaos y Eamon ont correctement souligné, le if test introduit dans l'optimisation est en effet no effectuée sur chaque élément, uniquement dans le bloc de correspondance des prédicats. Dans mon exemple, j'ai complètement négligé le fait que les modifications proposées n'affecteront pas les performances globales de l'implémentation.

Je conviens que l'introduction de l'optimisation serait probablement bénéfique pour tous les scénarios. Mais il est bon de voir qu'en fin de compte, la décision de mettre en œuvre l'optimisation est prise sur la base de mesures des performances.

Answer 4

Je pense que c'est un "bug" d'optimisation prématurée.

Pourquoi ce n'est PAS un comportement raisonnable en raison des effets secondaires.

Certains ont fait valoir qu'en raison des effets secondaires, on devrait s'attendre à ce que la liste entière soit évaluée. Après tout, dans le cas correct (la séquence n'a en effet qu'un seul élément), elle est complètement énumérée, et pour des raisons de cohérence avec ce cas normal, il est plus agréable d'énumérer la séquence entière dans la fonction tous cas.

Bien que cet argument soit raisonnable, il va à l'encontre de la pratique générale des bibliothèques LINQ : elles utilisent partout l'évaluation paresseuse. C'est no L'énumération complète des séquences n'est pas une pratique générale, sauf en cas de nécessité absolue. IList.Count lorsqu'elle est disponible sur n'importe quelle itération - même si cette itération peut avoir des effets secondaires.

Plus loin, .Single() sans Le prédicat ne présente pas ce comportement : il se termine dès que possible. Si l'argument était que .Single() doit respecter les effets secondaires de l'énumération, on peut s'attendre à ce que toutes les surcharges le fassent de manière équivalente.

Pourquoi les arguments en faveur de la vitesse ne tiennent pas

Peter Lillevold a fait l'observation intéressante qu'il pourrait être plus rapide de faire...

foreach(var elem in elems)
    if(pred(elem)) {
        retval=elem;
        count++;
    }
if(count!=1)...

que

foreach(var elem in elems)
    if(pred(elem)) {
        retval=elem;
        count++;
        if(count>1) ...
    }
if(count==0)...

Après tout, la deuxième version, qui sortirait de l'itération dès que le premier conflit est détecté, nécessiterait un test supplémentaire dans la boucle - un test qui, dans le "correct", est purement du lest. Belle théorie, non ?

Sauf que, ce n'est pas bourré de chiffres ; par exemple sur ma machine (YMMV) Enumerable.Range(0,100000000).Where(x=>x==123).Single() est en fait plus rapide que Enumerable.Range(0,100000000).Single(x=>x==123) !

Il s'agit peut-être d'une bizarrerie du JITter pour cette expression précise sur cette machine. Where suivi de sans prédicat Single est toujours plus rapide.

Mais quoi qu'il en soit, il est très peu probable que la solution "fail-fast" soit significativement plus lente. Après tout, même dans le cas normal, nous avons affaire à une branche bon marché : une branche qui est jamais pris et donc facile pour le prédicteur de branche. Et bien sûr, la branche n'est plus jamais rencontrée que lorsque pred tient - c'est-à-dire une fois par appel dans le cas normal. Ce coût est tout simplement négligeable par rapport au coût de l'appel au délégué. pred et sa mise en œuvre, plus le coût des méthodes de l'interface .MoveNext() y .get_Current() et leurs mises en œuvre.

Il est tout simplement très peu probable que vous remarquiez la dégradation des performances causée par une branche prévisible par rapport à toutes les autres pénalités d'abstraction, sans parler du fait que la plupart des séquences et des prédicats font eux-mêmes quelque chose.

Answer 5

Cela me semble très clair.

Single est prévu pour le cas où l'appelant sait que l'énumération contient exactement une correspondance, car dans tout autre cas, une exception coûteuse est levée.

Pour ce cas d'utilisation, la surcharge qui prend un prédicat doit itérer sur l'ensemble de l'énumération. Il est légèrement plus rapide de le faire sans une condition supplémentaire sur chaque boucle.

À mon avis, l'implémentation actuelle est correcte : elle est optimisée pour le cas d'utilisation attendu d'une énumération qui contient exactement un élément correspondant.