Утверждая два спискаЭквивалентны друг другу

Question

Чтобы убедиться, что два списка одинаковы, в nunit мы можем использовать CollectionAssert.AreEquivalent, чтобы проверить, что эти два списка содержат одинаковые элементы (порядки не важны).

Но как проверить, эквивалентны ли два List<List<T>>? Идея состоит в том, что если один List<T> имеет те же элементы, что и другие List<T> (опять же, порядок не важен), то они равны.

Answer 1

Вы должны пройти через них, чтобы убедиться, что они эквивалентны, но с некоторыми важными сочетаниями клавиш:

1. Если они на самом деле являются одним и тем же экземпляром (и в реальном коде это часто), то ReferenceEquals(x, y) вернет true.В противном случае это не так.Если ReferenceEquals возвращает истину, то они эквивалентны.

2. Если один равен нулю, а другой нет, то, очевидно, они не равны (если они оба равны нулю, вы 'Я поймал это выше с ReferenceEquals).В любом случае вам нужно будет проверить на нулевое значение для обеспечения безопасности, поэтому во многих случаях у вас есть другой короткий путь.

3. Если они имеют разные размеры, то (для большинства определений эквивалентностиЕсть исключения) они не равны.Немедленно верните false.

4. В тот момент, когда вы обнаружили несоответствие, вы можете вернуть false без продолжения проверки.

5. Это будет быстреесравнить их, если они уже отсортированы.Если вы можете сохранить их отсортированными или потерпеть неудачу, отслеживая, отсортированы они или нет, а затем сортировать только при необходимости, вы можете значительно ускорить процесс.(Обратите внимание, что многие алгоритмы сортировки ведут себя в худшем случае при ненужной сортировке уже отсортированного списка).

Answer 2

Вот попытка, не проверенная.Если каждый внутренний список содержит m элементов, а внешний список-список содержит n списков, я считаю, что сложность составляет O (n^2 x m), но я могу ошибаться.Допущения:

1. T не реализует IComparable или любой другой интерфейс, который позволяет сортировку.
2. Порядок не имеет отношения к равенству как для List<List<T>> s, так и для составления 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 3

Я бы использовал SelectMany() и сгладил список. Теперь вы можете либо сравнивать элемент с элементом, используя Assert.Equals (), либо использовать обычную коллекцию assert для списков. Выражение запроса с двумя предложениями from будет делать то же самое:

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);
}

Обратите внимание, что это очень наивная реализация, сглаженные последовательности могут быть равными, в то время как исходные последовательности содержат те же элементы, но в другом разбиении.

Answer 4

Я думаю, вам нужно написать собственный код для этого.

Посмотрите, как CollectionAssert.AreEquivalent работает с Reflector, затем напишите свой собственный вспомогательный класс "MyAsserts".

Вам нужно быть умным, если вы хотите работать быстрее, чем O (n ^ 2 * m ^ 2), где n - это количество списков в крайнем списке, а m - количество элементов во внутренних списках.

Простое решение - перебрать все «внутренние списки» в list1 и использовать код из CollectionAssert.AreEquivalent, чтобы проверить, содержит ли list2 такой список. Затем поменяйте местами list1 и list2 и повторите. Однако вы можете сделать намного лучше.

(Затем вам нужно решить, как создать полезное сообщение, когда списки не эквивалентны.)

Answer 5

Я не думаю, что вы проверяете каждый элемент в отдельности. Обычно я сначала проверяю одинаковую длину, затем проверяю, скажем, i, на длину списков и проверяю, что list1 [i] == list2 [i]

обновление

Извините, пропустил (центральную) часть об элементах, которые не должны быть в порядке. В этом случае создайте HashSet с элементами второго списка и проверьте для каждого элемента в списке list1, находится ли он в хэш-наборе. Это сокращает время выполнения поиска от линейного до логарифмического.

обновление 2 Как отметил Дональд Рэй, вы должны проверить оба способа, если у вас есть возможность многократного появления отдельных объектов в любом из списков.