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

Question

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

Я читал другую тему о Перечислимый.Последовательность одинаковая, но это не совсем то, что я ищу.

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

Пример:

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

Оказывается, Microsoft уже предусмотрела это в своей платформе тестирования: CollectionAssert.Эквивалентны

Замечания

Две коллекции эквивалентны, если они содержат одинаковые элементы в одинаковом количестве, но в любом порядке.Элементы равны, если их значения равны, нет, если они ссылаются на один и тот же объект.

Используя reflector, я изменил код AreEquivalent() для создания соответствующего средства сравнения равенства.Он более полон, чем существующие ответы, поскольку учитывает нули, реализует IEqualityComparer и имеет некоторые проверки эффективности и граничных регистров.кроме того, это Майкрософт :)

public class MultiSetComparer<T> : IEqualityComparer<IEnumerable<T>>
{
    private readonly IEqualityComparer<T> m_comparer;
    public MultiSetComparer(IEqualityComparer<T> comparer = null)
    {
        m_comparer = comparer ?? EqualityComparer<T>.Default;
    }

    public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
    {
        if (first == null)
            return second == null;

        if (second == null)
            return false;

        if (ReferenceEquals(first, second))
            return true;

        if (first is ICollection<T> firstCollection && second is ICollection<T> secondCollection)
        {
            if (firstCollection.Count != secondCollection.Count)
                return false;

            if (firstCollection.Count == 0)
                return true;
        }

        return !HaveMismatchedElement(first, second);
    }

    private bool HaveMismatchedElement(IEnumerable<T> first, IEnumerable<T> second)
    {
        int firstNullCount;
        int secondNullCount;

        var firstElementCounts = GetElementCounts(first, out firstNullCount);
        var secondElementCounts = GetElementCounts(second, out secondNullCount);

        if (firstNullCount != secondNullCount || firstElementCounts.Count != secondElementCounts.Count)
            return true;

        foreach (var kvp in firstElementCounts)
        {
            var firstElementCount = kvp.Value;
            int secondElementCount;
            secondElementCounts.TryGetValue(kvp.Key, out secondElementCount);

            if (firstElementCount != secondElementCount)
                return true;
        }

        return false;
    }

    private Dictionary<T, int> GetElementCounts(IEnumerable<T> enumerable, out int nullCount)
    {
        var dictionary = new Dictionary<T, int>(m_comparer);
        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;
    }

    public int GetHashCode(IEnumerable<T> enumerable)
    {
        if (enumerable == null) throw new ArgumentNullException(nameof(enumerable));

        int hash = 17;

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

        return hash;
    }
}

Пример использования:

var set = new HashSet<IEnumerable<int>>(new[] {new[]{1,2,3}}, new MultiSetComparer<int>());
Console.WriteLine(set.Contains(new [] {3,2,1})); //true
Console.WriteLine(set.Contains(new [] {1, 2, 3, 3})); //false

Или, если вы просто хотите напрямую сравнить две коллекции:

var comp = new MultiSetComparer<string>();
Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","c","b"})); //true
Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","b"})); //false

Наконец, вы можете использовать свой компаратор равенства по вашему выбору:

var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true

Answer 2

Простым и довольно эффективным решением является сортировка обеих коллекций, а затем сравнение их на предмет равенства:

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

Этот алгоритм равен O (N * logN), в то время как ваше решение выше равно O (N ^ 2).

Если коллекции обладают определенными свойствами, возможно, вы сможете реализовать более быстрое решение.Например, если обе ваши коллекции являются хэш-наборами, они не могут содержать дубликатов.Кроме того, проверка того, содержит ли хэш-набор какой-либо элемент, выполняется очень быстро.В этом случае алгоритм, подобный вашему, скорее всего, будет самым быстрым.

Answer 3

Создайте словарь "dict", а затем для каждого элемента в первой коллекции выполните команду dict[member]++;

Затем выполните цикл по второй коллекции таким же образом, но для каждого элемента выполните dict[member]--.

В конце выполните цикл по всем элементам в словаре:

    private bool SetEqual (List<int> left, List<int> right) {

        if (left.Count != right.Count)
            return false;

        Dictionary<int, int> dict = new Dictionary<int, int>();

        foreach (int member in left) {
            if (dict.ContainsKey(member) == false)
                dict[member] = 1;
            else
                dict[member]++;
        }

        foreach (int member in right) {
            if (dict.ContainsKey(member) == false)
                return false;
            else
                dict[member]--;
        }

        foreach (KeyValuePair<int, int> kvp in dict) {
            if (kvp.Value != 0)
                return false;
        }

        return true;

    }

Редактировать:Насколько я могу судить, это происходит в том же порядке, что и наиболее эффективный алгоритм.Этот алгоритм равен O (N), предполагая, что словарь использует O (1) поисковых запросов.

Answer 4

