2つのListに共通する要素を抽出する

Question

前提・実現したいこと

1. Guidを格納しているListが2つあり、両方(targetList, searchList)に存在する要素を抽出すること
2. 結果(resultList)はtargetListの順序に格納されること

上記2点を満たす処理を実装したいです。

・targetList - 検索対象のリスト
[0]AAAA-AAAA
[1]BBBB-BBBB
[2]CCCC-CCCC
[3]DDDD-DDDD

・searchList - 検索条件のリスト
[0]CCCC-CCCC
[1]AAAA-AAAA

・resultList- 検索結果のリスト
[0]AAAA-AAAA
[1]CCCC-CCCC
※以下の順序はNG
[0]CCCC-CCCC
[1]AAAA-AAAA

発生している問題・エラーメッセージ

上記の条件を満たすため、findAll関数を使用し実装しましたが、
リストに格納された要素数が多いためか、非常に時間がかかっています。
targetList - 約350,000件
searchList - 約50,000件
処理時間 - 約60秒

処理時間を可能な限り短縮したいのですが、
なにか良い方法はありませんでしょうか？
前提条件を満たすことが出来ればListでなくとも構いません。
よろしくお願い致します。

該当のソースコード

List<Guid> resultList = targetList.FindAll(searchList.Contains);

補足情報（FW/ツールのバージョンなど）

・環境：C#4.0
・CPU：Xeon E3-1241
・Memory：16GB

Answer 1

こんなのどうでしょう？

var targetList = Enumerable.Range(0, 350000)
    .Select(i => Guid.NewGuid())
    .ToList();


var searchList = new HashSet<Guid>();
searchList.Add(targetList.Skip(100).First());
searchList.Add(targetList.Skip(101).First());

//最近はこれ
//var searchList = targetList
//    .Skip(100)
//    .Take(2)
//    .ToHashSet();

var resultList = targetList
    .Where(g => searchList.Contains(g))
    .ToList();

Answer 2

searchList.AsParallel().Intersect(targetList.AsParallel()).ToList();はどうでしょう？

順序要件を見逃していたので。
targetList.AsParallel().Intersect(searchList.AsParallel()).ToList();

何というか振りかえると、Whereでよかったんじゃないかとか、即時にリスト化しなきゃならないのかとか、考えるべきことは色々あるように思います。

Comments

[papinianus]

1回しかやってないですが、findAllだと114287ミリ秒かかる環境で、hihijijiさんのHashSetだと58ミリ秒、こちらは165ミリ秒(AsParallelせずに111ミリ秒)でした。

[x_x]

なぜsearchListを2件にしているのかわかりませんが、5000件に増やしたところ(targetList.Skip(100000).Take(5000))、こちらのほうが2桁以上速くなりました。
ところで、これは順序の要件もあるため、targetListとsearchListが逆じゃないですかね？

[papinianus]

私の試行は、50000件でやりました(だったと思います)(2件にした理由は存じません)。同じようにTake(50000)をして、です。
順序要件は完全に見逃してました。ご指摘ありがとうございます(逆にしたからといって速くなったりはしないのですかね、計測してないです)。

[x_x]

こちらの環境と違うんでしょうか？
……すみませんもう一つ違いがありました。ToListをToArrayにして比較したらどうでしょう？

[papinianus]

何回か実行してみましたが、おおよそ変わりませんでした(intersectはだいたい100ミリ秒台でばらつきはあるものの100ミリ秒を切ることはない状況。ToArray()しても。HashSetのWhere部は5、60ミリ秒)。普段測定とかしないので、私がくだらないミスをしているのかもしれないですが…

自分のための参考として、searchlistとtargetlistを逆転させても有意な差は見られませんでした。

[x_x]

> searchlistとtargetlistを逆転させても有意な差は見られませんでした
ええと、それはTake(50000)で生成しているからですね(順序が一緒)。
元の質問では出現順や場所については触れられていない以上、理想的にはsearchListはtargetlistからランダムに抽出してテストしたほうがいいでしょう。
Skipしているのもそれに近似させるためだと思います

[papinianus]

あらためて考えると、検証すべき要素の組み合わせの数は同等だから差がでると思ったのはおかしいように思えてきました(Any()のように短絡で走査を中断できる状況であれば、外側の集団が小さく、内側が大きいほうが有利なような理論的想像を抱いているのですが、今回はそもそもそういうコードになっていませんでした)。
順序がそれに寄与するという点は、未熟で理解が及びませんでした。考えてみます。ありがとうございます。
質問者さま < 本筋から逸れていてすみません。

Answer 3

searchListのvalueをキーにした連想配列を用意してしまえば、targetListのリストの数だけ回せばいいので、searchList+targetList回だけ回せば済みます。