문자열(std::string)을 키로 가지는 맵 같은 경우, 문자열 비교 자체에 걸리는 시간 때문에 검색이 느려질 수 있다. 이 경우, 키로 사용하는 문자열이 별로 중요한 내용이 아니라면 아래와 같은 클래스를 사용함으로서 성능을 약간 증가시킬 수 있다.
/// \class cStringKey
/// \brief STL 컨테이너를 위한 문자열 키
class cStringKey
{
private:
enum {
BYTE_SIZE = 32,
};
char m_Text[BYTE_SIZE]; ///< 문자열
public:
/// \brief 생성자
cStringKey() {
memset(m_Text, 0, sizeof(m_Text));
}
/// \brief 생성자
cStringKey(const char* text) {
memset(m_Text, 0, sizeof(m_Text));
memcpy_s(m_Text, sizeof(m_Text), text, std::min(sizeof(m_Text), strlen(text)));
}
/// \brief 생성자
cStringKey(const std::string& text) {
memset(m_Text, 0, sizeof(m_Text));
memcpy_s(m_Text, sizeof(m_Text), text.c_str(), std::min(sizeof(m_Text), text.size()));
}
/// \brief 복사 생성자
cStringKey(const cStringKey& rhs) {
memcpy_s(m_Text, sizeof(m_Text), rhs.m_Text, sizeof(m_Text));
}
public:
/// \brief 대입 연산자
inline const cStringKey& operator = (const cStringKey& rhs) {
if (this != &rhs)
memcpy_s(m_Text, sizeof(m_Text), rhs.m_Text, sizeof(m_Text));
return *this;
}
/// \brief 비교 연산자
///
/// 이 함수는 약간 유의해야 하는데, 속도를 위해 루프를 풀어버렸기 때문이다.
/// 클래스의 크기가 변경되면, 이 함수도 같이 변경해줘야 한다.
inline bool operator < (const cStringKey& rhs) const {
const int* buf1 = reinterpret_cast<const int*>(this);
const int* buf2 = reinterpret_cast<const int*>(&rhs);
if (*buf1 != *buf2) return *buf1 < *buf2; // 0-3
++buf1; ++buf2;
if (*buf1 != *buf2) return *buf1 < *buf2; // 4-7
++buf1; ++buf2;
if (*buf1 != *buf2) return *buf1 < *buf2; // 8-11
++buf1; ++buf2;
if (*buf1 != *buf2) return *buf1 < *buf2; // 12-15
++buf1; ++buf2;
if (*buf1 != *buf2) return *buf1 < *buf2; // 16-19
++buf1; ++buf2;
if (*buf1 != *buf2) return *buf1 < *buf2; // 20-23
++buf1; ++buf2;
if (*buf1 != *buf2) return *buf1 < *buf2; // 24-27
++buf1; ++buf2;
return *buf1 < *buf2; // 28-31
}
};
대소문자 구별없이 비교를 할 수 없다는 점이 좀 아쉽다. 어셈블리도 좀 안다면 비교 연산자를 좀 더 깔끔하게 만들 수 있을 텐데. 어쨌든 테스트해보니, 릴리즈 빌드에서 약 25~33% 정도의 성능이 향상되었다.
typedef std::map<std::string, std::string> OLD_MAP;
typedef std::map<cStringKey, std::string> NEW_MAP;
OLD_MAP oldMap;
NEW_MAP newMap;
for (int i=0; i<1000; ++i) {
std::string key = generic::to_string(rand() % 1000, 4);
std::string value = generic::to_string(rand() % 1000, 4);
oldMap.insert(OLD_MAP::value_type(key, value));
newMap.insert(NEW_MAP::value_type(key, value));
}
DWORD begin = 0, oldTime = 0, newTime = 0;
int repetition = 200000;
begin = timeGetTime();
for (int i=0; i<repetition; ++i)
oldMap.find(generic::to_string(rand() % 1000, 4));
oldTime = timeGetTime() - begin;
begin = timeGetTime();
for (int i=0; i<repetition; ++i)
newMap.find(generic::to_string(rand() % 1000, 4));
newTime = timeGetTime() - begin;
std::cout << "OLD: " << oldTime << std::endl;
std::cout << "NEW: " << newTime << std::endl;
OLD: 241
NEW: 146
이런 자잘한 최적화 해봐야 얼마나 달라지겠냐만은 기왕이면 다홍치마 아닌가.
트랙백 주소 :: http://serious-code.net/tc/trackback/11
트랙백 RSS :: http://serious-code.net/tc/rss/trackback/11
트랙백 ATOM :: http://serious-code.net/tc/atom/trackback/11
글
댓글을 달아 주세요
댓글 RSS 주소 : http://serious-code.net/tc/rss/comment/20댓글 ATOM 주소 : http://serious-code.net/tc/atom/comment/20
새해복 많이 받아요 'ㅁ'
오랜만
근데 결혼 ㅡㅡ;;
좋겠다.... 축하 축하....
예 오랜만이네요. 어찌 지내시는지 ㅎㅎ
정리해놓으신 유용한 정보들 항상 감사하게 생각하고 있습니다.
어제 또 하나의 포스팅에 있는 내용을 유용하게 사용했습니다. 다시한번 감사드립니다. (__)
즐거운 프로그래밍 되시기 바랍니다.
http://serious-code.net/moin.cgi/CppSnippets
정리해놓으신 정보 잘 보고 갑니다.
종종 오겠습니다 ^^;