☰

2つのコレクションの等価性を比較して、その中のアイテムの順序に関わらず比較する 質問する

tag-icon • tag-icon .net collections comparison equality
2つのコレクションの等価性を比較して、その中のアイテムの順序に関わらず比較する 質問する

2 つのコレクションを (C# で) 比較したいのですが、これを効率的に実装する最適な方法がわかりません。

私は他のスレッドを読みました列挙可能.SequenceEqual、しかしそれはまさに私が探しているものではありません。

私の場合、2 つのコレクションは、両方に同じアイテム (順序に関係なく) が含まれている場合は等しくなります。

例：

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

collection1 == collection2; // true

私が通常行うことは、1 つのコレクションの各項目をループして、それが他のコレクションに存在するかどうかを確認し、次に他のコレクションの各項目をループして、それが最初のコレクションに存在するかどうかを確認することです (長さを比較することから始めます)。

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

ただし、これは完全に正しいわけではなく、おそらく 2 つのコレクションの等価性を比較する最も効率的な方法ではありません。

私が思いつく間違った例は次のとおりです。

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

これは私の実装と同じになります。各アイテムが見つかった回数を数えて、両方のコレクションでカウントが等しいことを確認するだけでよいのでしょうか?

例はある種の C# (疑似 C# と呼びましょう) で書かれていますが、回答はどの言語で書いても構いません。

注記：例では簡単にするために整数を使用しましたが、参照型のオブジェクトも使用できるようにしたいと思います (オブジェクトの参照のみが比較され、コンテンツは比較されないため、キーとして正しく動作しません)。

ベストアンサー1

実は、Microsoft はテスト フレームワークでこれをすでにカバーしています。コレクションアサート.AreEquivalent

備考

2 つのコレクションは、同じ要素が同じ数だけあるが順序は任意である場合に同等です。要素は、値が等しい場合に等しくなりますが、同じオブジェクトを参照している場合は等しくなります。

リフレクタを使用して、AreEquivalent()の背後にあるコードを修正し、対応する等価比較子を作成しました。これは、nullを考慮し、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)
            hash ^= (val == null ? 42 : m_comparer.GetHashCode(val));

        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

または、2 つのコレクションを直接比較したい場合:

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

おすすめ記事