0

次のループでブランチを削除することは可能ですか。すべてのイテレータはコンテナ型からのものですstd::map<type_name, T>

  record_iterator beginIter = lastLookup_;                                                                                                                                                                                                                                                                                                                             
  record_iterator endIter = lastLookup_;                                                                                                                                                                                                                                                                                                                               
  ++endIter;                                                                                                                                                                                                                                                                                                                                                           
  for(;endIter != end(); ++beginIter, ++endIter){                                                                                                                                                                                                                                                                                                                      
    time_type now = beginIter->first;                                                                                                                                                                                                                                                                                                                                  
    if(ts == now){                                                                                                                                                                                                                                                                                                                                                     
      lastLookup_ = beginIter;                                                                                                                                                                                                                                                                                                                                         
      return beginIter;                                                                                                                                                                                                                                                                                                                                                
    }else if(ts > now && ts <= endIter->first){                                                                                                                                                                                                                                                                                                                        
      lastLookup_ = beginIter;                                                                                                                                                                                                                                                                                                                                         
      return endIter;
    }
  }

このアルゴリズムが解決しようとしている問題は、最後に検索された場所と同じか (それほど遠くない) 前方にあると想定される前方参照を最適化することです。理想的には、最後に検索した場所の反復子を保持し、直線的に前進します。しかし、これは、

  record_iterator it= sliceMap_.find(ts);                                                                                                                                                                                                                                                                                                                              
  if(it !=end()){                                                                                                                                                                                                                                                                                                                                                      
    return it;                                                                                                                                                                                                                                                                                                                                                         
  }else{                                                                                                                                                                                                                                                                                                                                                               
    return sliceMap_.upper_bound(ts);                                                                                                                                                                                                                                                                                                                                  
  }

問題はブランチだと思うので、このコードでブランチを削除して、速度の違いをプロファイルできますか?

4

2 に答える 2

5

最初のアプローチには3つの大きな問題があります。

  • ループ内の比較が多すぎます。
  • でイテレータを使用するにstd::mapは、を使用する必要がありますstd::map<>::iterator::operator++()が、これは正確には高速ではありません。62行目から始まる実装を見てください：http：//gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-3.4/tree_8cc-source.html。
  • でイテレータを使用することstd::mapは線形探索です。地図での検索は対数で行う必要があります。

2番目のアプローチにも問題があります。2回検索しています。

使ってみませんか

return sliceMap_.lower_bound(ts);

これは、1回の対数探索で必要なことを正確に実行するはずです。

于 2012-10-29T18:21:05.407 に答える
2

一部の人々が言っ​​たように、最初の方法は、順序付けられたコンテナで線形検索を行っているため、あまり意味がありません。場所はlastLookupの近くにあるはずだと思います

2番目の方法については、単純な最適化で2番目のルックアップを排除できると思います。record_iteratorで1つ実行していますit=liceMap_.find（ts）; もう1つはsliceMap_.upper_bound（ts）;を返します。

編集：
この方法で試してみてください：

record_iterator it = sliceMap_.lower_bound(ts);                                                                                                                                                                                                                                                                                                                              
return it;

そこで行っているのは、lower_bound（）を使用して、キーがts未満と比較されない最初の要素を見つけることです（upper_bound（）が実行しない等しい要素を含みます）。

于 2012-10-29T18:21:10.113 に答える