c# - example - Mala implementación de Enumerable.Single?

select linq c# example

Question

Me encontré con esta implementación en Enumerable.cs por 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
}

Creo que deberían romper el ciclo si hay más de 2 elementos que cumplan con la condición, ¿por qué siempre recorren toda la colección? En caso de que ese reflector desmonte incorrectamente el dll, escribo una prueba 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);

Para este caso de prueba, creo que se imprimirá "obteniendo 0, obteniendo 1" y luego lanzará una excepción. Pero la verdad es que sigue "recibiendo 0 ... obteniendo 10" y arroja una excepción. ¿Hay alguna razón algorítmica para implementar este método como este?

EDITAR Algunos de ustedes pensaron que era debido a los efectos secundarios de la expresión del predicado , después de un pensamiento profundo y algunos casos de prueba, tengo la conclusión de que los efectos secundarios no importan en este caso . Por favor dé un ejemplo si no está de acuerdo con esta conclusión.

Answer 1

Actualizar:
Obtuve muy buenos comentarios a mi respuesta, lo que me hizo repensar. Por lo tanto, primero proporcionaré la respuesta que establece mi "nuevo" punto de vista; aún puedes encontrar mi respuesta original justo debajo. Asegúrese de leer los comentarios intermedios para entender dónde mi primera respuesta falla.

Nueva respuesta:

Supongamos que Single debe lanzar una excepción cuando su condición previa no se cumple; es decir, cuando Single detecta que ninguno o más de un elemento en la colección coincide con el predicado.

Single puede tener éxito sin lanzar una excepción al recorrer toda la colección. Tiene que asegurarse de que haya exactamente un elemento coincidente, por lo que deberá verificar todos los elementos de la colección.

Esto significa que lanzar una excepción anticipadamente (tan pronto como encuentra un segundo elemento coincidente) es esencialmente una optimización de la que solo puede beneficiarse cuando no se puede cumplir la condición previa de Single y cuando lanza una excepción.

Como el usuario CodeInChaos dice claramente en un comentario a continuación, la optimización no sería incorrecta, pero no tiene sentido, porque uno generalmente introduce optimizaciones que beneficiarán al código de trabajo correcto, no optimizaciones que beneficiarán al código que no funciona bien.

Por lo tanto, en realidad es correcto que Single podría lanzar una excepción temprano; pero no tiene porque, porque prácticamente no hay ningún beneficio adicional.

Respuesta anterior:

No puedo dar una razón técnica por la que ese método se implemente de la manera en que es, ya que no lo implementé. Pero puedo expresar mi comprensión del propósito del operador Single , y de ahí sacar mi conclusión personal de que, de hecho, está mal implementado:

Mi entendimiento de Single :

¿Cuál es el propósito de Single , y cómo es diferente de, por ejemplo, First or Last ?

Usar el operador Single básicamente expresa la suposición de que exactamente un ítem debe ser devuelto de la colección:

• Si no especifica un predicado, debería significar que se espera que la colección contenga exactamente un elemento.

