[short code] c++ for vs map vs unordered_map 중 누가 빠를까?

안녕하세요.

신랑 각시의 신랑 입니다.

저장된 데이터 중에서, 특정 값을 검색하는 데에는 여러 방법이 있을 수 있습니다.

그 중, for loop 으로 나올때까지 비교해서 찾거나, 혹은 STL 에서 제공하는 std::map 으로 find() 하는 것이 대표적인 방법일 것 입니다.

일하면서 문득 궁금했습니다.

데이터가 얼마나 많아야 std::map 이 for loop 보다 빠를까요?

산술적으로 평가할 수는 없습니다.

가독성을 생각한다면 for loop 보다는 STL 을 사용하는 편이 좋으니까요.

하지만, 성능이 신경쓰이는 프로그램을 만들 때에도 너무 고민없이 STL 을 사용하는 것은 아닐까 싶어서 테스트 해 봤습니다.

결과)

 약, 100개 이하의 데이터에서는 for loop 이 빠른 것 같습니다.

  주로 6번째 ( 110 건 ) 과 7번째 ( 130 건 ) 에서 for loop 보다 std::map 이 빠릅니다.

해석)

•  숫자는 제 환경에서의 결과일 뿐, 데이터 증가 추이나 소요 시간의 역전 포인트가 중요 합니다.
• 10건부터 시작하여 매 회마다 + 20 건씩 증가시키며 테스트 했습니다.
• 시간 단위는 nano 단위 입니다. ( 정확한 측정은 아닐 것 입니다. )
• for loop 는 데이터 입력 후, 가장 마지막에 원하는 데이터가 있는 것으로 가정 했습니다. 
• 데이터는 4 Byte 의 string 형태값을 찾는 것으로 했습니다.

테스트 환경)

  OS : RHEL 7.1 ( 3.10.0-229.el7.x86_64 )

  CPU :  8 core ( 2792.998 MHz, Cache size : 4096 KB

  MEM : 8 GB

결과 그래프) 

•   1차 결과

• 2차 결과

• 3차 결과

 테스트 코드)

#include <iostream>
#include <cstring>
#include <string>

#include <map>
#include <unordered_map	>
#include <chrono>

char buf[128];

void func1(int _cnt) {

    bool bFind = false;

    std::cout << "Loading.. start" << std::endl;
    auto a = std::chrono::steady_clock::now();

    std::string * arr = new std::string [_cnt];

    for(int nLoop=0; nLoop < _cnt; nLoop++) {
        sprintf(buf, "%04d", nLoop);
        arr[nLoop] = buf;
    }

    auto b = std::chrono::steady_clock::now();

    for(int nLoop=0; nLoop < _cnt; nLoop++) {
        if(!arr[nLoop].compare(buf)) {
            bFind = true;
            break;
        }
    }

    auto c = std::chrono::steady_clock::now();
    std::cout << "Find.. : " << bFind << std::endl;


    auto loading =
        std::chrono::duration_cast(b - a).count();
    auto calc =
        std::chrono::duration_cast(c - b).count();

    std::cout << "loading :" << loading << " calc :" << calc << std::endl;
}


void func2(int _cnt) {

    bool bFind = false;

    std::cout << "map - Loading.. start" << std::endl;
    auto a = std::chrono::steady_clock::now();

    std::map  m;
    for(int nLoop=0; nLoop < _cnt; nLoop++) {
        sprintf(buf, "%04d", nLoop);
        m.insert({buf, true});
    }
    auto b = std::chrono::steady_clock::now();

    auto iter = m.find(buf);
    if(iter != m.end())
        bFind = true;

    auto c = std::chrono::steady_clock::now();
    std::cout << "map - Find.. : " << bFind << std::endl;


    auto loading =
        std::chrono::duration_cast(b - a).count();
    auto calc =
        std::chrono::duration_cast(c - b).count();

    std::cout << "map - loading :" << loading << " calc :" << calc << std::endl;

}

void func3(int _cnt) {

    bool bFind = false;

    std::cout << "umap - Loading.. start" << std::endl;
    auto a = std::chrono::steady_clock::now();

    std::unordered_map  m;
    for(int nLoop=0; nLoop < _cnt; nLoop++) {
        sprintf(buf, "%04d", nLoop);
        m.insert({buf, true});
    }
    auto b = std::chrono::steady_clock::now();

    auto iter = m.find(buf);
    if(iter != m.end())
        bFind = true;

    auto c = std::chrono::steady_clock::now();
    std::cout << "umap - Find.. : " << bFind << std::endl;


    auto loading =
        std::chrono::duration_cast(b - a).count();
    auto calc =
        std::chrono::duration_cast(c - b).count();

    std::cout << "umap - loading :" << loading << " calc :" << calc << std::endl;

}


int main(int argc, char * argv[]) {

    if(argc != 3) {

        std::cout << "invalid argument\n";
        std::cout << "ex) for_map_str [for|map|umap] [cnt]\n";
        return 0;
    }

    if(strstr(argv[1], "for")) {

        func1(atoi(argv[2]));
        return 0;
    }

    if(strstr(argv[1], "map")) {
        func2(atoi(argv[2]));
        return 0;
    }

    if(strstr(argv[1], "umap")) {
        func3(atoi(argv[2]));
        return 0;
    }

    return 0;
}