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

162

Я хотел бы сравнить две коллекции (в 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 #), но давать ответ на любом языке, который вы пожелаете, это не имеет значения.

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

mbillard
источник
1
Как насчет алгоритма? Все ответы, связанные сравнением чего-либо, общие списки сравнивают linq и т. Д. Действительно, мы обещали кому-то, что никогда не будем использовать алгоритм как старомодный программист?
Нури ЙИЛМАЗ
Вы не проверяете на равенство, вы проверяете на эквивалентность. Это придирчиво, но важное различие. И очень давно. Это хороший Q + A.
CAD bloke
Возможно, вас заинтересует этот пост , в котором обсуждается настроенная версия словарного метода, описанного ниже. Одна из проблем, связанных с большинством простых подходов к словарю, заключается в том, что они не обрабатывают нули должным образом, поскольку класс Dictionary в .NET не допускает нулевые ключи.
ChaseMedallion

Ответы:

112

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

замечания

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

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

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
Охад Шнайдер
источник
7
Я не уверен на 100%, но думаю, что ваш ответ нарушает условия использования Microsoft против реверс-инжиниринга.
Ян Даллас
1
Здравствуйте, Охад! Пожалуйста, прочитайте следующую долгую дискуссию в теме: stackoverflow.com/questions/371328/… Если вы измените хэш-код объекта, когда он находится в хэш-наборе, он прервется с правильным действием хэш-набора и может вызвать исключение. Правило следующее: если два объекта равны - они должны иметь одинаковый хэш-код. Если два объекта имеют одинаковый хэш-код - для них не обязательно быть равными. Хэш-код должен оставаться неизменным на протяжении всего срока службы объекта! Вот почему вы привели ICarePareable и IEqualrity.
Джеймс Ройтер
2
@JamesRoeiter Возможно, мой комментарий вводил в заблуждение. Когда в словаре встречается хеш-код, который он уже содержит, он проверяет фактическое равенство с EqualityComparer(либо предоставленным вами, либо EqualityComparer.Defaultвы можете проверить Reflector или источник ссылки, чтобы проверить это). True, если объекты изменяются (и, в частности, изменяются их хэш-коды) во время работы этого метода, тогда результаты являются неожиданными, но это просто означает, что этот метод не является поточно-ориентированным в этом контексте.
Охад Шнайдер
1
@JamesRoeiter Предположим, что x и y - два объекта, которые мы хотим сравнить. Если у них разные хеш-коды, мы знаем, что они разные (потому что равные элементы имеют одинаковые хеш-коды), и приведенная выше реализация верна. Если они имеют одинаковый хэш-код, реализация словаря проверит фактическое равенство, используя указанное EqualityComparer(или, EqualityComparer.Defaultесли ни один не был указан), и снова реализация верна.
Охад Шнайдер
1
@CADbloke метод должен быть назван Equalsиз-за IEqualityComparer<T>интерфейса. То, на что вы должны смотреть - это имя самого компаратора . В этом случае это MultiSetComparerимеет смысл.
Охад Шнайдер
98

Простое и довольно эффективное решение - отсортировать обе коллекции и сравнить их на равенство:

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

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

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

Сани Сингх Хуттунен
источник
1
Вам просто нужно добавить использование System.Linq; первый, чтобы заставить его работать
Младший Mayhé
если этот код находится в цикле, а collection1 обновляется, а collection2 остается нетронутым, обратите внимание, даже если обе коллекции имеют один и тот же объект, отладчик будет показывать false для этой «равной» переменной.
Младший Mayhé
5
@ Чолки - я считаю, что OrderBy необходим. См .: dotnetfiddle.net/jA8iwE
Бретт,
Какой другой ответ упоминался как «выше»? Возможно stackoverflow.com/a/50465/3195477 ?
UuDdLrLrSs
32

Создайте словарь «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) поисков.

Дэниел Дженнингс
источник
Это почти то, что я хочу. Тем не менее, я хотел бы иметь возможность сделать это, даже если я не использую целые числа. Я хотел бы использовать ссылочные объекты, но они не работают как ключи в словарях.
mbillard
Моно, твой вопрос спорный, если твои Предметы несопоставимы. Если они не могут быть использованы в качестве ключей в словаре, решение не доступно.
Сколима
1
Я думаю, что Моно означает, что ключи не сортируются. Но решение Daniel явно предназначено для реализации с помощью хеш-таблицы, а не дерева, и будет работать до тех пор, пока есть тест на эквивалентность и хеш-функция.
Эриксон
Конечно, за помощь проголосовали, но не приняли, так как в ней отсутствует важный момент (о котором я расскажу в своем ответе).
mbillard
1
FWIW, вы можете упростить свой последний цикл foreach и оператор return с помощью этого:return dict.All(kvp => kvp.Value == 0);
Тайсон Уильямс
18

Это моя (под сильным влиянием Д. Дженнингса) общая реализация метода сравнения (в 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;
    }
}
mbillard
источник
12
Хорошая работа, но Примечание: 1. В отличие от решения Даниэля Дженнингса, это не O (N), а скорее O (N ^ 2), из-за функции find внутри цикла foreach в коллекции bar; 2. Вы можете обобщить метод для принятия IEnumerable <T> вместо ICollection <T> без дальнейшей модификации кода
Ohad Schneider
The keys of a dictionary are compared by reference, so we have to find the original key that is equivalent to the "item"- это неправда. Алгоритм основан на неправильных предположениях, и хотя он работает, он ужасно неэффективен.
Антонин Лейсек
10

Вы могли бы использовать Hashset . Посмотрите на метод SetEquals .