• Si especifica un predicado, debería significar que se espera que exactamente un elemento en la colección satisfaga esa condición. (Usar un predicado debe tener el mismo efecto que los items.Where(predicate).Single() .

Esto es lo que hace que Single sea ​​diferente de otros operadores, como First , Last o Take(1) . Ninguno de esos operadores tiene el requisito de que debe haber exactamente un elemento (coincidente).

¿Cuándo debe Single lanzar una excepción?

Básicamente, cuando encuentra que su suposición fue incorrecta; es decir, cuando la colección subyacente no produce exactamente un elemento (coincidente). Es decir, cuando hay cero o más de un elemento.

¿Cuándo se debe usar Single ?

El uso de Single es apropiado cuando la lógica de su programa puede garantizar que la colección arroje exactamente un elemento y un solo artículo. Si se lanza una excepción, eso debería significar que la lógica de su programa contiene un error.

Si procesa colecciones "no confiables", como entradas de E / S, primero debe validar la entrada antes de pasarla a Single . Single , junto con un bloque catch excepción, no es apropiado para asegurarse de que la colección solo tenga un elemento coincidente. Para cuando invoque Single , ya debería haberse asegurado de que solo haya un elemento coincidente.

Conclusión:

Lo anterior indica mi comprensión del operador Single LINQ. Si sigue y está de acuerdo con este entendimiento, debe llegar a la conclusión de que Single debe emitir una excepción lo antes posible . No hay ninguna razón para esperar hasta el final de la colección (posiblemente muy grande), ya que se viola la condición previa de Single tan pronto como detecta un segundo elemento (coincidente) en la colección.

Answer 2

Al considerar esta implementación, debemos recordar que este es el BCL: código general que se supone que funciona lo suficientemente bien en todo tipo de escenarios.

Primero, tome estos escenarios:

1. Iterar más de 10 números, donde el primer y el segundo elemento son iguales
2. Iterar más de 1.000.000 de números, donde el primer y el tercer elemento son iguales

El algoritmo original funcionará lo suficientemente bien para 10 elementos, pero 1M tendrá una pérdida severa de ciclos. Entonces, en estos casos donde sabemos que hay dos o más al principio de las secuencias, la optimización propuesta tendría un buen efecto.

Luego, mira estos escenarios:

1. Iterar más de 10 números, donde el primer y el último elemento son iguales
2. Iterar más de 1.000.000 de números, donde el primer y el último elemento son iguales

En estos escenarios, el algoritmo sigue siendo necesario para inspeccionar cada elemento en las listas. No hay ningún atajo. El algoritmo original funcionará lo suficientemente bien, cumple con el contrato. Cambiar el algoritmo, introducir un if en cada iteración en realidad reducirá el rendimiento. Para 10 elementos será insignificante, pero 1M será un gran éxito.

IMO, la implementación original es la correcta, ya que es lo suficientemente buena para la mayoría de los escenarios. Sin embargo, conocer la implementación de Single es bueno, porque nos permite tomar decisiones inteligentes basadas en lo que sabemos sobre las secuencias en las que lo usamos. Si las mediciones de rendimiento en un escenario en particular muestran que Single está causando un cuello de botella, entonces: podemos implementar nuestra propia variante que funcione mejor en ese escenario particular .

Actualización: como CodeInChaos y Eamon han señalado correctamente, la prueba if introducida en la optimización no se realiza en cada elemento, solo dentro del bloque de coincidencia de predicados. En mi ejemplo, he pasado por alto por completo el hecho de que los cambios propuestos no afectarán el rendimiento general de la implementación.

Estoy de acuerdo con que la introducción de la optimización probablemente beneficie todos los escenarios. Sin embargo, es bueno ver que, finalmente, la decisión de implementar la optimización se basa en mediciones de rendimiento.

Answer 3

Creo que es un "error" de optimización prematura.

Por qué esto NO es un comportamiento razonable debido a los efectos secundarios

Algunos han argumentado que debido a los efectos secundarios, se debe esperar que se evalúe toda la lista. Después de todo, en el caso correcto (la secuencia de hecho tiene solo 1 elemento) está completamente enumerado, y por coherencia con este caso normal, es más agradable enumerar la secuencia completa en todos los casos.

A pesar de que es un argumento razonable, va en contra de la práctica general en todas las bibliotecas de LINQ: usan evaluaciones perezosas en todas partes. No es una práctica general enumerar por completo las secuencias, excepto cuando sea absolutamente necesario; de hecho, varios métodos prefieren usar IList.Count cuando esté disponible en cualquier iteración, incluso cuando esa iteración pueda tener efectos secundarios.

Además, .Single() sin predicado no muestra este comportamiento: eso termina tan pronto como sea posible. Si el argumento fuera que .Single() debería respetar los efectos secundarios de la enumeración, esperaría que todas las sobrecargas lo hicieran de manera equivalente.

Por qué el caso de la velocidad no se sostiene

Peter Lillevold hizo la interesante observación de que puede ser más rápido ...

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)...

