Skip to main content

C++ of the Day #23 - boost::mpl을 사용한 log_n, power_n 구현

Question

바로 이전 글인 C++ of the Day #22 - MemPool 클래스 개선 (switch-case문 제거)을 보면 log_2와 power_2 meta-function을 다음과 같이 구현하여 사용하고 있음을 알 수 있습니다. 각 함수는 main-template과 end-condition을 위한 template specialization으로 구성되어 있습니다.
template <int N>
struct log_2
{
  BOOST_STATIC_ASSERT(N % 2 == 0);

  enum {
    value = 1 + log_2<n / 2>::value
  };
};

template <>
struct log_2<2>
{
  enum {
    value = 1
  };
};

template <std::size_t N>
struct power_2
{
  enum {
    value = 2 * power_2<n - 1>::value
  };
};

template <>
struct power_2<0>
{
  enum {
    value = 1
  };
};
  1. 이를 boost::mpl 라이브러리를 사용하여 구현하려면 어떻게 해야 할까요?
  2. 위의 코드에 비해 얻을 수 있는 장점은 무엇일까요?


Answer

먼저 power_2를 구현하기 위해 좀 더 범용적인 power_n을 mpl 라이브러리를 사용하여 구현해 보겠습니다. 먼저 np를 구하는 power_n 함수의 대략적인 구조는 다음과 같습니다.
template <class N, class P>
struct power_n : ??
{
  BOOST_STATIC_ASSERT(P::value >= 0);
};
이 power_n이 동작하기 위해서는 ?? 부분을 이용하여 N * power_n<N, P-1> 의 형식으로 P 항이 0 이 될때까지 recursive하게 호출되어야 합니다. 물론 P 가 0 이 되면 N0 은 1 이므로 1 을 리턴해야 합니다.

만약 이 부분이 run-time 함수로 작성된다면 다음과 유사한 코드가 될 것입니다.
return P <= 0 ? 1 : N * power_n(N, P - 1);
이를 그대로 mpl 버전으로 바꾸면 다음과 같습니다. 거의 똑같은 모양입니다. ;-)
: mpl::eval_if<mpl::less_equal<P, mpl::int_<0> >,
  mpl::int_<1>,
  mpl::multiplies<N, power_n<N, typename mpl::prior<p>::type> >
>::type
위의 코드에서 P - 1 을 만들기 위해 prior를 사용하였으나 다음과 같이 minus를 사용하여도 무방합니다. 하지만 prior가 decrease by 1 이라는 의미를 좀 더 잘 나타내는 것 같네요.
power_n<N, typename mpl::minus<P, mpl::int_<1> >::type>
마지막으로 power_n을 사용하여 power_2를 만드는 것은 매우 간단합니다.
template <int N>
struct power_2 : power_n<mpl::int_<2>, mpl::int_<n> >
{
};
log_n 구현은 power_n 구현과 매우 유사함으로 중간 과정은 생략하겠습니다. 1 + log_n<B, N/B> 식을 사용하여 recusive 호출을 하며 N <= B 인 경우 종료하도록 되어 있습니다. logbn을 구하는 log_n 의 구현은 다음과 같습니다. ((조건절의 equal_to<B, int_<1> > 부분은 B가 1인 경우 recursive를 종료하고 BOOST_STATIC_ASSERT가 동작하도록 하기 위해 추가되었습니다.))
template <class B, class N>
struct log_n : mpl::eval_if<mpl::or_<
  mpl::less_equal<N, B>,
  mpl::equal_to<B, mpl::int_<1> > >,
  mpl::int_<1>,
  mpl::plus<mpl::int_<1>, log_n<B, mpl::divides<N, B> > >
>::type
{
BOOST_STATIC_ASSERT(N::value % B::value == 0);
BOOST_STATIC_ASSERT(B::value > 1);
};

