Compara dos matrices o listas de arreglos, encuentra valores similares y diferentes

Tengo dos matrices (o listas de matrices si es más fácil) de cadenas. Necesito comparar estos, encontrar los que solo existen en el primer conjunto, que existen en ambos y que solo existen en el segundo conjunto. Estas matrices tienen diferentes longitudes y pueden estar en diferentes órdenes. Si es necesario, supongo que podría ordenarlos ...Compara dos matrices o listas de arreglos, encuentra valores similares y diferentes

Sé que podría hackear esto juntos, pero creo que esto podría tener una solución bastante estándar y eficiente/"mejor", y tengo curiosidad más que nada.

Estoy usando C# para esto, pero si quiere escribir su solución en otro idioma, cualquier ayuda es bienvenida.

¡Gracias por la ayuda!

Fuente

2010-07-19 Wes

¿Tarea por casualidad? –

Eche un vistazo a las muestras de Linq 101 aquí, deberían ayudar (especialmente a los operadores de conjuntos): http://msdn.microsoft.com/en-us/vcsharp/aa336746.aspx – andyp

No, no es tarea de haha. Solo sé que hay una manera más fresca/más eficiente de lo que podría llegar en unos 20 minutos. No he usado Linq antes, pero este podría ser el momento perfecto para sumergirse en él. Gracias por la sugerencia. – Wes

var onlyinfirst = from s in list1 where !list2.Contains(s) select s; 
var onlyinsecond = from s in list2 where !list1.Contains(s) select s; 
var onboth = from s in list1 where list2.Contains(s) select s;

Fuente

2010-07-19 19:24:59 Luiscencio

Esto es lo que se me ocurrió. Me di cuenta de que hay una buena forma de hacerlo C#/.net usando comparables o algo así. También daré una oportunidad, pero si todo lo demás falla, funcionará. – Wes

Tenga en cuenta que si las listas son de tamaño nym, estas soluciones son todas O (n * m). Existen soluciones mucho más eficientes si m y n son grandes. –

Si las matrices son grandes, querrá utilizar una estructura de datos que sea eficiente para estas operaciones; las matrices no son

La solución ingenua es O (n^2) en el tiempo si las matrices son de tamaño n.

Si ordena las matrices en su lugar, puede buscarlas binariamente para los artículos; la clasificación será probablemente O (n lg n) y la búsqueda n veces a un costo de lg n por búsqueda también será O (n lg n) en el tiempo.

Si convierte cada matriz en HashSet<T> primero, puede hacerlo en O (n) tiempo y en O (n) espacio adicional.

Fuente

2010-07-19 19:35:55

Nunca he usado un hashset pero soy muy curioso, lo investigaré, ¡gracias! – Wes

@Wes: 'HashSet' se introdujo en .NET Framework 3.5. – Brian

@Wes: @Brian: Y se llamaba HashSet en lugar del nombre más sensible "Establecer" porque ... espera ... porque "Establecer" es * una palabra clave de Visual Basic *. –

Compara dos matrices o listas de arreglos, encuentra valores similares y diferentes

Respuesta

Cuestiones relacionadas