Después de todo, la segunda versión, que saldría de la iteración tan pronto como se detecte el primer conflicto, requeriría una prueba adicional en el circuito, una prueba que en el "correcto" es puramente lastre. Teoría limpia, ¿verdad?

Excepto, eso no es una bourne por los números; por ejemplo, en mi máquina (YMMV) Enumerable.Range(0,100000000).Where(x=>x==123).Single() es en realidad más rápido que Enumerable.Range(0,100000000).Single(x=>x==123) !

Es posiblemente una peculiaridad JETter de esta expresión precisa en esta máquina. No estoy afirmando que Where seguido por Single predicado sea siempre más rápido.

Pero sea cual sea el caso, la solución a prueba de fallas es muy poco probable que sea significativamente más lenta. Después de todo, incluso en el caso normal, se trata de una sucursal barata: una sucursal que nunca se toma y, por lo tanto, es fácil para el pronosticador de bifurcación. Y por supuesto; la rama solo se encuentra cuando se tiene pred - es decir, una vez por llamada en el caso normal. Ese costo es simplemente insignificante comparado con el costo de la llamada de delegado pred y su implementación, más el costo de los métodos de interfaz .MoveNext() y .get_Current() y sus implementaciones.

Es muy poco probable que notes la degradación del rendimiento causada por una rama predecible en comparación con toda esa otra penalización de abstracción, por no mencionar el hecho de que la mayoría de las secuencias y los predicados realmente hacen algo ellos mismos.

Answer 4

Eso parece ser una mala implementación, en mi opinión.

Solo para ilustrar la posible gravedad del problema:

var oneMillion = Enumerable.Range(1, 1000000)
                           .Select(x => { Console.WriteLine(x); return x; });

int firstEven = oneMillion.Single(x => x % 2 == 0);

Lo anterior generará todos los enteros de 1 a 1000000 antes de lanzar una excepción.

Es un rascador de cabeza seguro.

Answer 5

Me parece muy claro.

Single está destinado para el caso en que la persona que llama sabe que la enumeración contiene exactamente una coincidencia, ya que en cualquier otro caso se lanza una excepción costosa.

Para este caso de uso, la sobrecarga que toma un predicado debe iterar sobre toda la enumeración. Es un poco más rápido hacerlo sin una condición adicional en cada ciclo.

En mi opinión, la implementación actual es correcta: está optimizada para el caso de uso esperado de una enumeración que contiene exactamente un elemento coincidente.

Answer 6

Sí, lo encuentro un poco extraño, especialmente porque la sobrecarga que no toma un predicado (es decir, funciona solo en la secuencia) parece tener la ''optimización'' de tiro rápido.

Sin embargo, en la defensa del BCL, diría que la excepción InvalidOperation que Single throws es una excepción que normalmente no debería usarse para control-flow. No es necesario que la biblioteca optimice estos casos.

El código que usa Single donde cero o múltiples coincidencias es una posibilidad perfectamente válida , como por ejemplo:

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

catch(InvalidOperationException)
{
     DoSomethingElseUnexceptional();    
}

se debe refactorizar a un código que no use la excepción para control-flow, como (solo una muestra; esto se puede implementar de manera más eficiente):

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 otras palabras, deberíamos dejar el uso de Single a los casos cuando esperamos que la secuencia contenga solo una coincidencia. Debería comportarse de manera idéntica a First pero con la afirmación adicional en tiempo de ejecución de que la secuencia no contiene múltiples coincidencias. Al igual que cualquier otra aseveración, la falla, es decir, los casos en los que Single lanza, se deben usar para representar errores en el programa (ya sea en el método que ejecuta la consulta o en los argumentos que le pasa la persona que llama).