Это моя (под сильным влиянием Д.Дженнингса) общая реализация метода сравнения (на C #):

/// <summary>
/// Represents a service used to compare two collections for equality.
/// </summary>
/// <typeparam name="T">The type of the items in the collections.</typeparam>
public class CollectionComparer<T>
{
    /// <summary>
    /// Compares the content of two collections for equality.
    /// </summary>
    /// <param name="foo">The first collection.</param>
    /// <param name="bar">The second collection.</param>
    /// <returns>True if both collections have the same content, false otherwise.</returns>
    public bool Execute(ICollection<T> foo, ICollection<T> bar)
    {
        // Declare a dictionary to count the occurence of the items in the collection
        Dictionary<T, int> itemCounts = new Dictionary<T,int>();

        // Increase the count for each occurence of the item in the first collection
        foreach (T item in foo)
        {
            if (itemCounts.ContainsKey(item))
            {
                itemCounts[item]++;
            }
            else
            {
                itemCounts[item] = 1;
            }
        }

        // Wrap the keys in a searchable list
        List<T> keys = new List<T>(itemCounts.Keys);

        // Decrease the count for each occurence of the item in the second collection
        foreach (T item in bar)
        {
            // Try to find a key for the item
            // The keys of a dictionary are compared by reference, so we have to
            // find the original key that is equivalent to the "item"
            // You may want to override ".Equals" to define what it means for
            // two "T" objects to be equal
            T key = keys.Find(
                delegate(T listKey)
                {
                    return listKey.Equals(item);
                });

            // Check if a key was found
            if(key != null)
            {
                itemCounts[key]--;
            }
            else
            {
                // There was no occurence of this item in the first collection, thus the collections are not equal
                return false;
            }
        }

        // The count of each item should be 0 if the contents of the collections are equal
        foreach (int value in itemCounts.Values)
        {
            if (value != 0)
            {
                return false;
            }
        }

        // The collections are equal
        return true;
    }
}

Answer 5

Вы могли бы использовать Хэш - набор.Посмотрите на Установленные значения способ.

Answer 6

Редактировать:Как только я задал вопрос, я понял, что это действительно работает только для наборов - это не будет должным образом работать с коллекциями, в которых есть дублирующиеся элементы.Например, { 1, 1, 2 } и { 2, 2, 1 } будут считаться равными с точки зрения этого алгоритма.Однако, если ваши коллекции являются наборами (или их равенство можно измерить таким образом), я надеюсь, что вы найдете приведенное ниже полезным.

Решение, которое я использую, это:

return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;

Linq выполняет работу со словарем под прикрытием, так что это тоже O (N).(Обратите внимание, это значение равно O (1), если коллекции разного размера).

Я провел проверку работоспособности, используя метод "SetEqual", предложенный Дэниелом, метод OrderBy / SequenceEquals, предложенный Игорем, и мое предложение.Результаты приведены ниже, они показывают O (N * LogN) для Игоря и O (N) для меня и Даниэля.

Я думаю, что простота кода Linq intersect делает его предпочтительным решением.

__Test Latency(ms)__
N, SetEquals, OrderBy, Intersect    
1024, 0, 0, 0    
2048, 0, 0, 0    
4096, 31.2468, 0, 0    
8192, 62.4936, 0, 0    
16384, 156.234, 15.6234, 0    
32768, 312.468, 15.6234, 46.8702    
65536, 640.5594, 46.8702, 31.2468    
131072, 1312.3656, 93.7404, 203.1042    
262144, 3765.2394, 187.4808, 187.4808    
524288, 5718.1644, 374.9616, 406.2084    
1048576, 11420.7054, 734.2998, 718.6764    
2097152, 35090.1564, 1515.4698, 1484.223

Answer 7

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

public class SetComparer<T> : IEqualityComparer<IEnumerable<T>> 
where T:IComparable<T>
{
    public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
    {
        if (first == second)
            return true;
        if ((first == null) || (second == null))
            return false;
        return first.ToHashSet().SetEquals(second);
    }

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

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

        return hash;
    }
}

Здесь это реализация ToHashSet (), которую я использовал.Тот Самый алгоритм хэш- кода происходит из эффективной Java (через Джона Скита).

Answer 8

static bool SetsContainSameElements<T>(IEnumerable<T> set1, IEnumerable<T> set2) {
    var setXOR = new HashSet<T>(set1);
    setXOR.SymmetricExceptWith(set2);
    return (setXOR.Count == 0);
}

Для решения требуется .NET 3.5 и System.Collections.Generic пространство имен. По данным Microsoft, SymmetricExceptWith является O (n + m) операция, с n представляющий количество элементов в первом наборе и m представляющий количество элементов во втором.Вы всегда можете добавить средство сравнения равенства к этой функции, если это необходимо.

Answer 9

Почему бы не использовать .За исключением()

// Create the IEnumerable data sources.
string[] names1 = System.IO.File.ReadAllLines(@"../../../names1.txt");
string[] names2 = System.IO.File.ReadAllLines(@"../../../names2.txt");
// Create the query. Note that method syntax must be used here.
IEnumerable<string> differenceQuery =   names1.Except(names2);
// Execute the query.
Console.WriteLine("The following lines are in names1.txt but not names2.txt");
foreach (string s in differenceQuery)
     Console.WriteLine(s);

http://msdn.microsoft.com/en-us/library/bb397894.aspx

Answer 10

Если вы используете Долженствующий, вы можете использовать ShouldAllBe с Contains .

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

collection1.ShouldAllBe(item=>collection2.Contains(item)); // true

И, наконец, вы можете написать расширение.

public static class ShouldlyIEnumerableExtensions
{
    public static void ShouldEquivalentTo<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
    {
        list.ShouldAllBe(l => equivalent.Contains(l));
    }
}

Обновить

Необязательный параметр существует на Должно быть способ.

collection1.ShouldBe(collection2, ignoreOrder: true); // true

Answer 11

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

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

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 12

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

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

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

Answer 13

Вот вариант моего метода расширения ответа 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 14

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

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 15

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

Answer 16

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

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

Пожалуйста, прочтите комментарии от меня и мистера.Шнайдера к его посту, за который проголосовало больше всего.

Джеймс

Answer 17

Допуск дубликатов в 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 18

Это простое решение заставляет IEnumerableуниверсальный тип для реализации IComparable.Из - за OrderByэто определение.

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

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