template <int N>
struct log_2 : log_n<mpl::int_<2>, mpl::int_<n> >
{
};
그런데 가만히 코드를 보고 있으면 mpl을 사용한 버전보다 기존의 코드가 작성하기도 쉽고 읽기도 쉬워 보입니다. mpl을 사용하여 작성한 코드에는 어떤 장점이 있을까요?

첫번째로는 하나의 template class로 기능을 구현할 수 있다는 점입니다. 기존의 구현은 end-condition을 위한 template specialization이 필요하여 구현에 두개의 클래스가 필요했습니다. 이 경우엔 기능이 간단하여 두 개였지만 경우에 따라 더 많은 클래스가 필요할 수도 있으며 이렇게 필요한 클래스가 많아질수록 코드를 읽기도 어려워집니다. 따라서 복잡한 기능의 경우에는 mpl을 사용하는 것이 좀 더 읽기 쉬운 코드를 만들어 냅니다.

두번째 장점은 바로 작성한 함수를 다른 mpl 라이브러리의 알고리즘과 같이 사용할 수 있게 된다는 점입니다. 예를 들어 power_n을 사용하여 1, 2, 3, 4등의 배열을 입력받아 13 + 23 + 33 + 43 의 값을 계산하는 함수를 mpl을 사용하여 만들어 볼까요? 여기서는 transform과 inserter를 사용합니다. ((여기서 inserter는 std::inserter보다는 std::accumulate에 가깝다고 보시면 됩니다.))
using namespace mpl::placeholders;

typedef mpl::vector_c<int, 1, 2, 3, 4> S;
typedef mpl::transform<S, power_n<_, mpl::int_<3> >,
  mpl::inserter<mpl::int_<0>, mpl::plus<_, _> >
>::type square_sum;
cout << square_sum::value << endl;
// output: 100
이제 C++의 template meta programming 기법이 조금씩 조금씩 주 개발 라인에서도 사용되기 시작하는 것 같습니다. 부지런히 연습해서 빨리 익숙해지도록 해야겠습니다.. :-)

같은 날 오후 추가

log_n으로부터 log_2를 만들기 위해 상속 받는 방법을 사용했는데 이는 C++에서 templated typedef을 지원하지 않기 때문입니다. 만약 templated typedef이 가능했다면 다음과 같은 방법으로 log_2를 만들 수 있었을 것입니다.
template <int N> typedef log_n<mpl::int_<2>, mpl::int_<n> > log_2;

cout << log_2<8>::value << endl;
하지만 현재로서는 이런 문법이 불가능하기 때문에 typedef로 할 수 있는 것은 고작 다음과 같은 정도입니다. :-|
typedef mpl::bind<mpl::quote2<log_n>, mpl::int_<2>, _1> log_2;

cout << log_2::apply >::type::value << endl;

Comments

Popular posts from this blog

1의 개수 세기 - 해답