Esto nos deja con dos casos:

1. La afirmación es válida: hay una sola coincidencia. En este caso, queremos que Single consuma toda la secuencia de todos modos para afirmar nuestro reclamo. No hay beneficio para la ''optimización''. De hecho, se podría argumentar que la implementación de la muestra de la ''optimización'' proporcionada por el OP será en realidad más lenta debido a la comprobación en cada iteración del ciclo.
2. La afirmación falla: hay cero o múltiples coincidencias. En este caso, tiramos más tarde de lo que pudimos , pero esto no es tan importante ya que la excepción es descabellada: es indicativo de un error que debe corregirse.

En resumen, si la "implementación deficiente" le está mordiendo en lo que respecta al rendimiento en la producción, ya sea:

1. Está utilizando el Single incorrectamente.
2. Usted tiene un error en su programa. Una vez que se corrige el error, este problema particular de rendimiento desaparecerá.

EDITAR: Aclaró mi punto.

EDITAR: Aquí hay un uso válido de Single, donde la falla indica errores en el código de llamada (argumento malo):

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 7

Solo encontré esta pregunta después de presentar un informe en https://connect.microsoft.com/VisualStudio/feedback/details/810457/public-static-tsource-single-tsource-this-ienumerable-tsource-source-func-tsource-bool-predicate-doesnt-throw-immediately-on-second-matching-result#

El argumento del efecto secundario no se cumple, porque:

1. Tener efectos secundarios no es realmente funcional, y se llaman Func por una razón.
2. Si desea efectos secundarios, no tiene más sentido afirmar que la versión que tiene los efectos secundarios durante toda la secuencia es deseable, y no lo es para la versión que se lanza inmediatamente.
3. No coincide con el comportamiento de First o la otra sobrecarga de Single .
4. No coincide con al menos algunas otras implementaciones de Single , por ejemplo, Linq2SQL utiliza TOP 2 para garantizar que solo se devuelvan los dos casos coincidentes necesarios para probar más de una coincidencia.
5. Podemos construir casos donde deberíamos esperar que un programa se detenga, pero no se detiene.
6. Podemos construir casos donde se lanza OverflowException , que no es un comportamiento documentado, y por lo tanto claramente un error.

Lo más importante de todo, si estamos en una condición donde esperábamos que la secuencia tuviera solo un elemento coincidente, y aún no lo estamos, entonces algo claramente ha salido mal. Además del principio general de que lo único que debe hacer al detectar un estado de error es la limpieza (y esta implementación lo retrasa) antes de lanzar, el caso de una secuencia que tenga más de un elemento coincidente se solapará con el caso de una secuencia que tiene más elementos en total de lo esperado, tal vez porque la secuencia tiene un error que hace que se repita inesperadamente. Por lo tanto, es precisamente en un conjunto posible de errores que debe desencadenar la excepción, que la excepción se retrasa más.

Editar:

La mención de Peter Lillevold de una prueba repetida puede ser una de las razones por las cuales el autor optó por adoptar el enfoque que utilizaron, como una optimización para el caso no excepcional. De ser así, era innecesario, incluso aparte de Eamon Nerbonne, que demostraba que no mejoraría mucho. No es necesario tener una prueba repetida en el ciclo inicial, ya que podemos cambiar lo que estamos probando en el primer partido:

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
  if(source == null)
    throw new ArgumentNullException("source");
  if(predicate == null)
    throw new ArgumentNullException("predicate");
  using(IEnumerator<TSource> en = source.GetEnumerator())
  {
    while(en.MoveNext())
    {
      TSource cur = en.Current;
      if(predicate(cur))
      {
        while(en.MoveNext())
          if(predicate(en.Current))
            throw new InvalidOperationException("Sequence contains more than one matching element");
       return cur;
      }
    }
  }
  throw new InvalidOperationException("Sequence contains no matching element");
}