Skip to main content

C++ of the Day #28 - random_number_iterator 구현

원래는 지난번 글로 Boost::Iterator 라이브러리 얘기를 마치려고 했는데 읽던 책에 random number generator에 관한 내용이 나오네요. ((The C++ Standard Library Extensions: A Tutorial and Reference, Pete Becker, Addison-Wesley Professional, 2006))

이 내용을 이용하여 random_number_iterator를 만들어 보았습니다. random number generator는 tr1에 있으나 같은 내용이 boost에도 있으므로 boost 라이브러리를 사용하였습니다.

먼저 random number generator는 여러가지 random number 생성을 해주는 engine들과 이들 engine을 결합하여 다른 엔진을 만들어 주는 compound engine, 그리고 이를 사용하는 각종 distribution 및 engine과 distribution을 결합해 주는 variate_generator등으로 구성되어 있습니다. 또한 기본 engine들에 적당한 default 값을 사용한 predefine된 타입도 제공합니다.
boost::mt19937 rng;
boost::uniform_int<> six(1,6);
boost::variate_generator<boost::mt19937&, boost::uniform_int<> > die(rng, six);

int x = die();
예를 들어 위의 코드에서 mt19937은 mersenne_twister라는 engine을 사용하여 predefined된 타입입니다. ((Boost Random Number Library 문서에서 가져왔습니다.)) 그리고 uniform_int는 어떤 random number의 sequence를 특정 범위안의 uniformly distributed random sequence로 변경해 주는 클래스이고 마지막으로 variate_generator는 engine과 distribution을 결합시키기 위해 사용되었습니다.

이렇게 해서 생성된 die 객체는 function call operator를 가지고 있어 마지막 라인과 같이 호출할 때마다 새로운 1~6의 범위안에서 uniformly distributed된 random number를 리턴합니다. 즉, 정육면체 주사위를 simulate할 수 있는 객체죠.

이 function call operator를 사용하여 특정 container의 값을 채우기 위한 방법에는 다음과 같은 것들이 있습니다.
for (int i = 0; i < vi.size(); ++i) vi[i] = die();

std::generate(vi.begin(), vi.end(), die);

std::generate_n(vi.begin(), vi.size(), die);
하지만 이번 글에서 만들어 볼 iterator 클래스를 사용하면 다음과 같이 사용이 가능합니다.
random_number_iterator<??> first(die, N);
random_number_iterator<??> last(die);
copy(first, last, vi.begin());
여기서 N은 이 iterator가 만들어 낼 random number의 갯수입니다. 그리고 ?? 부분에 대해서는 뒤에서 알아 보겠습니다.

그럼 Boost::Iterator에 대한 설명을 생략하고 바로 코드를 보겠습니다.
template <class Gen>
class random_number_iterator
  : public boost::iterator_facade<
      random_number_iterator<gen>,
      typename Gen::result_type const,
      forward_traversal_tag
    >
{
  typedef typename Gen::result_type result_type;
public:
  explicit random_number_iterator(Gen& gen, int cnt = 0)
      : gen_(gen), cnt_(cnt) {
    if (cnt != 0) val_ = gen_();
  }

private:
  friend class boost::iterator_core_access;

  void increment() { --cnt_; val_ = gen_(); }

  bool equal(random_number_iterator const& other) const
  {
    return cnt_ == other.cnt_;
  }

  result_type const& dereference() const { return val_; }

private:
  Gen& gen_;
  int cnt_;
  result_type val_;
};
cnt_ 멤버는 default로 0으로 셋팅되어 iterator의 end()를 나타내게 됩니다. 0이 아닌 값은 end()가 아니며 increment() 호출시마다 1씩 감소하여 결국 end()가 되도록 만들었습니다. 그리고 이 increment()시에 gen_()을 호출하여 random number를 val_에다 저장하도록 하였습니다.

여기서 만약 val_ 멤버 변수를 없애기 위해 dereference()마다 gen_()을 호출하였다면 아래와 같은 코드에서 i와 j는 서로 다른 값을 가지는 문제가 생기게 됩니다.
i = *iter;
j = *iter;
다음으로 주의할 점은 생성자에서 cnt_가 0이면 val_의 초기값을 셋팅하지 않는다는 것입니다. 물론 end()를 dereference하는 것은 금지되어 있어 사용자가 호출하진 않겠지만 만약 여기서 gen_()을 호출한다면 reference로 가지고 있는 gen_의 상태가 변하게 되고 역시 이 reference를 가지고 있을 다른 iterator의 상태에 영향을 주기 때문입니다.

그럼 이제 이 iterator를 사용하여 앞에서 살펴본 ?? 를 가지고 있던 코드를 다시 작성해 보겠습니다.
random_number_iterator<variate_generator<boost::mt19937&, boost::uniform_int<> > > first(die, N);
random_number_iterator<variate_generator<boost::mt19937&, boost::uniform_int<> > > last(die);
copy(first, last, vi.begin());
너무 길군요. :-| 그럼 이를 좀 간단히 해줄 helper function을 만들어 보겠습니다.
template <class Gen>
random_number_iterator<gen> make_random_number_iterator(Gen& gen, int cnt = 0)
{
return random_number_iterator<gen>(gen, cnt);
}
이제 이 function을 사용하여 다음과 같이 코드를 작성할 수 있습니다.
copy(
make_random_number_iterator(die, N),
make_random_number_iterator(die),
vi.begin());
이제 실제 타입이 아무리 길어도 위의 함수를 사용하여 비교적 간단히 algorithm들을 사용할 수 있게 되었습니다.

