algorithm - 効率的なペアマッチングアルゴリズムの実装

Question

オブジェクトのリストが2つあり、リスト1のすべてのオブジェクトをリスト2のすべてのオブジェクトと一致させたいとします。

これはおそらく、すぐに思いつくアルゴリズムでしょう。

for( it_1=list_1.begin() ; it_1!=list_1.end() ; it_1++ )
  {
      for( it_2=list_2.begin() ; it_2!=list_2.end() ; it_2++ )
      {
          //now match 
           match(*it_1,*it_2);
      }

  }

これを行うためのより良い方法があるのだろうか。これにはO（n1 * n2）が必要です。ここで、n1とn2はそれぞれlist_1とlist_2の長さです。

Answer 1

ここでは、探しているサイズと効率に応じてlist1を2つまたは3つの部分に分割し、list2を使用して各スレッドで一致アルゴリズムを実行し、結果を呼び出し元に照合することで、マルチスレッドを利用できます。

それが役立つかどうかを確認してください。