C＃で最も速いメンバーシップルックアップを提供するものは何ですか？

Question

は、なぜ我々は、ラムダ式内の任意のネイティブコンテナにContains()を使用してメンバーシップの検索を避けるために持っているのですか？

Answer 1

のは、次のことを考えてみましょう：

今

var source = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 
var matches = new[] { 12, 2, 19, 8, 40, 12, 123, 121, 1212, 122334, 2, 102, 10, 29 }; 
foreach (var item in source.Where(i => matches.Contains(i))) 
{ 
    Console.WriteLine(item); 
} 

、我々はそれを書き出しするかどうかを知る前と比較する必要がありますどのように多くの項目matchesiで考えてみましょう：

1: 14 
2: 2 
3: 14 
5: 14 
6: 14 
7: 14 
8: 4 
9: 14 
10: 13 

ながら答えは、我々はいけないということである場合は特に、我々は時々我々が一般的にない、非常に素早く答えを得るので、私たちは10個の項目を処理するために、103回の比較を持っています。我々はまた、我々はすでにチェックした値（2は二回matchesであるという事実を）比較する時間を無駄に。

我々はO(m)操作をやっているので、n回アルゴリズムがO(nm)です。

我々はとのより良い行うことができます。

var source = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 
var matches = new HashSet<int> { 12, 2, 19, 8, 40, 12, 123, 121, 1212, 122334, 2, 102, 10, 29 }; 
foreach (var item in source.Where(i => matches.Contains(i))) 
{ 
    Console.WriteLine(item); 
} 

ハッシュセットにContainsは、アルゴリズムは全体的にそれができると同じくらい良いですO(n)、あるO(1)ですので。

注意すべきいくつかの重要な事柄ですけれども：

1. 上記はどんなタイプmatchesそれはそう、生産SQLでWHERE句のCONTAINS一部に変えられるでしょうし、次いで、データベース上で行われている場合それは（CONTAINSが連鎖=の一定数までまだ=よりもはるかに遅いですが、劇中での要因が異なっている）問題ではありません。

2. 比較的小さな一致のセットでは、O(n)のコストがContainsであることは、ハッシュセットの作成と検索の一定コストよりも安いです。 （上記の例はおそらくほぼ同じ時間で実行されます）。

コストがあるときに、それは決してしないためのものではないのですが、あなたはコストとそれらがどのようにソースデータとそれらが実行されている方法によって影響を受けているの知っておくべきもの、およびパフォーマンスを向上させる方法特に高い。

私たちがラムダを使用していることは特に重要ではありませんが、いくつかのコードを素早く書くことができるという点を除けば、隠された非効率なコードを素早く書くことができます。 O(nm)がより明確になります。 HashSetの の例外を除いて