c# - Afirmar dos listas<Lista<T>> son equivalentes entre sí

nunit

Question

Para asegurarnos de que dos listas sean iguales, en nunit, podemos usar CollectionAssert.AreEquivalent para verificar que estas dos listas contengan los mismos elementos (los pedidos no son importantes).

Pero, ¿cómo verificar si dos List<List<T>> son equivalentes? La idea es que si una List<T> tiene los mismos elementos que la otra List<T> (de nuevo, el orden no es importante), entonces son iguales.

Answer 1

Aquí hay un intento, no probado. Si cada lista interna contiene m elementos y la lista externa contiene n listas, creo que la complejidad es O (n^2 xm) , pero podría estar equivocado. Suposiciones

1. T no implementa IComparable ni ninguna interfaz que permita la clasificación.
2. El ordenamiento es irrelevante para la igualdad tanto para los objetos List<List<T>> como para los que componen List<T> .

-

public static bool ListListsAreEqual<T>(List<List<T>> listlist1, List<List<T>> listlist2)
{
    if (listlist1.Count != listlist2.Count)
        return false;

    var listList2Clone = listlist2.ToList();

    foreach (var list1 in listlist1)
    {
        var indexOfMatchInList2 = listList2Clone
                   .FindIndex(list2 => ListsArePermutations(list1, list2));

        if (indexOfMatchInList2 == -1)
            return false;

        listList2Clone.RemoveAt(indexOfMatchInList2);
    }

    return true;
}

private static bool ListsArePermutations<T>(List<T> list1, List<T> list2)
{
    return list1.Count == list2.Count && new HashSet<T>(list1).SetEquals(list2);
}

Answer 2

Creo que necesitarás escribir tu propio código para hacer esto.

Mire cómo funciona CollectionAssert.AreEquivalent con Reflector y luego escriba su propia clase de ayudante "MyAsserts".

Tendrá que ser inteligente si desea correr más rápido que O (n ^ 2 * m ^ 2), donde n es el número de listas en la lista superior y m es el número de elementos en las listas internas.

La solución simple es recorrer todas las "listas internas" en la lista1 y usar el código de CollectionAssert.AreEquivalent para verificar si la lista2 contiene dicha lista. Luego intercambie list1 y list2 y repita. Sin embargo puedes hacerlo mucho mejor.

(A continuación, debe averiguar cómo producir un mensaje útil cuando las listas no son equivalentes.)

Answer 3

No creo que te muevas revisando cada elemento individualmente. Por lo general, primero verificaré la misma longitud, luego recorreré para decir i sobre la longitud de las listas y revisaré esa lista1 [i] == list2 [i]

actualizar

Lo sentimos, se perdió la parte (central) sobre los elementos que no tienen que estar en orden. En ese caso, cree un HashSet con los elementos de la segunda lista y compruebe cada elemento en la lista1 si está en el hashset. Esto reduce el tiempo de ejecución para la búsqueda de lineal a logarítmica.

actualización 2 Como lo señaló Donald Ray, debe verificar ambas formas si tiene posibles apariciones múltiples de objetos individuales en cualquiera de las listas.

Answer 4

Tienes que recorrerlos para asegurarte de que son equivalentes, pero con algunos atajos importantes:

1. Si en realidad son la misma instancia (y en el código real esto suele aparecer), ReferenceEquals(x, y) devolverá true. De lo contrario no lo hará. Si ReferenceEquals devuelve true, entonces son equivalentes.

2. Si uno es nulo y el otro no, entonces obviamente no son iguales (si los dos son nulos, habrás capturado eso anteriormente con ReferenceEquals ). Tendrá que realizar una prueba de seguridad de null de todos modos, por lo que tendrá otro atajo en muchos casos.

3. Si son de diferentes tamaños, entonces (para la mayoría de las definiciones de equivalencia, hay excepciones) no son iguales. Devuelve falso inmediatamente.

4. En el momento en que encuentra un desajuste, puede devolver falso sin seguir comprobando.

5. Será más rápido compararlos si ya están ordenados. Si puede mantenerlos ordenados, o si falla, hacer un seguimiento de si están ordenados o no y luego ordenar solo cuando sea necesario, puede acelerar enormemente las cosas. (Sin embargo, tenga en cuenta que muchos algoritmos de clasificación tienen su peor comportamiento cuando se clasifica innecesariamente una lista que ya está clasificada).

Answer 5

SelectMany() y SelectMany() la lista. Ahora puede comparar elemento contra elemento, utilizando Assert.Equals () o usar un aserto de colección normal para listas. Una expresión de consulta con dos cláusulas from hará lo mismo:

void AssertEquals<T>(List<List<T>> expected, List<List<T>> actual)
{
  var flatExpected = expected.SelectMany(x=>x);
  var flatActual = expected.SelectMany(x=>x);

  CollectionAssert.Equals(flatExpected, flatActual);
}

Tenga en cuenta que esta es solo una implementación muy ingenua, las secuencias aplanadas pueden ser iguales, mientras que las secuencias de origen contienen los mismos elementos pero en una partición diferente.