두 표준 사이의 일치를 찾는 C++ 효율적인 방법

Question

데이터 세트의 각 이미지에 대해 타임 스탬프와 파일 이름이 저장되는 RGB-D 카메라와 텍스트 파일로 데이터 세트를 얻습니다. 내가하는 일은이 파일을 파싱하고 두 개의 std :: map을 채우는 것이다. 하나는 rgb 이미지 용이고 다른 하나는 깊이 이미지 용이다. 이제는 타임 스탬프가 교차하지 않기 때문에 타임 스탬프를 기반으로 일치하는 이미지를 찾는 루틴을 작성해야합니다. 이것은 내가 지금까지 쓴 것입니다 :

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 개의 m)이다. 이를 개선하는 방법은 두 가지가 있습니다 (두 번째 방법이 더 효율적이지만 코드 작성이 더 어렵습니다). 외부 루프의 본문

• , while(found == false && jt!=depth_images.end()) 통해 제 2 맵 내의 모든 요소를 ​​수행하지 루프. 대신 it->first - tolerance 및 it->first + tolerance을 검색하려면 std::map::lower_bound 및 std::map::upper_bound을 사용하십시오. 이 두 호출의 결과 사이에서만 반복하십시오.

  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; 
  }