Creative Commons License

map<string,*>::find(const string&) const 피하는 방법 없을까? IT



STL에 map과 string을 엮어서 자주 사용하는 편인데, 일반적인 규모에서는 흡족할만한 성능을 보여주기에 별 불만이 없다. 하지만 대용량처리(초당 1,000,000건 정도?)를 하다보면 실망스럽기 서울역에 그지 없다. 다음 소스를 보면 암묵적 형변환에 의해 얼마나 그지 같이 느려지는지 알 수 있다.
testFunc(size_t cnt)
{
    map<string,void*> tmpcont;
    const char* key_1("Hello, world! What are you doing?");
    const string key_2(key_1);

    // 100만개 아이템을 우겨넣는다. (생략)

    // C-style string key
    t1 = getTimestamp();
    for (size_t i(0); i<cnt; i++)
    {
       tmpcont.find(key_1);
    }
    t2 = getTimestamp();
    cerr << t2-t1 << endl;

    // STL string key
    t1 = getTimestamp();
    for (size_t i(0); i<cnt; i++)
    {
       tmpcont.find(key_2);
    }
    t2 = getTimestamp();
    cerr << t2-t1 << endl;
}
결과는 약 5배 차이가 난다. -_-; 5배 차이라고 해봤자, 1,000,000건에 0.1초 차이이지만, 대용량 처리에서 저런게 누적하기 시작하면 대략 난감하다. map에서 반드시 key_type과 동일한 타입을 인자로 갖는 비교 함수를 쓰지 않는다면 어떻게 해보겠지만, 정말이지 초난감할 뿐이다. 어떻게 하지...?

덧글

  • chadr 2007/09/22 22:59 #

    안그래도 스트링을 키값으로 가질 경우 성능저하 때문에 고민한적이 있었는데..
    대략 키값에 구조체로 해서 정수형 해시 키값과 실제 스트링 키값을 가지도록 하고 < 연산자에서 아주 가벼운 해시 펑션을 이용해서
    스트링에 대한 해시값을 계산하도록 하면 어떨지..

    라고 생각만 해보고 실제 성능 테스트는 안해서 어쩔지 모르겠네요 _-_
  • 샘이 2007/09/27 09:39 #

    chadr// 해시를 하는게 더 느리지 않을까? 어짜피 비교 당하는 쪽이나 비교 하는 쪽 스트링을 모두 해싱해야는데, 비교랑 비슷하게 O(n)이 걸릴꺼 같은데? 다만 비교만 하는 것과 다르게 기타 해싱연산도 들어가니 더 느릴 것 같아.
  • chadr 2007/09/27 11:27 # 삭제

    그래서 아주 가벼운 해시 펑션을 쓰자고 한거긴 해요..
    해싱하는데 걸리는 시간이 키값 비교하는데 걸리는 시간보다 더 크면 안될테니까요..
    실제 테스트는 해봐야지 알겠지만..

    역시 귀찮은게 문제 ㄱ-
  • 샘이 2007/09/27 14:54 #

    chadr// 문자열 길이가 다르고 중간에 다른 값이 있는 문자열 비교 시, 보통 문자열 비교 함수는 다른 부분에서 return하기 때문에 문자열을 끝까지 검사하지 않지. 그러나 hash는 일단 주어진 문자열을 충실하게 끝까지 scan하기 때문에 -_-
※ 이 포스트는 더 이상 덧글을 남길 수 없습니다.

Google Adsense

Google Adsense

Google Analytics



C로그팬박스