速く何、インライン関数呼び出しまたはハッシュマップ検索

Question

は私が（(val * 100) + secondValの昇順に）valとsecondValの値に基づいてstd::sort()でソートする必要があるクラスClassToSortを持っていると言います。並べ替えながら

class ClassToSort { 
    private: 
    int val; 
    long int secondVal; 
    int id; 

    public: 
    inline const int getVal() const { return val; } 
    inline const long int getSecondVal() const { return secondVal; } 
    inline const int getID() const { return id; } 
}; 

std::vector<ClassToSort*> objs; 

は今、私は（どちらか、それを並べ替える(val * 100) + secondValの値を事前に計算し、std::unordered_map<int, long> valMapに保管し、このマップを参照してください並べ替えながら、または関数を作成するには2つの方法がgetVal()とgetSecondVal()に呼び出すたびに持っていますこれにより、関数呼び出しの数が2倍になります）。ここでは、2つのオプションは次のとおりです。

std::sort(objs.begin(), objs.end(), 
     [&](const ClassToSort* first, const ClassToSort* second) { 
      return valMap[first->getID()] < valMap[second->getID()]; 
     }); 

と

std::sort(objs.begin(), objs.end(), 
     [](const ClassToSort* first, const ClassToSort* second) { 
      return (first->getVal() * 100 + first->getSecondVal()) < 
       (second->getVal() * 100 + second->getSecondVal()); 
     }); 

第二の選択肢は二回、各オブジェクトのgetter関数を呼び出すだけでなく、ことは明らかであるが、また、二度同じ計算を行います。直観的には、入力の数が多いと、関数呼び出しの数が多い場合よりもハッシュテーブルの参照が速くなり、再計算が必要になると思います。私の理解は正しいのですか？

Answer 1

直接関数呼び出しは、ほとんどの場合自動的にインライン展開されます。

例の複雑さは、特定の要素とのすべての比較で»ゲッター«を2回呼び出すのではなく、何回か計算を行うことではありません。

unordered_mapを使用すると、最初にハッシュテーブルを作成する必要があります。

theseベンチマークをご覧ください。

メンバーを直接使用するかゲッター機能を使用しても違いはありません。
ハッシュルックアップは、各比較の計算を行うの10倍です。
複数回ソートする必要がある場合は、計算された値（キャッシュ）を（ハッシュマップのより安価な代替として）ペアとして保存すると便利です。

値の代わりにクラスへのポインタを使用すると、パフォーマンスが変わる可能性があります（悪化した場合）が、観察された差異を変更してはなりません。