質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう！

質問する

ただいまの
回答率

90.61%

  • C#

    6849questions

    C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

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

受付中

回答 3

投稿

  • 評価
  • クリップ 1
  • VIEW 191
nanana71

nanana71

score 2

 前提・実現したいこと

  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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3 件

link

+6

こんなのどうでしょう？ 

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();

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

link

+2

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/07/11 18:46

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

    キャンセル

  • 2018/07/12 18:00

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

    キャンセル

  • 2018/07/12 18:52

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

    キャンセル

  • 2018/07/17 09:28

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

    キャンセル

  • 2018/07/18 13:33

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

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

    キャンセル

  • 2018/07/18 13:47

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

    キャンセル

  • 2018/07/18 16:02

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

    キャンセル

link

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう！

  • ただいまの回答率 90.61%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる
質問する

関連した質問

同じタグがついた質問を見る

  • C#

    6849questions

    C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

SNSアカウントでログイン

  • Facebookでログイン
  • Twitterでログイン
  • Googleでログイン
  • Githubでログイン
  • Hatenaでログイン

teratailアカウントでログイン

思考するエンジニアのためのQ&Aサイト「teratail」について詳しく知る