c# - que - ¿Cuál es la forma más sencilla de lograr el rendimiento de O(n) al crear la unión de 3 IEnumerables?

list ienumerable c#

Question

Diga que a, b, c son todos List<t> y quiero crear una unión sin clasificar de ellos. Aunque el rendimiento no es super crítico, pueden tener 10,000 entradas en cada una, así que estoy dispuesto a evitar las soluciones O (n ^ 2).

AFAICT la documentación de MSDN no dice nada sobre las características de rendimiento de la unión en lo que respecta a los diferentes tipos.

Mi instinto dice que si solo hago un. a.Union(b).Union(c) , esto tomará tiempo O (n ^ 2), pero new Hashset<t>(a).Union(b).Union(c) sería O (n).

¿Alguien tiene alguna documentación o métrica para confirmar o negar esta suposición?

Answer 1

Debe utilizar Enumerable.Union porque es tan eficiente como el enfoque HashSet . La complejidad es O (n + m) porque:

Enumerable.Union

Cuando se enumera el objeto devuelto por este método, Union<TSource> e numera primero y segundo en ese orden y produce cada elemento que aún no se ha producido.

Código fuente here .

Ivan tiene razón, hay una sobrecarga si utiliza Enumerable.Union con varias colecciones, ya que se debe crear un nuevo conjunto para cada llamada encadenada. Por lo tanto, podría ser más eficiente (en términos de consumo de memoria) si utiliza uno de estos métodos:

1. Concat + Distinct :

   a.Concat(b).Concat(c)...Concat(x).Distinct()

2. Union + Concat

   a.Union(b.Concat(c)...Concat(x))

3. HashSet<T> constructor que toma IEnumerable<T> (fe con int ):

   new HashSet<int>(a.Concat(b).Concat(c)...Concat(x))

La diferencia entre los dos primeros puede ser despreciable. El tercer enfoque no es usar la ejecución diferida, crea un HashSet<> en la memoria. Es una manera buena y eficiente 1. si necesita este tipo de colección o 2. si esta es la operación final en la consulta. Pero si necesita realizar más operaciones en esta consulta encadenada, debería preferir Concat + Distinct o Union + Concat .

Answer 2

Si bien @Tim Schmelter tiene razón sobre la complejidad de tiempo lineal del método Enumerable.Union , el encadenamiento de múltiples operadores de la Union tiene la sobrecarga oculta que cada operador de la Union crea internamente un conjunto de hash que básicamente duplica el del operador anterior (más elementos adicionales) utilizando mucha más memoria en comparación con el enfoque de HashSet único.

Si tomamos en cuenta el hecho de que Union es simplemente un acceso directo para Concat + Distinct , la solución LINQ escalable con la misma complejidad de tiempo / espacio del HashSet será:

a.Concat(b).Concat(c)...Concat(x).Distinct()

Answer 3

Union es O (n).

a.Union(b).Union(c) es menos eficiente en la mayoría de las implementaciones que a.Union(b.Concat(c)) porque crea un hash-set para la primera operación de unión y luego otra para la segunda, como otra Las respuestas han dicho. Ambos de estos también terminan con una cadena de IEnumerator<T> en uso que aumenta el costo a medida que se agregan otras fuentes.

a.Union(b).Union(c) es más eficiente en .NET Core porque la segunda operación .Union() produce un solo objeto con conocimiento de a , b y creará un conjunto de hash único para todo el operación, así como evitar la cadena de IEnumerator<T> .