지도 삽입 속도를 높이는 방법은 무엇입니까?

Question

마치 마침내 약간의지도 삽입 속도 (삽입하기 전에 정렬)를 개선 한 것처럼 보입니다. 이 결과에 대해 어떻게 생각하십니까? 더 이상 최적화가 있습니까?

#include <map> 
#include <iostream> 
#include <algorithm> 

int main (int argc, char* argv []) { 
    //a map<size_t, size_t> random initilisation 
    std::map<size_t, size_t> m0, m1; 
    { 
    std::vector<std::pair<size_t, size_t> > t (10000, std::pair<size_t, size_t> ((size_t) -1, (size_t) -1)); 
    std::vector<std::pair<size_t, size_t> >::iterator i (t.begin()); 
    for (; i != t.end(); ++i) { 
     i->first = rand() % 1000000; 
     i->second = rand() %1; 
    } 
    m0.insert (t.begin(), t.end()); 
    m1 = m0; 
    } 
    //vins : 
    std::vector<std::pair<size_t, size_t> > vins (10000, std::pair<size_t, size_t> (0, 0)); 
    { 
    std::vector<std::pair<size_t, size_t> >::iterator i (vins.begin()); 
    for (; i != vins.end(); ++i) { 
     i->first = rand() % 1000000; 
     i->second = rand() %1; 
    } 
    } 
    //normal insertion 
    clock_t t0 (clock()), t1 (t0); 
    { 
    m0.insert (vins.begin(), vins.end()); 
    } 
    t1 = clock(); 
    std::cout << "normal insertion took " << (size_t) (t1 - t0) << " ticks" << std::endl; 
    //sort + hint insertion 
    t0 = t1; 
    { 
    std::sort (vins.begin(), vins.end(), [] (std::pair<size_t, size_t>& p0, std::pair<size_t, size_t>& p1)->bool { 
     return (p0.first < p1.first ? true:false); 
    }); 
    std::map<size_t, size_t>::iterator ihint (m1.begin()); 
    //std::vector<std::pair<size_t, size_t> >::iterator i (vins.begin()); 
    //imroved and more C++11 solution 
    std::for_each (vins.begin(), vins.end(), [&ihint, &m1] (std::pair<size_t, size_t>& p) { 
     ihint = m1.insert (ihint, p); 
    }); 
    } 
    t1 = clock(); 
    std::cout << "insertion after sorting took " << (size_t) (t1 - t0) << " ticks" << std::endl; 
    if (m0 != m1) std::cout << "but insertion is nok" << std::endl; 
    else std::cout << "and insertion is ok" << std::endl; 
} 

레노버의 결과는 센터 생각 :

정렬 한 후 삽입 (1706)했다

틱

틱하고 그렇지 않으면 삽입

Answer 1

괜찮 2355했다 삽입 항목을 주문해야합니다. std::unordered_map을 사용하는 것이 일반적으로 std::map보다 좋습니다. 바 대신 해시 테이블을 사용합니다. 대부분의 구현에서 lanced tree는 작업이 O(log n)이 아니라 평균 O(1)임을 의미합니다. 또한 기본 데이터 구조 (배열)가 일반적으로 트리보다 캐시 친화적이기 때문에 캐시 위치에서 성능이 향상 될 수 있습니다. -O3 (또는 이와 유사한 최적화 수준)을 사용

는 당신의 코드의 성능을 향상하지만, /지도의 삽입의 성능에 영향을 (아직 컴파일 된 것 같은) 작업을 찾을 가능성이 있습니다. -Ofast을 사용하면 컴파일러가 더 이상 엄격하게 표준을 준수 할 필요가 없다는 것을 명심하십시오. 성능이 중요하고 코드가 예상대로 작동하는지 확인하는 데 사용하지만 대개는 -O3입니다. 충분히. 내 컴퓨터에

---

(데비안, g ++ 6.3.0), 몇 가지 실행을 사용하고 거친 평균 복용 : 당신이 주문 속성을 필요로하지 않는 경우

Configuration    Normal Hint Insertion Hint Insertion 
------------------------- ----------------------- ---------------- 
    std::map,   -O0     9750    9200 
    std::map,   -O3     8000    4250 
    std::unordered_map, -O0     7000    9700 
    std::unordered_map, -O3     4200    5000