참고로 C++에 auto 키워드가 추가되고 나면 다음과 같이 작성할 수 있게 됩니다.
auto first = make_random_number_iterator(die, N),
auto last = make_random_number_iterator(die),
copy(first, last, vi.begin());
이번 글에서는 Boost::Iterator 시리즈의 복습 삼아 random_number_iterator를 작성해 보았습니다. 해보면서 느끼는 건데 iterator 만들기 정말 쉬워졌군요. :-)

Comments

Popular posts from this blog

1의 개수 세기

저도 간단한 알고리즘 문제 하나... :-)

어떤 수 n이 주어졌을때 1~n까지의 수를 쭈욱 썼을때 나오는 1의 개수를 구하는 문제입니다.

예를 들어 13이라는 수가 주어지면 1~13까지의 수 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13에서 1은 1, 10, 11, 12, 13에 나오며 그 개수는 6이 됩니다. 즉, f(13)=6.

원래 문제는 f(n)=n이 되는 1이 아닌 가장 작은 수를 구하는 문제인데 이 문제의 경우에는 처음부터 쭈욱 세어나가면 되기 때문에 간단히 다음과 같이 구현을 하면 됩니다. ((한가지 주의할 점은 이전에 찾았던 n-1값을 사용하지 않고 다시 처음부터 n까지 값을 계산하면 시간이 너무 많이 걸린다는 점입니다. 위의 코드에서는 static 변수를 사용하여 이전 값에 계속 더해나가는 방법을 사용했습니다.))


#include

int count1(int n)
{
static int cnt = 1; // not 0 because n starts from 2. see main.

while (n > 0) {
if ((n % 10) == 1) ++cnt;
n /= 10;
}

return cnt;
}

int main()
{
using namespace std;

int n = 2;

while (count1(n) != n) ++n;
cout << n << endl;
}


좀 재미가 없죠? 그래서 이번 문제는 어떤 수 n에 대해서 f(n)을 O(1)시간에 구하는 알고리즘을 만드는 것입니다. 관심있으신 분들은 한번 풀어보세요. 제가 만든 코드는 내일 올려보겠습니다.

C++ of the Day #9 - Boost.Python 사용하기 #1

Python은 가장 인기있는 interpret 언어중의 하나입니다. Python의 장점 중 하나는 C/C++ 모듈과 쉽게 연동할 수 있다는 점입니다. 물론 손으로 일일히 wrapper를 만드는 것은 손이 많이 가고 에러를 만들수 있는 작업이나 SWIG등과 같은 도구를 사용하면 쉽게 python 모듈을 만들 수 있습니다.

Boost.Python은 이런 SWIG와 같이 python 모듈을 쉽게 만들 수 있도록 도와주는 라이브러리로 순수 C++만을 사용한다는 점이 SWIG와 다른 점입니다. 그리고 개인적으로는 Boost 라이브러리에 포함되어 있는 것들이 왠지 좀 더 믿음직스러워서... :-)

이번 글에서는 Boost.Python 문서에 나와 있는 예제를 가지고 간단하게 python 모듈을 만드는 방법에 대해서 알아보겠습니다.

Requirements리눅스
이 글에서는 리눅스 환경에서의 사용 방법을 설명한다.Boost.Python 라이브러리 (1.33.1)
Boost 라이브러리를 다운로드받아 아래와 유사한 명령으로 라이브러리를 빌드한다.
bjam -sTOOLS=gcc -with-python install

bjam의 --prefix 옵션으로 라이브러리가 설치될 위치를 변경할 수 있다.Python 라이브러리 (2.4.3)
Python을 다운로드 받아 빌드하여 설치한다.
위의 경우와 유사하게 configure의 --prefix 옵션으로 설치될 위치를 변경할 수 있다.

Write C++ Code다음과 같이 코드를 작성한다.

// greet.cpp #include <stdexcept> char const* greet(unsigned x) { static char const* const msgs[] = { "hello", "Boost.Python", "world!" }; if (x > 2) throw std::range_error("greet: index out of range"…

Hello Wordpress, again.

한 두주일 정도 Textpattern을 사용해봤는데 다시 Wordpress로 돌아오기로 결정했습니다. 무엇보다 스킨 변경이 너무 복잡하고 사용자층이 Wordpress에 비해 너무 앏네요. 원하는 plugin도 찾기 어렵고... :-|

그동안 Textpattern에 썼던 글들은 모두 Wordpress로 옮겼습니다. 2개 있던 댓글도 옮겼는데 그중의 하난 제가 쓴... ;-)

애초에 wp-dokuwiki plugin이 무거워서 옮겼던 것이라 이 plugin은 설치를 안할 예정인데 몇가지 아쉬운 점이 있네요.

첫째는 code highlighting 기능인데 이 기능은 예전에 만들어 놨던 것을 조금 수정해서 쓰려고 준비중입니다. 두번째는 Footnote 기능인데 찾아보니 Footnotes 0.9 Plugin for WordPress 2.0.x라는게 있네요.

이정도면 비록 wiki syntax에 비할바는 아니지만 쓸만할 것 같습니다. :-)