.net - アイテムの順序に関係なく、2 つのコレクションが等しいかどうかを比較する

Question

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

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

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

例：

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

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

間違っていると私が考えることができる例は次のとおりです。

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

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

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

注:簡単にするために例では整数を使用しましたが、参照型オブジェクトも使用できるようにしたいと考えています (内容ではなくオブジェクトの参照のみが比較されるため、これらはキーとして正しく動作しません)。

score 122 · Accepted Answer

Microsoft は既にテストフレームワークでこれをカバーしていることが判明しました: CollectionAssert.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

score 105 · Accepted Answer

シンプルでかなり効率的な解決策は、両方のコレクションを並べ替えてから、それらが等しいかどうかを比較することです。

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

このアルゴリズムは O(N*logN) ですが、上記のソリューションは O(N^2) です。

コレクションに特定のプロパティがある場合は、より高速なソリューションを実装できる場合があります。たとえば、両方のコレクションがハッシュセットである場合、重複を含めることはできません。また、ハッシュセットに要素が含まれているかどうかのチェックも非常に高速です。その場合、あなたのアルゴリズムに似たアルゴリズムがおそらく最速です。

score 32 · Accepted Answer

ディクショナリ「dict」を作成し、最初のコレクションの各メンバーに対して、dict[member]++; を実行します。

次に、同じ方法で 2 番目のコレクションをループしますが、メンバーごとに 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;

    }

編集：私が知る限り、これは最も効率的なアルゴリズムと同じ順序です。Dictionary が O(1) ルックアップを使用すると仮定すると、このアルゴリズムは O(N) です。

score 18 · Accepted Answer

これは私の (D.Jennings の影響を強く受けた) 比較メソッドの一般的な実装 (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;
    }
}

score 11 · Accepted Answer

11

Hashsetを使用できます。SetEqualsメソッドを見てください。

于 2008-10-04T04:38:31.400 に答える

score 7 · Accepted Answer

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は 2 番目のセットの要素数を表します。必要に応じて、この関数に等値比較子をいつでも追加できます。

score 7 · Accepted Answer

Shouldlyを使用する場合は、Contains で ShouldAllBe を使用できます。

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

score 5 · Accepted Answer

繰り返しも順序もない場合、次の 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 Skeet による) から来ています。

score 5 · Accepted Answer

編集:これは実際にはセットに対してのみ機能することを提起するとすぐに気付きました-重複したアイテムを持つコレクションを適切に処理しません。たとえば、{ 1, 1, 2 } と { 2, 2, 1 } は、このアルゴリズムの観点からは等しいと見なされます。ただし、コレクションがセットである場合 (またはそれらの等価性をそのように測定できる場合)、以下が役立つことを願っています。

私が使用する解決策は次のとおりです。

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

Linq は内部で辞書処理を行うため、これも O(N) です。(コレクションが同じサイズでない場合は O(1) です)。

Daniel が提案した「SetEqual」メソッド、Igor が提案した OrderBy/SequenceEquals メソッド、および私の提案を使用して、健全性チェックを行いました。結果は以下のとおりで、Igor の場合は O(N*LogN)、私のものと Daniel の場合は 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

score 4 · Accepted Answer

.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

score 2 · Accepted Answer

ある種の重複した投稿ですが、コレクションを比較するための私の解決策を確認してください。とても簡単です。

これにより、順序に関係なく等価比較が実行されます。

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

元の投稿はこちら。

score 1 · Accepted Answer

誰かに役立つ場合に備えて、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;
    }
}

score 1 · Accepted Answer

これは、これよりも改善されたソリューションです。

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

score 0 · Accepted Answer

エリクソンはほぼ正しいです。重複の数で一致させたいので、Bagが必要です。Java では、これは次のようになります。

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

C# には組み込みの Set 実装があると確信しています。最初にそれを使用します。パフォーマンスに問題がある場合は、常に別の Set 実装を使用できますが、同じ Set インターフェイスを使用できます。

score 0 · Accepted Answer

多くの場合、唯一の適切な回答は Igor Ostrovsky のものであり、他の回答はオブジェクトハッシュコードに基づいています。しかし、オブジェクトのハッシュコードを生成するときは、オブジェクト Id フィールド (データベースエンティティの場合) などの IMMUTABLE フィールドのみに基づいて生成します。

つまり、2 つのコレクションを比較すると、異なるアイテムのフィールドが等しくなくても、compare メソッドの結果は true になる可能性があります。コレクションを詳細に比較するには、Igor のメソッドを使用して IEqualirity を実装する必要があります。

私と Schnider 氏の最も投票された投稿に対するコメントを読んでください。

ジェームズ

score 0 · Accepted Answer

この問題には多くの解決策があります。重複を気にしない場合は、両方を並べ替える必要はありません。まず、アイテムの数が同じであることを確認します。その後、コレクションの 1 つを並べ替えます。次に、並べ替えられたコレクションの 2 番目のコレクションから各アイテムをビンサーチします。指定されたアイテムが見つからない場合は、停止して false を返します。これの複雑さ: - 最初のコレクションのソート: N Log(N) - 2 番目から 1 番目への各項目の検索: NLOG(N) したがって、それらが一致し、すべてを検索すると仮定すると、 2*N*LOG(N) になります。これは、両方の並べ替えの複雑さに似ています。また、これにより、違いがある場合に早期に停止できるという利点があります。ただし、この比較に入る前に両方がソートされていて、qsort などを使用してソートしようとすると、ソートのコストが高くなることに注意してください。これには最適化があります。要素の範囲がわかっている小さなコレクションに最適な別の方法は、ビットマスクインデックスを使用することです。これにより、O(n) パフォーマンスが得られます。もう 1 つの方法は、ハッシュを使用して検索することです。小さなコレクションの場合、通常、並べ替えまたはビットマスクインデックスを実行する方がはるかに優れています。Hashtable には局所性が悪いという欠点があるため、その点に注意してください。繰り返しますが、それはあなたがそうしない場合に限られます。重複は気にしません。重複を考慮したい場合は、両方を並べ替えます。

score 0 · Accepted Answer

重複した質問のこの回答、および回答の下のコメント、および @brian-genisio の回答に基づいて、私はこれらを思いつきました:

        public static bool AreEquivalentIgnoringDuplicates<T>(this IEnumerable<T> items, IEnumerable<T> otherItems)
        {
            var itemList = items.ToList();
            var otherItemList = otherItems.ToList();
            var except = itemList.Except(otherItemList);
            return itemList.Count == otherItemList.Count && except.IsEmpty();
        }

        public static bool AreEquivalent<T>(this IEnumerable<T> items, IEnumerable<T> otherItems)
        {
            var itemList = items.ToList();
            var otherItemList = otherItems.ToList();
            var except = itemList.Except(otherItemList);
            return itemList.Distinct().Count() == otherItemList.Count && except.IsEmpty();
        }

これら 2 つのテスト:

        [Test]
        public void collection_with_duplicates_are_equivalent()
        {
            var a = new[] {1, 5, 5};
            var b = new[] {1, 1, 5};

            a.AreEquivalentIgnoringDuplicates(b).ShouldBe(true); 
        }

        [Test]
        public void collection_with_duplicates_are_not_equivalent()
        {
            var a = new[] {1, 5, 5};
            var b = new[] {1, 1, 5};

            a.AreEquivalent(b).ShouldBe(false); 
        }

score 0 · Accepted Answer

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

.net - アイテムの順序に関係なく、2 つのコレクションが等しいかどうかを比較する

20 に答える 20

Related

Reference