2つのstd :: map間のマッチを見つけるC++の効率的な方法

Question

RGB-Dカメラとテキストファイルでデータセットを取得しました。ここで、データセットの各イメージに対して、タイムスタンプとファイル名が格納されています。私が行うのは、このファイルを解析し、2つのstd :: mapを埋め、1つはrgbイメージ用、もう1つは深度イメージ用です。今、タイムスタンプが交差しないので、私はタイムスタンプに基づいて一致するイメージを見つけるルーチンを書く必要があります。これは私が今までに書いたものです：

typedef map<double,string> StampImageMap; 

... 

vector<string> &vstrImageFilenamesRGB; 
vector<string> &vstrImageFilenamesD; 
vector<double> &vTimestampsRGB; 
vector<double> &vTimestampsDPT; 

double tolerance = 0.02; 

for(StampImageMap::iterator it=rgb_images.begin(); it != rgb_images.end(); it++) { 
     bool found = false; 
     StampImageMap::iterator jt=depth_images.begin(); 
     while(found == false && jt!=depth_images.end()) { 
      if(fabs(it->first - jt->first) < tolerance) { 
       found = true; 
       vstrImageFilenamesRGB.push_back(it->second); 
       vstrImageFilenamesD.push_back(jt->second); 
       vTimestampsRGB.push_back(it->first); 
       vTimestampsDPT.push_back(jt->first); 
      } 
      jt++; 
     } 
    } 

このタスクを実行するより効率的な方法があるのでしょうか？

Answer 1

コードは現在書かれているように、複雑さがΘ（N M）である、N、メートルは、配列の大きさです。これを改善するには、少なくとも2つの方法があります（2番目は効率的ですが、コード化が難しい）。外側のループの本体で

• 、while(found == false && jt!=depth_images.end())を介して第2のマップのすべての要素の上にないループを行います。代わりに、it->first - toleranceとit->first + toleranceをそれぞれ検索するには、std::map::lower_boundとstd::map::upper_boundを使用してください。この2つの呼び出しの結果の間だけをループします。

  for(StampImageMap::iterator it=rgb_images.begin(); it != rgb_images.end(); it++) { 
      StampImageMap::const_iterator lower = depth_images.lower_bound(it->first - tolerance); 
      StampImageMap::const_iterator upper = depth_images.lower_bound(it->first + tolerance); 
  
      // Now just search between lower and upper. 
  } 
  

  これはPこの範囲の大きさであるΘ（ログ（M））+ Pに各反復を減少させる。

  したがって、コードは次のようになります。

• マップのキーがソートされているので、standard technique of finding the intersection of two sorted arraysをこのケースに変更することができます。これにより、実行時間がΘ（m + n）に減少します。正確な要素の交差点を見つけようとしているのではなく、「十分に近い」要素の交差点を見つけようとしているので、この変更はややこしいことに注意してください。

  it = rgb_image.begin(); 
  jt = depth_image.begin(); 
  
  while(it != rgb_image.end() && jt != depth_image.end()) { 
      if(fabs(it->first - jt->first) < tolerance) { 
       // Match found! 
       ++it; 
       ++jt; 
       continue; 
      } 
  
      if(it.first > jt.first + tolerance) { 
       ++jt; 
       continue; 
      } 
  
      ++it; 
  }