9

私は2つのリストAとB（リスト）を持っています。それらが最も安価な方法で等しいかどうかを判断する方法は？'（AマイナスB）和集合（BマイナスA）=空集合'のように書くか、それらを結合して要素の量を数えることができますが、かなり高価です。回避策はありますか？

4

5 に答える 5

18

リスト項目の順序が適切である場合:

bool areEqual = a.SequenceEqual(b);

リストを順序なしセットとして扱う場合:

// assumes that the list items are ints
bool areEqual = new HashSet<int>(a).SetEquals(b);

(その機能が必要な場合はSequenceEqual、メソッドとHashSet<T>コンストラクターの両方に、パラメーターを受け取るオーバーロードがあります。)IEqualityComparer<T>

于 2009-06-03T15:14:46.443 に答える
7

それは、リストをどのように解釈するかによって異なります。

それらをタプルと見なす場合（リスト内の要素の順序が重要になるため）、次のコードを使用できます。

    public bool AreEqual<T>(IList<T> A, IList<T> B)
    {
        if (A.Count != B.Count)
            return false;
        for (int i = 0; i < A.Count; i++)
            if (!A[i].Equals(B[i])) 
                return false;
    }

リストをセットと見なす場合 (要素の順序は関係ありません)、間違ったデータ構造を使用していると思います:

    public bool AreEqual<T>(IList<T> A, IList<T> B)
    {
        HashSet<T> setA = new HashSet<T>(A);
        return setA.SetEquals(B);
    }
于 2009-06-03T14:51:04.493 に答える
1

「リストが等しい」という意味に依存します。それらに同じオブジェクトが含まれていることを意味する場合、ダニエルが提案したソリューションは問題ありません.2つのリストを Union() してアイテムを数えるだけです。

「等しい」とは、同じ順序で同じアイテムがあることを意味する場合、両方のリストのカウントを比較したほうがよいでしょう。カウントが同じ場合は、単純に反復してfor loop両方の各要素を比較します同じインデックスにリストします。きれいではありませんが、速くなることはほとんどありません。

于 2009-06-03T14:47:43.783 に答える
1

実際には、リストがソートされていない限り、ショートカットはありません。ソートされている場合は、要素を 1 つずつ比較できます。そして明らかに、順序は問題ではないと思います。さもなければ、それらを 1 つずつ比較できることも明らかです。

それ以外の場合、アイテムの大きなリストに対して取得できる最も効率的なアルゴリズムは、おそらく次のようなものであり、ハッシュテーブルを使用して見たものを追跡することをお勧めします（警告：テストしていませんが、テストする必要があります私が何を得ているのかを明確にしてください。）

public static bool IsEqual<T>(this List<T> x1, List<T> x2)
{
    if(x1.Count != x2.Count) return false;

    var x1Elements = new Dictionary<T, int>();

    foreach(var item in x1)
    {
        int n; x1Elements.TryGetValue(item, out n);
        x1Elements[item] = n+1;
    }

    foreach(var item in x2)
    {
        int n; x1Elements.TryGetValue(item, out n);
        if(n <= 0) return false; // this element was in x2 but not x1
        else x1Elements[item] = n-1;
    }

    // make sure x1 didn't have any elements
    // that weren't in x2

    return x1Elements.Values.All(x => x == 0);
}
于 2009-06-03T14:49:30.333 に答える
-1

最初のショット - それらに同じ項目が含まれている場合、両方のリストの結合には、両方のリストのいずれかと同じ数の項目が含まれている必要があります。

listA.Union(listB).Count() == listA.Count()

注: 1 つのリストが空の場合は失敗します。

しかし、それはおそらくまだO(n²)操作です。

別の解決策 - リストは同じ長さである必要があり、リスト A からリスト B を差し引いた部分に要素が含まれていてはなりません。

(listA.Count() == listB.Count()) && !listA.Except(listB).Any()
于 2009-06-03T14:42:47.897 に答える