Сравнение двух коллекций на равенство независимо от порядка предметов в них

Question

Я хотел бы сравнить две коллекции (в C #), но я не уверен, что это лучший способ реализовать это эффективно.

Я читал в другой ветке о Enumerable.SequenceEqual , но это не совсем то, что я ищу.

В моем случае две коллекции были бы равны, если бы они содержали одинаковые предметы (независимо от порядка).

Пример:

collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};

collection1 == collection2; // true

Что я обычно делаю, это перебираю каждый элемент одной коллекции и вижу, существует ли он в другой коллекции, затем перебираю каждый элемент другой коллекции и проверяю, существует ли он в первой коллекции. (Я начинаю со сравнения длин).

if (collection1.Count != collection2.Count)
    return false; // the collections are not equal

foreach (Item item in collection1)
{
    if (!collection2.Contains(item))
        return false; // the collections are not equal
}

foreach (Item item in collection2)
{
    if (!collection1.Contains(item))
        return false; // the collections are not equal
}

return true; // the collections are equal

Однако это не совсем правильно, и, вероятно, это не самый эффективный способ сравнить две коллекции на равенство.

Пример, который я могу представить, был бы неправильным:

collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}

Что было бы равным моей реализации. Стоит ли просто подсчитать, сколько раз найден каждый предмет, и убедиться, что количество совпадений в обеих коллекциях одинаково?

---

Примеры приведены в некотором роде C # (назовем это псевдо-C #), но давать ответ на любом языке, который вы пожелаете, не имеет значения.

Примечание: Я использовал целые числа в примерах для простоты, но я хочу иметь возможность также использовать объекты ссылочного типа (они не работают корректно в качестве ключей, поскольку сравнивается только ссылка на объект) , а не содержание).

Answer 1

Дублирующий пост, но проверьте мое решение для сравнения коллекций . Все довольно просто:

Будет выполнено сравнение на равенство независимо от порядка:

var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;

Это позволит проверить, были ли элементы добавлены / удалены:

var list1 = new[] { "Billy", "Bob" };
var list2 = new[] { "Bob", "Sally" };
var diff = list1.Compare(list2);
var onlyinlist1 = diff.Removed; //Billy
var onlyinlist2 = diff.Added;   //Sally
var inbothlists = diff.Equal;   //Bob

Будет показано, какие элементы в словаре изменились:

var original = new Dictionary<int, string>() { { 1, "a" }, { 2, "b" } };
var changed = new Dictionary<int, string>() { { 1, "aaa" }, { 2, "b" } };
var diff = original.Compare(changed, (x, y) => x.Value == y.Value, (x, y) => x.Value == y.Value);
foreach (var item in diff.Different)
  Console.Write("{0} changed to {1}", item.Key.Value, item.Value.Value);
//Will output: a changed to aaa

Оригинальный пост здесь .

Answer 2

Вот решение, которое является улучшением по сравнению с этим .

public static bool HasSameElementsAs<T>(
        this IEnumerable<T> first, 
        IEnumerable<T> second, 
        IEqualityComparer<T> comparer = null)
    {
        var firstMap = first
            .GroupBy(x => x, comparer)
            .ToDictionary(x => x.Key, x => x.Count(), comparer);

        var secondMap = second
            .GroupBy(x => x, comparer)
            .ToDictionary(x => x.Key, x => x.Count(), comparer);

        if (firstMap.Keys.Count != secondMap.Keys.Count)
            return false;

        if (firstMap.Keys.Any(k1 => !secondMap.ContainsKey(k1)))
            return false;

        return firstMap.Keys.All(x => firstMap[x] == secondMap[x]);
    }

Answer 3

Вот мой вариант метода ответа ohadsc на случай, если он кому-нибудь пригодится

static public class EnumerableExtensions 
{
    static public bool IsEquivalentTo<T>(this IEnumerable<T> first, IEnumerable<T> second)
    {
        if ((first == null) != (second == null))
            return false;

        if (!object.ReferenceEquals(first, second) && (first != null))
        {
            if (first.Count() != second.Count())
                return false;

            if ((first.Count() != 0) && HaveMismatchedElement<T>(first, second))
                return false;
        }

        return true;
    }

    private static bool HaveMismatchedElement<T>(IEnumerable<T> first, IEnumerable<T> second)
    {
        int firstCount;
        int secondCount;

        var firstElementCounts = GetElementCounts<T>(first, out firstCount);
        var secondElementCounts = GetElementCounts<T>(second, out secondCount);

        if (firstCount != secondCount)
            return true;

        foreach (var kvp in firstElementCounts)
        {
            firstCount = kvp.Value;
            secondElementCounts.TryGetValue(kvp.Key, out secondCount);

            if (firstCount != secondCount)
                return true;
        }

        return false;
    }

    private static Dictionary<T, int> GetElementCounts<T>(IEnumerable<T> enumerable, out int nullCount)
    {
        var dictionary = new Dictionary<T, int>();
        nullCount = 0;

        foreach (T element in enumerable)
        {
            if (element == null)
            {
                nullCount++;
            }
            else
            {
                int num;
                dictionary.TryGetValue(element, out num);
                num++;
                dictionary[element] = num;
            }
        }

        return dictionary;
    }

