CPU 및 메모리에 관한 C++의 무거운지도 삽입을 최적화하는 방법

Question

요소가 없다는 조건에 따라지도에 요소를 추가해야하는지도를 반복합니다 (다른 조건 일 수 있음).

내 큰 문제는 추가해야 할 큰 규모의 업데이트로 인해 응용 프로그램이 전체 CPU와 모든 메모리를 차지한다는 것입니다.

주 수업 : 주에서

class State { 

    int id; 

    int timeStamp; 

    int state; 

} 

방법 :

void State::updateStateIfTimeStampIsHigher(const State& state) { 
    if (this->id == state.getId() && state.getTimeStamp() > this->getTimeStamp()) { 
     this->timeStamp = state.getTimeStamp(); 
     this->state = state.getState(); 
    } 
} 

루프 코드 :가 data.insert처럼 보이는

std::map<int, State> data; 

const std::map<int, State>& update; 

for (auto const& updatePos : update) { 
    if (updatePos.first != this->toNodeId) { 
     std::map<int, State>::iterator message = data.find(updatePos.first); 
     if (message != data.end() && message->first) { 
      message->second.updateStateIfTimeStampIsHigher(updatePos.second); 
     } else { 
      data.insert(std::make_pair(updatePos.first, updatePos.second)); 
     } 
    } 
} 

보고 KCacheGrind 데이터() 라인 대부분의 시간/메모리를 사용합니다. 나는 KCacheGrind를 처음 사용하지만,이 라인은 비용의 약 72 % 인 것으로 보입니다.

개선 방법에 대한 의견이 있으십니까?

Answer 1

질문에 대한 의견을 조사해 주시면 만족스러운 답변을 찾을 수 있습니다. 그것은 지도에서 unordered_map으로 조금 변경하는 데 도움이되었지만 여전히 만족스럽지 않은 결과를 얻었습니다.

나는 항목을 지우는 데 따른 단점에도 불구하고 더 나은 리소스 사용을 제공하는 Google의 sparsehash을 사용했다.

코드 솔루션은 다음과 같습니다.우선 필요한 라이브러리를 포함 정의 보이는, 그리고 나의 새로운 데이터를

#include <sparsehash/sparse_hash_map> 

을 같은 : 나는 내가 sparsemap 후이 작업을 수행해야한다 "삭제"를 사용해야하기 때문에

struct eqint { 
    bool operator()(int i1, int i2) const { 
     return i1 == i2; 
    } 
}; 

google::sparse_hash_map<int, State, std::tr1::hash<int>, eqint> data; 

건설 :

data.clear_deleted_key(); 
data.set_deleted_key(-1); 

마지막으로 내 루프 코드가 약간 변경 :

for (auto const& updatePos : update) { 
    if (updatePos.first != this->toNodeId) { 
     google::sparse_hash_map<int, State, std::tr1::hash<int>, eqint>::iterator msgIt = data.find(updatePos.first); 
     if (msgIt != data.end() && msgIt->first) { 
      msgIt->second.updateStateIfTimeStampIsHigher(updatePos.second); 
     } else { 
      data[updatePos.first] = updatePos.second; 
     } 
    } 
} 

시간 특정 매개 변수에서 실행 전체 응용 프로그램에 대한 변경을했다하기 전에 :

real 0m28,592s 
user 0m27,912s 
sys  0m0,676s 

그리고 시간 같은에서 전체 응용 프로그램 실행에 대한 변경을 후 특정 매개 변수는 다음과 같습니다.

real 0m37,464s 
user 0m37,032s 
sys  0m0,428s 

다른 사례와 함께 실행합니다. 그리고 그 결과는 (질적 관점에서) 비슷한 경우. 시스템 시간 및 자원 사용 (CPU 및 메모리)이 감소하고 사용자 시간이 증가합니다.

전반적으로 나는 실행 시간보다 리소스 사용에 더 많은 관심이 있었기 때문에 전반적으로 만족합니다 (응용 프로그램이 시뮬레이터이고 실제로로드가 심한 상황에서 끝내고 결과를 얻을 수 없었습니다).

Answer 2

귀하의 질문은 매우 일반적이지만, 나는 그것을 실행 속도가 물건 tho를 참조하십시오

1. 사용이 삽입/설치 장소를 암시했다. 새로운 요소를 추가하면 iterator가 반환됩니다. 두 맵이 동일한 방식으로 정렬되었다고 가정하면 마지막으로 삽입 된 위치를 알 수 있으므로 조회가 더 빨라야합니다 (여기서는 일부 벤치마킹을 사용할 수 있음).

샘플 코드 여기에 빠른 삽입

사용 emplace_hint : 당신은 당신이 (Is there any advantage of using map over unordered_map in case of trivial keys?를) unordered_map도 사용할 수있는 메모리를 통해 CPU를 거래하기를 원하지만 경우

std::map<int, long> data; 

const std::map<int, long> update; 
auto recent = data.begin(); 

for (auto const& updatePos : update) { 
    if (updateElemNotFound) { 
     recent = data.emplace_hint(recent, updatePos); 
    } 
} 

또한, 첫 번째 점은 더 이상 문제가되지 것입니다 .