すぐにリストを作成する方法<T>。コンテナ（）

Question

私は「交差している」と思うことをしようとしています（私は正しい名前が何であるか分かりませんが、それはEpicGamesのTim Sweeneyが

// foo and bar have some identical elements (given a case-insensitive match) 
List‹string› foo = GetFoo(); 
List‹string› bar = GetBar(); 

// remove non matches 
foo = foo.Where(x => bar.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList(); 
bar = bar.Where(x => foo.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList(); 

その後、元のファイルから結果を差し引いて、削除した要素を確認します。これは超高速です.Except（）を使用するので、そこにトラブルはありません。

これは、どちらのリストでも（文字列の）〜30,000個の要素でかなり悪い結果になるので、これを行うにはもっと速い方法が必要です。好ましくは、このステップを実行し、後に1つのステップを実行する方法は、すばらしいことになるだろう。私は.Contains（）の代わりに.Exists（）を使ってみましたが、やや遅くなりました。私は少し厚く感じますが、.Except（）と.Intersect（）や.Union（）のいくつかの組み合わせで可能になるはずです。

Answer 1

では、それはこのように行われます交わる：ソートされたリストで

var matches = ((from f in foo 
       select f) 
       .Intersect(
        from b in bar 
        select b, StringComparer.InvariantCultureIgnoreCase)) 

Answer 2

この操作は、対称的な違いと呼ぶことができます。

ハッシュテーブルのような別のデータ構造が必要です。両方のセットの交差をそれに追加し、各セットから交差を差してください。

UPDATE：

私はコードでこれを試して少し時間を得ました。

オリジナル：79499ミリ秒

HashSetの：33ミリところで

私は以下の結果と2〜10文字の長から、50,000文字列のセットでHashSet<T>を使用しましたHashSetにはSymmetricExceptWithというメソッドがありますが、それは私にとってはうまくいくと思っていましたが、実際には両方のセットのさまざまな要素がメソッドに呼び出されるセットに追加されます。おそらく、これは最初の2つのセットを変更せずに残すよりも、あなたが望むものであり、コードはよりエレガントになります。ここ

コードである：

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 

class Program 
{ 
    static void Main(string[] args) 
    { 
     // foo and bar have some identical elements (given a case-insensitive match) 
     var foo = getRandomStrings(); 
     var bar = getRandomStrings(); 

     var timer = new Stopwatch(); 

     timer.Start(); 
     // remove non matches 
     var f = foo.Where(x => !bar.Contains(x)).ToList(); 
     var b = bar.Where(x => !foo.Contains(x)).ToList(); 
     timer.Stop(); 

     Debug.WriteLine(String.Format("Original: {0} ms", timer.ElapsedMilliseconds)); 

     timer.Reset(); 

     timer.Start(); 
     var intersect = new HashSet<String>(foo); 
     intersect.IntersectWith(bar); 

     var fSet = new HashSet<String>(foo); 
     var bSet = new HashSet<String>(bar); 

     fSet.ExceptWith(intersect); 
     bSet.ExceptWith(intersect); 
     timer.Stop(); 

     var fCheck = new HashSet<String>(f); 
     var bCheck = new HashSet<String>(b); 

     Debug.WriteLine(String.Format("Hashset: {0} ms", timer.ElapsedMilliseconds)); 

     Console.WriteLine("Sets equal? {0} {1}", fSet.SetEquals(fCheck), bSet.SetEquals(bCheck)); //bSet.SetEquals(set)); 
     Console.ReadKey(); 
    } 

    static Random _rnd = new Random(); 

    private const int Count = 50000; 

    private static List<string> getRandomStrings() 
    { 
     var strings = new List<String>(Count); 

     var chars = new Char[10]; 

     for (var i = 0; i < Count; i++) 
     { 
      var len = _rnd.Next(2, 10); 

      for (var j = 0; j < len; j++) 
      { 
       var c = (Char)_rnd.Next('a', 'z'); 
       chars[j] = c; 
      } 

      strings.Add(new String(chars, 0, len)); 
     } 

     return strings; 
    } 
} 

Answer 3

はリストに含まO（N）操作されています。並べ替えられたリストや辞書など、別のデータ構造を持っていた場合、時間が大幅に短縮されます。ソートされたリストのキーへのアクセスは通常O（ログN）時間であり、ハッシュでは通常O（1）時間です。

Answer 4

要素が各リスト内で一意である場合は、HashSet

のHashSet（T）クラスは 高性能セット操作を提供し使用することを検討してください。集合は、 要素の重複を含まず、要素が 特定の順序にない コレクションです。

Answer 5

、あなたはバイナリ検索を使用することができます。