¿Cómo buscar si un elemento de una lista está en otra lista?

Quiero saber si al menos un elemento en una primera lista se puede encontrar en una segunda lista.¿Cómo buscar si un elemento de una lista está en otra lista?

Puedo ver dos formas de hacerlo. Digamos nuestras listas son:

List<string> list1 = new[] { "A", "C", "F", "H", "I" }; 
List<string> list2 = new[] { "B", "D", "F", "G", "I" };

El primer enfoque utiliza un bucle:

bool isFound = false; 
foreach (item1 in list1) 
{ 
    if (list2.Contains(item1)) 
    { 
     isFound = true; 
     break; 
    } 
}

El segundo utiliza LINQ directamente:

bool isFound = list1.Intersect(list2).Any();

El primero de ellos es mucho tiempo para escribir y no muy sencillo/fácil de leer. El segundo es corto y claro, pero las actuaciones serán bajas, especialmente en listas grandes.

¿Cuál puede ser una manera elegante de hacerlo?

Fuente

2011-02-20 Arseni Mourzenko

Creo que el segundo será más rápido para grandes listas. Dado que el primero es 'O (list1.Count * list2.Count)' mientras que el segundo es 'O (list1.Count + list2.Count)'. En segundo lugar, se necesita más memoria. – CodesInChaos

Si realmente quiere usar LINQ para buscar * exactamente * como su primera muestra, use 'bool isFound = list1.Any (list2.Contains);' – Ani

Pero por supuesto esa variante, al igual que el código original tiene un rendimiento cuadrático. – CodesInChaos

El segundo tiene un mejor rendimiento en listas grandes que el primero. Intersect coloca los elementos de una lista en una tabla hash antes de verificar los elementos de la otra lista para la membresía.

Fuente

2011-02-20 22:56:22 mquander

Pensé que en el segundo caso, se calcularía la intersección de dos listas, y solo entonces se ejecutará 'Any'. ¿Me equivoco? –

La intersección se calcula de forma perezosa.Creo que primero crea un hashset fuera de list2 y luego pasa a list1 regresando y agregando al hashset a medida que avanza. – CodesInChaos

@MainMa - sí, estás equivocado en eso. Hará hash el * primer * set, luego usará un bloque iterador para colocar el spool sobre el segundo. En cada punto, solo devuelve una sola coincidencia. Los bloques iteradores no se ejecutan hasta su finalización antes de devolver el contenido. No es necesario calcular el conjunto completo de coincidencias en una colección. La única vez que 'Any()' se ejecutará hasta su finalización es si devuelve 'false'; de lo contrario, se cortocircuitaría la secuencia en la primera coincidencia. –

Parece extraño criticar el rendimiento de LINQ cuando el original es claramente (el peor de los casos) O (n * m); el enfoque LINQ sería . Espero que use un HashSet<T> en una lista, y luego utilice un bloque de iteración de transmisión, por lo que el rendimiento debería ser O (n + m), es decir, mejor.

Fuente

2011-02-20 22:57:38

Creo que el segundo será más rápido para las listas grandes. Dado que el primero es O (list1.Count * list2.Count) mientras que el segundo es O (list1.Count + list2.Count). En segundo lugar, se necesita más memoria.

Y la sobrecarga de linq suele ser un factor de multiplicación constante sobre el código artesanal. Supongo que el segundo es más lento que el código imperativo por un factor máximo de dos, probablemente ni siquiera eso. Utiliza la memoria O(list1.Count+list2.Count) que puede reducirse a O(Min(list1,list2)) si escribe cuidadosamente el código para el uso de memoria baja manteniendo el rendimiento lineal.

Este código debe ser relativamente rápido en grandes listas:

bool isFound = false; 
HashSet<string> set2=new HashSet<string>(list2); 
foreach (item1 in list1) 
{ 
    if (set2.Contains(item1)) 
    { 
     isFound = true; 
     break; 
    } 
}

Puede optimizar el código más haciendo la lista más pequeña en un hashset en lugar de utilizar lista2 siempre.

Fuente

2011-02-20 22:58:52 CodesInChaos

La respuesta aceptada es excelente, sin embargo, no funciona con Linq-a-sql, ya que no hay mapeo para Intersect. En ese caso, debería usar:

bool isFound = table.Any(row => list2.Contains(row.FieldWithValue));

Esto se compila a WHERE EXSITS

Fuente

2013-08-29 10:06:07

¿Cómo buscar si un elemento de una lista está en otra lista?

Respuesta

Cuestiones relacionadas