algorithm - 实现高效的配对算法

Question

假设我有两个对象列表，我想将列表 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 运行匹配算法并将结果整理回调用者。

看看有没有帮助。。