'STL'에 해당되는 글 2건

  1. 2009/09/03 김성민 문자열을 키로 쓰는 std::set, std::map 성능 향상시키기
  2. 2009/09/03 김성민 STL 컨테이너에서 아이템 삭제하기

문자열을 키로 쓰는 std::set, std::map 성능 향상시키기

개발 2009/09/03 09:07 김성민
문자열(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

이런 자잘한 최적화 해봐야 얼마나 달라지겠냐만은 기왕이면 다홍치마 아닌가.
2009/09/03 09:07 2009/09/03 09:07
TAG , ,
받은 트랙백이 없고, 댓글이 없습니다.

댓글+트랙백 RSS :: http://serious-code.net/tc/rss/response/11

댓글+트랙백 ATOM :: http://serious-code.net/tc/atom/response/11

STL 컨테이너에서 아이템 삭제하기

개발 2009/09/03 08:54 김성민
컨테이너를 횡단하면서 아이템 삭제하기에 관한 글은 Effective C++에 잘 나와있다.

순차형(sequential) 컬렉션

typedef std::list<OBJECT*> OBJECTS;
OBJECTS objects;
...
for (OBJECTS::iterator itr(objects.begin()); itr != object.end(); )
{
  OBJECT* object = *itr;

  if (should_delete(object))
  {
     itr = objects.erase(itr);
     delete object;
  }
  else itr++;
}

연관형(associative) 컬렉션

typedef std::map<int, OBJECT*> OBJECTS;
OBJECTS objects;
...
for (OBJECTS::iterator itr(objects.begin()); itr != object.end(); )
{
  OBJECT* object = itr->second;

  if (should_delete(object))
  {
     objects.erase(itr++);
     delete object;
  }
  else itr++;
}

문제는 둘이 비슷비슷해서 자꾸 착각한다는 것. 컨테이너가 어떤 것이냐와는 상관없이 아이템을 삭제하고 싶었다. 더불어 컨테이너에 들어있는 것이 일반(?) 변수인지 포인터 변수인지도 신경쓰고 싶지 않았다. 뜻이 있는 곳에 길이 있는 법.

struct YES {};
struct NO {};

template <typename T>
struct is_ptr
{
  enum { result = false };
  typedef NO Result;
};

template <typename T>
struct is_ptr<T*>
{
  enum { result = true };
  typedef YES Result;
};

template <typename T>
struct is_ptr<T* const>
{
  enum { result = true };
  typedef YES Result;
};

template <typename T>
struct is_ptr<T* volatile>
{
  enum { result = true };
  typedef YES Result;
};

template <typename T>
struct is_ptr<T* const volatile>
{
  enum { result = true };
  typedef YES Result;
};

template <typename T>
class is_pair
{
private:
  template <typename U>
  struct is_pair_imp
  {
     enum { value = false };
     typedef NO Result;
  };

  template <typename U, typename V>
  struct is_pair_imp < std::pair<U, V> >
  {
    enum { value = true };
     typedef YES Result;
  };

public:
  enum { value = is_pair_imp<T>::value };
  typedef typename is_pair_imp<T>::Result Result;
};

template <typename IS_POINTER>
struct do_delete {};

template <>
struct do_delete<YES>
{
  template <typename U>
  void operator()(U param) { delete param; }
};

template <>
struct do_delete<NO>
{
  template <typename U>
  void operator()(U param) {}
};
      
template <typename IS_ASSOCIATION>
struct delete_if_imp {};

template <>
struct delete_if_imp<YES>
{
  template <typename C, typename P>
  void operator()(C& con, P comp)
  {
     do_delete< is_ptr<C::value_type::second_type>::Result > doDelete;
     for (C::iterator itr(con.begin()); itr != con.end();)
     {
         if (comp(itr->second))
         {
             doDelete(itr->second);
             con.erase(itr++);
         }
         else ++itr;
     }
  }
};

template <>
struct delete_if_imp<NO>
{
  template <typename C, typename P>
  void operator()(C& con, P comp)
  {
     do_delete< is_ptr<C::value_type>::Result > doDelete;
     for (C::iterator itr(con.begin()); itr != con.end();)
     {
         if (comp(*itr))
         {
             doDelete(*itr);
             itr = con.erase(itr);
         }
         else ++itr;
     }
  }
};

template <typename C, typename P>
inline void delete_if(C& con, P comp)
{
  delete_if_imp< is_pair<C::value_type>::Result > imp;
  imp(con, comp);
}

하는 일에 비해 코드가 꽤 길어졌다. 뭐 어쨌든 최종 결과물인 delete_if 함수를 이용하면 컨테이너의 종류와 상관없이 아이템을 삭제할 수 있다.

class test
{
private:
  int myValue;

public:
  test(int value = 0) : myValue(value) {}
  ~test()
  {
  //std::cout << myValue << " dying" << std::endl;
  }
};

struct COMPARE_TEST
{
  bool operator()(test* t) { return t->myValue < 2; }
  bool operator()(test& t) { return t.myValue < 2; }
};

int main()
{
  std::map<int, test*> myMap;
  std::map<int, test> myMap2;
  std::vector<test*> myVector;

  myMap[0] = new test(0);
  myMap[1] = new test(1);
  myMap[2] = new test(2);
  myMap[3] = new test(3);

  myMap2[0] = test(0);
  myMap2[1] = test(1);
  myMap2[2] = test(2);
  myMap2[3] = test(3);

  myVector.push_back(new test(0));
  myVector.push_back(new test(1));
  myVector.push_back(new test(2));
  myVector.push_back(new test(3));

  std::cout << ">> MAP BEFORE: " << myMap.size() << std::endl;
  delete_if(myMap, COMPARE_TEST());
  std::cout << ">> MAP AFTER: " << myMap.size() << std::endl;

  std::cout << ">> MAP2 BEFORE: " << myMap2.size() << std::endl;
  delete_if(myMap2, COMPARE_TEST());
  std::cout << ">> MAP2 AFTER: " << myMap2.size() << std::endl;

  std::cout << ">> VECTOR BEFORE: " << myVector.size() << std::endl;
  delete_if(myVector, COMPARE_TEST());
  std::cout << ">> VECTOR AFTER: " << myVector.size() << std::endl;

  return 0;
}

 

2009/09/03 08:54 2009/09/03 08:54
TAG , ,
받은 트랙백이 없고, 댓글이 없습니다.

댓글+트랙백 RSS :: http://serious-code.net/tc/rss/response/5

댓글+트랙백 ATOM :: http://serious-code.net/tc/atom/response/5

◀ 이전페이지 1 다음페이지 ▶