블로그 이미지
Every unexpected event is a path to learning for you.

카테고리

분류 전체보기 (2731)
Unity3D (814)
Programming (474)
Server (33)
Unreal (4)
Gamebryo (56)
Tip & Tech (228)
협업 (57)
3DS Max (3)
Game (12)
Utility (136)
Etc (96)
Link (32)
Portfolio (19)
Subject (90)
iOS,OSX (51)
Android (14)
Linux (5)
잉여 프로젝트 (2)
게임이야기 (3)
Memories (20)
Interest (38)
Thinking (38)
한글 (30)
PaperCraft (5)
Animation (408)
Wallpaper (2)
재테크 (18)
Exercise (3)
나만의 맛집 (3)
냥이 (10)
육아 (16)
Total
Today
Yesterday
03-28 00:02

'문자열키'에 해당되는 글 1건

  1. 2011.02.07 2.1 문자열을 키로 쓰는 map, set 성능 향상시키기
    문자열(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;


반응형
Posted by blueasa
, |