Жоэль Говро
источник
2
Конечно, использование HashSet предполагает отсутствие дубликатов, но если так, то HashSet - лучший путь
Mark Cidade
7

Если вы используете Следует , вы можете использовать Следует с помощью Содержит.

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

ОБНОВИТЬ

В методе ShouldBe существует необязательный параметр .

collection1.ShouldBe(collection2, ignoreOrder: true); // true
Пьер-Лайонел Сгард
источник
1
Я только что нашел на последнюю версию , что есть параметр bool ignoreOrderна ShouldBe методе.
Пьер-Лайонел
5

РЕДАКТИРОВАТЬ: я понял, как только я поставил, что это действительно работает только для наборов - он не будет правильно работать с коллекциями, которые имеют дубликаты предметов. Например, {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 делает его предпочтительным решением.

__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

источник
Единственная проблема с этим кодом заключается в том, что он работает только при сравнении типов значений или при сравнении указателей с ссылочными типами. У меня может быть два разных экземпляра одного и того же объекта в коллекциях, поэтому я должен иметь возможность указать, как сравнивать каждый из них. Можете ли вы передать делегат сравнения в метод пересечения?
mbillard
Конечно, вы можете передать делегат сравнения. Но обратите внимание на указанное выше ограничение в отношении наборов, которое я добавил, что значительно ограничивает его применимость.
Метод Intersect возвращает отдельную коллекцию. Учитывая a = {1,1,2} и b = {2,2,1}, a.Intersect (b) .Count ()! = A.Count, что заставляет ваше выражение корректно возвращать false. {1,2} .Count! = {1,1,2} .Count См. Ссылку [/ link] (обратите внимание, что обе стороны выделены перед сравнением.)
Гриффин
5

В случае отсутствия повторов и порядка, следующий 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 (), которую я использовал. Алгоритм хэш - код приходит от Effective Java (путем Jon тарелочкам).

Охад Шнайдер
источник
Какой смысл в Serializable для класса Comparer? : o Также вы можете изменить ввод, чтобы ISet<T>выразить, что он предназначен для наборов (то есть без дубликатов).
nawfal
@nawfal спасибо, не знаю, о чем я думал, когда пометил его как Serializable ... Что касается ISet, идея заключалась в том, чтобы рассматривать IEnumerableнабор как (потому что у вас есть IEnumerableдля начала), несмотря на то, что 0 повышений в более чем 5 лет, которые, возможно, не были самой острой идеей: P
Охад Шнайдер
4
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 представляет количество элементов во втором. При необходимости вы всегда можете добавить в эту функцию средство сравнения на равенство.

palswim
источник
3

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

// 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

Korayem
источник
2
Exceptне будет работать для подсчета дубликатов. Он вернет true для наборов {1,2,2} и {1,1,2}.
Кристиан Диаконеску
@CristiDiaconescu вы можете сначала сделать «.Distinct ()», чтобы удалить любые дубликаты
Korayem
ОП просит [1, 1, 2] != [1, 2, 2]. Использование Distinctсделает их похожими.
Кристиан Диаконеску
2

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

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

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

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

user329244
источник
1

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

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

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

Джеймс А. Розен
источник
1

Вот мой вариант метода ответа 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;
    }
}
Эрик Дж.
источник
Насколько хорошо это работает, какие-нибудь идеи?
Nawfal
Я использую это только для небольших коллекций, поэтому не думал о сложности Big-O и не делал сравнительный анализ. Параметр HaveMismatchedElements имеет значение O (M * N), поэтому он может не работать с большими коллекциями.
Эрик Дж.
Если IEnumerable<T>s являются запросами, то вызов Count()не является хорошей идеей. Подход оригинального ответа Охада - проверить, являются ли они ICollection<T>лучшей идеей.
nawfal
1

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

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]);
    }
N73k
источник
0

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


источник
0

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

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

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

Джеймс

Джеймс Ройтер
источник
0

С учетом дубликатов в 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;
    }
Джош Густ
источник
0

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

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

bool equal = collection1.OrderBy(i => i?.GetHashCode())
   .SequenceEqual(collection2.OrderBy(i => i?.GetHashCode()));
Джо Хэм
источник
0

При сравнении для целей утверждений модульного тестирования может иметь смысл выбросить некоторую эффективность в окно и просто преобразовать каждый список в строковое представление (csv) перед выполнением сравнения. Таким образом, стандартное тестовое сообщение подтверждения будет отображать различия в сообщении об ошибке.

Использование:

using Microsoft.VisualStudio.TestTools.UnitTesting;

// define collection1, collection2, ...

Assert.Equal(collection1.OrderBy(c=>c).ToCsv(), collection2.OrderBy(c=>c).ToCsv());

Метод расширения помощника:

public static string ToCsv<T>(
    this IEnumerable<T> values,
    Func<T, string> selector,
    string joinSeparator = ",")
{
    if (selector == null)
    {
        if (typeof(T) == typeof(Int16) ||
            typeof(T) == typeof(Int32) ||
            typeof(T) == typeof(Int64))
        {
            selector = (v) => Convert.ToInt64(v).ToStringInvariant();
        }
        else if (typeof(T) == typeof(decimal))
        {
            selector = (v) => Convert.ToDecimal(v).ToStringInvariant();
        }
        else if (typeof(T) == typeof(float) ||
                typeof(T) == typeof(double))
        {
            selector = (v) => Convert.ToDouble(v).ToString(CultureInfo.InvariantCulture);
        }
        else
        {
            selector = (v) => v.ToString();
        }
    }

    return String.Join(joinSeparator, values.Select(v => selector(v)));
}
crokusek
источник