meta programming 맛보기 1

1. 메타데이터(meta data)

문제) 구글 입사 문제
양의 정수 n에 대해서 1과 n 사이에 1이 나오는 횟수를 나타내는 함수를 f(n)이라고 한다. 예를 들어 f(13)=6이다.
f(n)=n이 되는 첫 번째 양수는 1이다. 두 번째 양수를 구할 수 있는 코드를 구현하시오. (정답은 199981)

일반적인 해법)

 

class count_num

{

        int            count(int num)

        {

               int cnt = 0;

 

               while(num)

               {

                       if( num%10 == _numofcount)

                              cnt++;

                       num /= 10;

               }

               return cnt;

        }

       

public:

        count_num(int numofcount):_numofcount(numofcount)

        {

        }

 

        int            result(int startnum)

        {

               while(1)

               {

                       int     counter = 0;

                       for( int i = 0; i <= startnum; i++ )

                       {

                              counter += count(i);

                       };

                       if( counter == startnum )

                              break;

 

                       startnum++;

               };

               return startnum;

        }

private:      

        int     _numofcount;

};

int main(void)

{

        count_num _count_num(1);

 

        std::cout << _count_num.result(1) << std::endl;

return 0;

}

메타데이터로서 접근)

 

template<int start_num>

class count_num

{ 

public:

        template<int num>

        struct count

{ 

               enum{result =  (((num%10)==1)?1:0)+ count<num/10>::result;}

        };

       

        template<>

        struct count<false>

        {

               enum{ result = 0 };

        };

 

        template<int num>

        struct loop_num

        {

               enum{ result=count< num>::result+loop_num<num-1>::result };

        };

       

        template <>

        struct loop_num<false>

        {

               enum{ result = 0 };

        };

 

        enum

        {

               result = loop_num<start_num>::result == start_num ?

                                       start_num:loop_num<start_num+1 >::result

        };

};

 

 

int main(void)

{

        std::cout << count_num<1>::result << std::endl;

        std::cout << count_num<199980>::result << std::endl;

        return 0;

}
//이 코드는 일반적인 컴파일 옵션으로는 컴파일이 되지 않는다. 괜히 컴파일 해볼려고 노력하지 말것 :) 왜 안되는지는 스스로 생각해 볼것 :D

일반적인 해법과 메타데이터로서의 접근과의 근본적인 차이점은, 실행시간에서의 결과값 계산과 컴파일시간에서의 결과값 계산이다.
(어떤 방법을 쓰던간에) 두 프로그램을 실행시키면, 어떤 것이 더 빠를것인가는 생각하지 않아도 후자가 빠르다. (전자의 실행시간은 O(n!), 후자는 O(1) 이다)

때문에 보통 메타프로그래밍은 컴파일시간을 희생시켜, 실행시간에서의 성능을 얻는다.