13

私はクラスを持っています：

class SomeClass
{
   public string Name{get;set;}
   public int SomeInt{get;set;}
}


class SomeComparison: IEqualityComparer<SomeClass>
{
     public bool Equals(SomeClass s, SomeClass d)
     {
         return s.Name == d.Name;
     }

     public int GetHashCode(SomeClass a)
     {
         return (a.Name.GetHashCode() * 251);
     }
}

私はまた2つの大きなList<SomeClass>と呼ばれるlist1とlist2

私が持っていた前に：

 var q = (from a in list1
         from b in list2
         where a.Name != b.Name
         select a).ToList();

実行には約1分かかりました。今私が持っています：

var q =  list1.Except(list2,new SomeComparison()).ToList();

そしてそれは1秒未満かかります！

Exceptメソッドが何をするのか理解したいと思います。このメソッドは、各リストのハッシュテーブルを作成してから、同じ比較を実行しますか？この比較をたくさん実行する場合は、代わりにハッシュテーブルを作成する必要がありますか？

編集

今、リストを持っている代わりに、私は2つHashSet<SomeClass>と呼ばれ hashSet1ていますhashSet2

私がする時：

   var q = (from a in hashSet1
           form b in hashSet2
           where a.Name != b.Name
           select a).ToList();

それでもまだ長い時間がかかります...私は何が間違っているのですか？

4

5 に答える 5

29

あなたの推測は近かった - Linq to Objects Except拡張メソッドは、HashSet<T>渡された 2 番目のシーケンスに内部的に、したがって、全体的な労力は O(n+m) です。ここで、n と m は入力シーケンスの長さです。各要素を少なくとも 1 回は確認する必要があるため、これが期待できる最善の方法です。

これがどのように実装されるかを確認するには、Jon Skeet の EduLinq シリーズをお勧めします。ここでは、実装の一部であり、章全体Exceptへのリンクです。

private static IEnumerable<TSource> ExceptImpl<TSource>(
    IEnumerable<TSource> first,
    IEnumerable<TSource> second,
    IEqualityComparer<TSource> comparer)
{
    HashSet<TSource> bannedElements = new HashSet<TSource>(second, comparer);
    foreach (TSource item in first)
    {
        if (bannedElements.Add(item))
        {
            yield return item;
        }
    }
}

一方、最初の実装では、最初のリストの各要素を 2 番目のリストの各要素と比較します。クロス積を実行しています。これには n m の操作が必要になるため、O(n m) で実行されます。n と m が大きくなると、これは法外に遅くなり、非常に速くなります。(また、この解決策は、重複した要素を作成するため、そのままでは間違っています)。

于 2012-04-22T16:22:08.983 に答える
2

2 つのコード例は、同じ結果を生成しません。

古いコードは、2 つのリストのデカルト積を作成します。

つまりa、list1 の各要素を複数回返します。つまりb、list2 の各要素が と等しくない場合に1 回aです。

「大きな」リストでは、これには長い時間がかかります。

于 2012-04-22T16:35:13.817 に答える
2

from a in list1 from b in list2要素を作成し、 !list1.Count * list2.Countと同じではありません。list1.Except(list2)

list1要素{ a, b, c, d }とlist2要素がある場合{ a, b, c }、最初のクエリは次のペアを生成します。 

(a、a)、(a、b)、(a、c)、  
(b、a)、(b、b)、(b、c)、  
(c,a)、(c,b)、(c,c)、  
(d,a)、(d,b)、(d,c)

等しい項目を除外するため、結果は次のようになります

(a,a) , (a,b), (a,c),  
(b,a)、(b,b)、(b,c)、  
(c,a), (c,b), (c,c) ,  
(d,a)、(d,b)、(d,c)

ペアの最初の要素のみを選択するため、次のようになります。

{ a, a, b, b, c, c, d, d, d }

2 番目のクエリは{ a, b, c, d }マイナス{ a, b, c }、つまり{ d }.

ハッシュ テーブルが使用されていない場合、Exclude実行中のネストされたループO(m*n)が発生します。ハッシュ テーブルを使用すると、クエリはおおよそ次のように実行されますO(n)(ハッシュ テーブルを埋めるためのコストは無視します)。

于 2012-04-22T16:36:55.277 に答える
0

これが私が考える方法です。

IEnumerable<T> Except<T>(IEnumerable<T> a,IEnumerable<T> b)
{
    return a.Where(x => !b.Contains(x)).Distinct();
}
于 2014-02-24T11:06:58.487 に答える