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

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

Оказывается, 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

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;

    }

Edit: насколько я могу судить, это в том же порядке, что и самый эффективный алгоритм. Этот алгоритм имеет 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

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

Answer 6

В случае отсутствия повторов и порядка, следующий 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 (через Джона Скита).

Answer 7

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

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

Если вы используете mustly , вы можете использовать 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));
    }
}

UPDATE

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

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

Answer 10

Почему бы не использовать .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