5

私は自分の問題に関するいくつかの記事を見つけようとしましたが、私のアプリケーションに関連するものや意味のあるものは何も見つかりませんでした。これが私の問題です：

（> 20,000）アイテムのリストが2つあります。

各リストの各アイテムを、反対のリストのすべてのアイテムと照合する必要があります。

このようなものの実装：

    foreach(var item1 in List1)
    {
         foreach(var item2 in List2)
         {
              // Check item 1 against item 2. 
              // Check item 2 against item 1.
         }
    }

チェックのために行われた作業のため、非常に遅く、使用できません。

このようなチェックが必要なアイテムのこれらの大きなリストを処理するためのより効率的な方法はありますか？

私が提供できるより多くの情報があれば私に知らせてください。ヘルプ/提案をありがとう。

C＃.NET3.5を使用しています

編集：チェックを簡単に説明してみましょう。

item1とitem2は、パスシステムの一部です。item1とitem2は、N個の他のアイテムによって接続されています。item1がitem2に接続されているか（有効なパス）、item2がitem1に接続されているかどうかを確認しています。item1-> item2の場合、item2->item1よりも想定できません。したがって、両方のチェックが必要です。

データベースには、item1->item2およびif/ howitem2->item1の情報が含まれています。チェックの中には、チェックを行うためのサービスへの名前付きパイプ呼び出しがあります。サービスはすべてのパスチェックを実行し、item1->item2などの場合に戻ります。

4

5 に答える 5

4

それはO(N * M)チェックです。

あるキーまたは他のキーの同等性を比較しているだけの場合は、妥当なハッシュコードとキーの適切な分散を前提として、O（N + M）の反復を回避できます。.NETでこれを行う最も簡単な方法は、LINQ結合を使用することです。

var pairs = from x in List1
            join y in List2 on x.Key1 equals y.Key2
            select new { x, y}; // Or whatever

foreach (var pair in pairs)
{
    // Process each match
}

もちろん、平等をチェックしていない場合、これは役に立ちません...しかし、より多くのコンテキストなしで具体的な助けを与えることはほとんど不可能です。

于 2012-06-20T17:22:58.113 に答える
2

長いループ + データベース クエリ = ひどいパフォーマンス。

最初にいくつかのクエリを実行し、必要なデータを取得してから、そのデータに対して N x M のチェックを実行する必要があります。

もちろん、これは必ずしも可能ではありません。実行しているチェックの種類によって異なります。

于 2012-06-20T17:21:39.100 に答える
1

反復ごとにデータベースにリクエストが送信される状況を回避するようにしてください。可能であれば、ループの外側でオールインワンクエリを実行するか、ループの外側で必要なデータをフェッチしてから、このデータをチェックしてみてください。

すべてチェック操作に依存します。だからそれらを説明してください。しかしとにかく、反復が独立している場合は、PLINQとタスク並列ライブラリを使用してループを並列化することもできます

データ並列処理（タスク並列ライブラリ）

方法：単純なParallel.ForEachループを作成する

于 2012-06-20T17:22:42.500 に答える
1

各テーブルの両側をハッシュ テーブル (O(n)) に変換し、各リストをスキャンし、他のテーブルで O(1) ルックアップを実行して、現在のアイテム (o(n) 全体) が含まれているかどうかを確認することをお勧めします。 ）。これにより、全体的に O(n) になります。

〜1,000,000のリストで同様のことを行いましたが、通常、覚えている範囲から〜1秒の範囲で終了します。

于 2014-09-17T21:26:18.053 に答える
-1

ラムダ式と Linq

時間を節約し、ループを避けます。あなたが達成しようとしているものは何でも、LINQ クエリで達成できると確信しています。

たとえば、別のコレクション内の値を検索したり、別のコレクション内のアイテムのコレクションを検索したりします。

次の例は、別のコレクションに含まれているアイテムのコレクションを ID で取得する方法を示しています。たとえば、名前で並べ替えられています。

var result = from x in List1
         where (from c in List2
                select c.Id).Contains(x.Id)
                select x).OrderByDescending(x => x.Name);
于 2012-06-20T17:24:51.080 に答える