c# - interseccion - Intersección de dos conjuntos de la manera más optimizada
interseccion de conjuntos c# (2)
Dado dos conjuntos de valores, tengo que encontrar nuestro si hay algún elemento común entre ellos o no, es decir, si su intersección es nula o no.
¿Cuál de la colección estándar de C # se adecuará mejor (en términos de rendimiento) para este propósito? Sé que linq tiene un método de extensión Intersect para averiguar la intersección de dos listas / matrices, pero mi atención se centra en el rendimiento en términos de Big-O notation .
¿Y si también tengo que descubrir la intersección de dos conjuntos?
Bueno, si usas el método Intersect de LINQ construirá un HashSet de la segunda secuencia, y luego verificará cada elemento de la primera secuencia. Entonces es O (M + N) ... y puedes usar foo.Intersect(bar).Any() para salir temprano.
Por supuesto, si almacena uno (cualquiera) configurado en un HashSet<T> para comenzar, puede simplemente iterar sobre el otro buscando la contención en cada paso. Aún así, necesitarías construir el set para empezar.
Fundamentalmente tienes un problema O (M + N) sea lo que sea que hagas: no vas a ser más barato que eso ( siempre existe la posibilidad de que tengas que mirar cada elemento) y si tus códigos hash son razonables , deberías poder alcanzar esa complejidad fácilmente. Por supuesto, algunas soluciones pueden dar mejores factores constantes que otras ... pero eso es rendimiento más que complejidad;)
EDITAR: Como se señaló en los comentarios, también hay ISet<T>.Overlaps : si ya tiene un conjunto con un tipo estático de ISet<T> o una implementación concreta, llamar a Overlaps aclara lo que está haciendo. Si ambos conjuntos están tipados estáticamente como ISet<T> , use larger.Overlaps(smaller) (donde más grandes y más pequeños son en términos del tamaño del conjunto) ya que esperaría que una implementación de Overlaps iterara sobre el argumento y comprueba cada elemento contra el contenido del conjunto al que lo llamas.
Como se mencionó, la aplicación Any() le dará algún rendimiento.
Lo probé en un conjunto de datos bastante grande y me dio un 25% de mejoras.
También aplicar más larger.Intersect(smaller) lugar de lo contrario es muy importante, en mi caso, dio un 35% de mejoras.
También ordenar la lista antes de aplicar intersectar dio otro 7-8%.
Otra cosa a tener en cuenta es que, dependiendo del caso de uso, puedes evitar la aplicación de intersección por completo.
Por ejemplo, para una lista de enteros, si el máximo y el mínimo no están dentro de los mismos rebotes, no es necesario aplicar la intersección, ya que nunca lo harán.
Lo mismo aplica para una lista de cuerdas con la misma idea aplicada a la primera letra.
De nuevo, dependiendo de su caso, intente tanto como sea posible para encontrar una regla donde la intersección sea imposible de evitar llamarlo.