빠른 게 뭔데, 인라인 함수 호출 또는 해시 맵 조회

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에 저장하고 정렬하는 동안이지도를 참조하거나 (정렬하는 동안 함수가 getVal() 및 getSecondVal() 매번 호출을하는 방법은 두 가지가 이로 인해 함수 호출 수가 두 배가됩니다). 여기에 두 가지 옵션은 다음과 같습니다

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

두 번째 옵션은 두 번 각 개체에 대한 게터 함수를 호출 할뿐만 아니라 분명하다, 또한이 두 번 같은 계산을한다. 직관적으로, 나는 많은 수의 입력에 대해, 재 계산과 함께 함수 호출 수가 더 많은 경우보다 해시 테이블 조회가 빠르다고 생각할 것이다. 내 이해가 맞습니까?

Answer 1

직접 함수 호출은 대부분 자동으로 인라인됩니다.

예제의 복잡성은 특정 요소와의 모든 비교에 대해»getter를 두 번 호출했지만 계산을 여러 번 수행하는 것이 아닙니다.

unordered_map을 사용하면 해시 테이블을 먼저 만들어야합니다.

these 벤치 마크를 살펴보십시오.

게터 기능과 직접적인 관계가없는 멤버를 사용하면 아무런 효과가 없습니다.
해시 조회는 각 비교에 대해 계산을 수행하는 것보다 10 배 느립니다.
여러 번 정렬해야하는 경우 계산 된 값 (캐시)을 쌍으로 저장하여 유지하는 것이 유용 할 수 있습니다 (해시 맵에 대한 더 저렴한 대안으로).

값 대신 클래스에 대한 포인터를 사용하면 성능이 저하 될 수 있지만 관찰 된 차이는 변경되지 않습니다.