벌써 어제 말한 내일이 되었는데 답을 주신 분이 아무도 없어서 좀 뻘쭘하네요. :-P 그리고 어제 문제에 O(1)이라고 적었는데 엄밀히 얘기하자면 O(log 10 n)이라고 적었어야 했네요. 죄송합니다. ... 문제를 잠시 생각해보면 1~n까지의 수들 중 1의 개수를 얻기 위해서는 해당 숫자 n의 각 자리의 1의 개수가 모두 몇개나 될지를 구해서 더하면 된다는 사실을 알 수 있습니다. 예를 들어 13이라는 수를 생각해 보면 1~13까지의 수에서 1의 자리에는 1이 모두 몇개나 되는지와 10의 자리에는 모두 몇개나 되는지를 구해 이 값을 더하면 됩니다. 먼저 1의 자리를 생각해 보면 1, 11의 두 개가 있으며 10의 자리의 경우, 10, 11, 12, 13의 네 개가 있습니다. 따라서 2+4=6이라는 값을 구할 수 있습니다. 이번엔 234라는 수에서 10의 자리를 예로 들어 살펴 보겠습니다. 1~234라는 수들 중 10의 자리에 1이 들어가는 수는 10, 11, ..., 19, 110, 111, ... 119, 210, 211, ..., 219들로 모두 30개가 있음을 알 수 있습니다. 이 규칙들을 보면 해당 자리수의 1의 개수를 구하는 공식을 만들 수 있습니다. 234의 10의 자리에 해당하는 1의 개수는 ((234/100)+1)*10이 됩니다. 여기서 +1은 해당 자리수의 수가 0이 아닌 경우에만 더해집니다. 예를 들어 204라면 ((204/100)+0)*10으로 30개가 아닌 20개가 됩니다. 이런 방식으로 234의 각 자리수의 1의 개수를 구하면 1의 자리에 해당하는 1의 개수는 ((234/10)+1)*1=24개가 되고 100의 자리에 해당하는 개수는 ((234/1000)+1)*100=100이 됩니다. 이들 세 수를 모두 합하면 24+30+100=154개가 됩니다. 한가지 추가로 생각해야 할 점은 제일 큰 자리의 수가 1인 경우 위의 공식이 아닌 다른 공식이 필요하다는 점입니다. 예를 들어 123에서 100의 자리에 해당하는 1의 개수는 ((123/1...

CodeHighlighter plugin test page.

This post is for testing CodeHighlighter plugin which uses GeSHi as a fontifier engine. ((Those code blocks are acquired from Google Code Search .)) ((For more supported languages, go CodeHighlighter plugin or GeSHi homepage.)) C++ (<pre lang="cpp" lineno="1">) class nsScannerBufferList { public: /** * Buffer objects are directly followed by a data segment. The start * of the data segment is determined by increment the |this| pointer * by 1 unit. */ class Buffer : public PRCList { public: Buffer() { ++index_; } PHP (<pre lang="php" lineno="4">) for ($i = 0; $i $value = ord( $utf8_string[ $i ] ); if ( $value < 128 ) { // ASCII $unicode .= chr($value); } else { if ( count( $values ) == 0 ) { $num_octets = ( $value } $values[] = $value; Lisp (<pre lang="lisp">) ;;; Assignment (define-caller-pattern setq ((:star var fo...

C++ of the Day #43 - SQLite3 C++ wrapper #1

The Definitive Guide to SQLite 를 읽다가 공부 겸 해서 C++ wrapper를 만들어 보았습니다. 최대한 C++ 냄새(?)가 나도록 만들어 보았습니다. :-) ((SQLite는 복잡한 관리가 필요없이 사용가능한, 파일이나 메모리 기반의, 라이브러리로 제공되는, 약 250kb 용량의, 대부분의 SQL92문을 지원하는, open source RDB입니다.)) 이 wrapper를 사용하기 위해서는 (당연하게도!) sqlite3 와 (당연하게도?) boost 라이브러리가 필요합니다. 사용 예들을 살펴보는 것으로 설명을 대신합니다. 이번 글에서는 다음과 같은 contacts 테이블이 test.db에 존재한다고 가정합니다. CREATE TABLE contacts ( id INTEGER PRIMARY KEY, name TEXT NOT NULL, phone TEXT NOT NULL, UNIQUE(name, phone) ); Command 먼저 test.db 파일을 사용하기 위해 다음과 같이 파일 이름을 주어 connection 객체를 생성합니다. 생성과 동시에 test.db와 연결이 이루어집니다. ((생성자외에 open() 함수를 사용할 수도 있습니다.)) sqlite3pp::connection conn("test.db"); 다음은 contacts 테이블에 정보를 추가하는 가장 간단한 방법입니다. connection 클래스에서 제공하는 execute 함수를 사용합니다. ((executef 함수를 사용하면 printf와 같은 문법을 사용하여 query문을 작성할 수 있습니다.)) conn.execute("INSERT INTO contacts (name, phone) VALUES ('user', '1234')"); 위와 동일한 작업을 parameterized query를 사용하여 할 수도 있습니다. ((step()함수가 실제 query문을 수행하는 함수입니다. ...