    static private int GetHashCode<T>(IEnumerable<T> enumerable)
    {
        int hash = 17;

        foreach (T val in enumerable.OrderBy(x => x))
            hash = hash * 23 + val.GetHashCode();

        return hash;
    }
}

Answer 4

erickson почти прав: поскольку вы хотите сопоставить по количеству дубликатов, вам нужна сумка . В Java это выглядит примерно так:

(new HashBag(collection1)).equals(new HashBag(collection2))

Я уверен, что C # имеет встроенную реализацию Set. Я бы использовал это в первую очередь; если производительность является проблемой, вы всегда можете использовать другую реализацию Set, но использовать тот же интерфейс Set.

Answer 5

Это простое решение заставляет универсальный тип IEnumerable реализовать IComparable. Потому что OrderBy определение.

Если вы не хотите делать такое предположение, но по-прежнему хотите использовать это решение, вы можете использовать следующий фрагмент кода:

bool equal = collection1.OrderBy(i => i?.GetHashCode())
   .SequenceEqual(collection2.OrderBy(i => i?.GetHashCode()));

Answer 6

Если разрешить дубликаты в IEnumerable<T> (если наборы нежелательны \ возможны) и "игнорировать порядок", вы сможете использовать .GroupBy().

Я не эксперт по измерениям сложности, но мое элементарное понимание состоит в том, что это должно быть O (n). Я понимаю, что O (n ^ 2) приходит от выполнения операции O (n) внутри другой операции O (n), такой как ListA.Where(a => ListB.Contains(a)).ToList(). Каждый элемент в ListB оценивается на равенство с каждым элементом в ListA.

Как я уже сказал, мое понимание сложности ограничено, поэтому поправьте меня, если я ошибаюсь.

public static bool IsSameAs<T, TKey>(this IEnumerable<T> source, IEnumerable<T> target, Expression<Func<T, TKey>> keySelectorExpression)
    {
        // check the object
        if (source == null && target == null) return true;
        if (source == null || target == null) return false;

        var sourceList = source.ToList();
        var targetList = target.ToList();

        // check the list count :: { 1,1,1 } != { 1,1,1,1 }
        if (sourceList.Count != targetList.Count) return false;

        var keySelector = keySelectorExpression.Compile();
        var groupedSourceList = sourceList.GroupBy(keySelector).ToList();
        var groupedTargetList = targetList.GroupBy(keySelector).ToList();

        // check that the number of grouptings match :: { 1,1,2,3,4 } != { 1,1,2,3,4,5 }
        var groupCountIsSame = groupedSourceList.Count == groupedTargetList.Count;
        if (!groupCountIsSame) return false;

        // check that the count of each group in source has the same count in target :: for values { 1,1,2,3,4 } & { 1,1,1,2,3,4 }
        // key:count
        // { 1:2, 2:1, 3:1, 4:1 } != { 1:3, 2:1, 3:1, 4:1 }
        var countsMissmatch = groupedSourceList.Any(sourceGroup =>
                                                        {
                                                            var targetGroup = groupedTargetList.Single(y => y.Key.Equals(sourceGroup.Key));
                                                            return sourceGroup.Count() != targetGroup.Count();
                                                        });
        return !countsMissmatch;
    }

Answer 7

Во многих случаях единственным подходящим ответом является ответ Игоря Островского, остальные ответы основаны на хэш-коде объектов. Но когда вы генерируете хеш-код для объекта, вы делаете это только на основе его полей IMMUTABLE, таких как поле Id объекта (в случае объекта базы данных) Почему важно переопределить GetHashCode при переопределении метода Equals?

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

Пожалуйста, прочитайте комментарии меня и mr.Schnider's к его самому популярному сообщению.

Джеймс

Answer 8

Есть много решений этой проблемы. Если вам не нужны дубликаты, вам не нужно сортировать оба. Сначала убедитесь, что у них одинаковое количество предметов. После этого сортируйте одну из коллекций. Затем binsearch каждого элемента из второй коллекции в отсортированной коллекции. Если вы не нашли данный элемент, остановитесь и верните false. Сложность этого: - сортировка первой коллекции: N Log (N) - поиск каждого элемента от второго к первому: N LOG (N) Таким образом, вы получите 2 * N * LOG (N), если они совпадают, и вы посмотрите все. Это похоже на сложность сортировки обоих. Также это дает вам возможность остановиться раньше, если есть разница. Однако имейте в виду, что если оба отсортированы, прежде чем вы приступите к этому сравнению, и вы попытаетесь отсортировать, используя что-то вроде qsort, сортировка будет более дорогой. Для этого есть оптимизации. Другая альтернатива, которая отлично подходит для небольших коллекций, где вы знаете диапазон элементов, - это использование индекса битовой маски. Это даст вам производительность O (n). Другая альтернатива - использовать хеш и искать его. Для небольших коллекций обычно намного лучше выполнить сортировку или индекс битовой маски. У Hashtable есть недостаток худшей местности, так что имейте это в виду. Опять же, это только если вы не заботитесь о дубликатах. Если вы хотите учесть дубликаты, выполните сортировку обоих.