C# Velocidad de expresión lambda

Question

No he usado muchas expresiones lambda antes y me encontré con un caso en el que pensé que podría usar hábilmente uno. Tengo una lista personalizada de ~ 19,000 registros y necesito averiguar si existe o no un registro en la lista, así que en lugar de escribir un montón de loops o usar linq para revisar la lista decidí probar esto:

for (int i = MinX; i <= MaxX; ++i) 
{ 
    tempY = MinY; 

    while (tempY <= MaxY) 
    { 
     bool exists = myList.Exists(item => item.XCoord == i && item.YCoord == tempY); 

     ++tempY; 
    } 
} 

El único problema es que tarda ~ 9 - 11 segundos en ejecutarse. ¿Estoy haciendo algo mal es solo un caso en el que no debería estar usando una expresión como esta?

Gracias.

EDIT: Lo siento. Debo elaborar. Estoy creando una lista de registros con el ciclo for y while y comprobando si ese registro existe en myList. Esa es la única forma en que podría pensar en hacerlo. Lo volveré a evaluar y veré con qué vengo.

Answer 1

Su algoritmo es ineficiente. Si usted está haciendo varias búsquedas en la misma lista que necesita para:

1. Sort la lista apropiada (por su mirada hacia arriba clave).
2. Utilice un binary search para encontrar el registro correcto.

Su otra opción es si la memoria no es un problema y desea que sea realmente rápido es poner los registros en un Dictionary<Your_Key,Record>. Eso le dará el acceso más rápido después de configurarlo.

Answer 2

No es un problema con la lambda, es un problema con su algoritmo. Estás pasando de MinX a MaxX, ¿cuántos? luego estás recorriendo lo mismo desde MinY a MaxY, luego estás recorriendo ~ 19,000 registros. entonces si el bucle X es 10 y el bucle y es 10, entonces estás haciendo 19,000 * 10 * 10 llamadas. Podría ser mucho peor.

Answer 3

¿No es esto lo que quieres?

myList.Where(
    item=>item.XCoord>=MinX 
     &&item.XCoord<=MaxX 
     &&item.YCoord>=MinY 
     &&item.YCoord<=MaxY 
) 

Todos los elementos resultantes cumplirán el criterio exists.

... o no entendí bien?

Answer 4

Este código no tiene sentido para mí, por lo que es muy difícil decir si lo estás haciendo mal o no. Las probabilidades son buenas de que sí, lo estás haciendo mal.

En lugar de mostrar el código, intente esto. Supongamos que tiene un método que hizo exactamente lo que quiere. ¿Cuál sería la firma de ese método? No el cuerpo, solo la firma.

Supongamos, por ejemplo, que quiere hacer la pregunta "¿esta lista de puntos contiene un punto particular?" A continuación, la firma sería

bool Contains(List<Point> list, Point p) 

Suponga que desea hacer la pregunta "¿Esto lista de puntos contiene ningún punto dentro de este rectángulo?" A continuación, la firma sería

bool ContainsAny(List<Point> list, Rectangle r) 

Suponga que desea hacer la pregunta "¿cuáles son los puntos que estas dos listas tienen en común?"Entonces la firma sería

List<Point> Intersection(List<Point> l1, List<Point> l2) 

y así sucesivamente. Estado lo que está tratando de hacer más clara y que puede ayudar a optimizar la operación. Comienza con la firma.

Answer 5

Voy a ampliar sobre la respuesta de Kevin con una buena solución a base de LINQ.

el código original calcula efectivamente una matriz de dos dimensiones booleano que indica si una coordenada existía en myList en el x & y coordenadas para cada elemento de la matriz.

La prueba utilizada para cada x & y se puede expresar como una función lambda como tal:

Func<int, int, bool> original = 
    (x, y) => 
     myList.Exists(item => item.XCoord == x && item.YCoord == y); 

Esto es ineficiente como el método Exists se llama, y ​​por lo tanto la lista se itera, para cada x & y coordinado probado. Si se itera o no toda la lista depende si se encuentra o no una coincidencia. En muchos casos, no habrá coincidencia, por lo que toda la lista se visita varias veces.

lo tanto, es mejor comprobar la validez de calcular un diccionario de diccionarios para determinar si una coordenada existe en myList para cualquier x & y coordenadas.

var xyLookup = 
    (from item in myList 
    group item by item.XCoord into XCoords 
    select new 
    { 
     X = XCoords.Key, 
     YLookup = (from x in XCoords 
        group x by x.YCoord into YCoords 
        select new 
        { 
         Y = YCoords.Key, 
         Coords = YCoords 
        }).ToDictionary(a => a.Y, a => a.Coords) 
    }).ToDictionary(b => b.X, b => b.YLookup); 

xyLookup permite ahora la siguiente función lambda para reemplazar la versión original.

Func<int, int, bool> refactored = 
    (x, y) => 
     xyLookup.ContainsKey(x) && xyLookup[x].ContainsKey(y); 

Pre-computing xyLookup lleva algún tiempo por lo que, de acuerdo con mis pruebas, si tengo una matriz de 3x3 y myList consta de 3 coordenadas a continuación, ambos métodos son más o menos la misma velocidad. Sin embargo, esperaría que el tamaño real de la matriz y el número de elementos en myList serían mucho mayores en la práctica.

Si tengo una matriz de 100x100 con 10.000 coordenadas en myList, entonces xyLookup es aproximadamente 91 veces más rápido que el método original.

Me encanta linq ... :-)