La forma más rápida de averiguar si dos ICollection < > las colecciones contienen los mismos objetos

Question

¿Cuál es la forma más rápida de averiguar si dos colecciones ICollection < T > contienen exactamente las mismas entradas? La fuerza bruta es clara, me preguntaba si hay un método más elegante.

Estamos usando C # 2.0, así que no hay métodos de extensión si es posible, ¡por favor!

Editar: la respuesta sería interesante tanto para colecciones ordenadas como no ordenadas, y con suerte sería diferente para cada una.

Answer 1

usa C5

http://www.itu.dk/research/c5/

ContinsAll

  

" Compruebe si todos los artículos en un   la colección suministrada está en esta bolsa
  (contando multiplicidades).
     los   artículos a buscar.
  
  Es cierto si todos los artículos son   encontrado. "

[Tested]

public virtual bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T
{
  HashBag<T> res = new HashBag<T>(itemequalityComparer);

  foreach (T item in items)
    if (res.ContainsCount(item) < ContainsCount(item))
      res.Add(item);
    else
      return false;

  return true;
}

Answer 2

Primero compare el. Recuento de las colecciones si tienen el mismo recuento, haga una comparación de fuerza bruta en todos los elementos. El peor de los casos es O (n). Esto es en el caso de que el orden de los elementos deba ser el mismo.

El segundo caso en el que el orden no es el mismo, debe usar un diccionario para almacenar el recuento de elementos encontrados en las colecciones: aquí hay un posible algoritmo

• Comparar el recuento de colecciones: devuelve falso si son diferentes
• Iterar la primera colección
  • Si el elemento no existe en el diccionario, agregue una entrada con Key = Item, Value = 1 (the count)
  • Si existe un elemento, incremente el recuento del elemento en el diccionario;
• Iterar la segunda colección
  • Si el elemento no está en el diccionario, entonces devuelve falso
  • Si el elemento está en el recuento de decremento del diccionario para el elemento
    • Si cuenta == 0 el elemento eliminado;
• return Dictionary.Count == 0;

Answer 3

Para colecciones ordenadas, puede usar el método de extensión SequenceEqual () definido por System.Linq.Enumerable :

if (firstCollection.SequenceEqual(secondCollection))

Answer 4

¿Te refieres a las mismas entradas o las mismas entradas en el mismo orden?

De todos modos, suponiendo que desea comparar si contienen las mismas entradas en el mismo orden, "fuerza bruta" es realmente tu única opción en C # 2.0. Sé lo que quieres decir con no elegante, pero si la comparación atómica en sí es O (1), todo el proceso debería estar en O (N), que no es eso malo.

Answer 5

Si las entradas deben estar en el mismo orden (además de ser las mismas), entonces sugiero, como optimización, que itere ambas colecciones al mismo tiempo y compare la entrada actual en cada colección. De lo contrario, la fuerza bruta es el camino a seguir.

Ah, y otra sugerencia: podría anular Equals para la clase de colección e implementar las cosas de igualdad allí (aunque depende de su proyecto).

Answer 6

Nuevamente, usando la biblioteca C5, que tiene dos conjuntos, puede usar:

C5.ICollection<T> set1 = C5.ICollection<T> ();
C5.ICollection<T> set2 = C5.ICollecton<T> ();
if (set1.UnsequencedEquals (set2)) {
  // Do something
}

La biblioteca C5 incluye una heurística que realmente prueba primero los códigos hash no secuenciados de los dos conjuntos (consulte C5.ICollection < T > .GetUnsequencedHashCode () ) de modo que si los códigos hash de los dos los conjuntos son desiguales, no necesita iterar sobre cada elemento para probar la igualdad.

También es algo notable para usted que C5.ICollection < T > hereda de System.Collections.Generic.ICollection < T > , por lo que puede usar implementaciones de C5 mientras sigue utilizando las interfaces .NET (aunque tiene acceso a menos funcionalidad a través de las interfaces tacañas de .NET).

Answer 7

La fuerza bruta toma O (n), comparando todos los elementos (suponiendo que estén ordenados), lo que creo que es lo mejor que puede hacer, a menos que haya alguna propiedad de los datos que lo haga más fácil.

Supongo que para el caso de no ordenado, es O (n * n).

En cuyo caso, creo que una solución basada en un fusionar tipo probablemente ayudaría .

Por ejemplo, ¿podría volver a modelarlo para que solo haya una colección? O 3 colecciones, una para aquellos en la colección A solamente, una para B solamente y para ambas, así que si A solo y B solo están vacías, entonces son lo mismo ... Probablemente estoy yendo por la tangente totalmente equivocada aquí ...