2012년 6월 12일 화요일

블로그스팟에 조금 더 예쁜 코드 넣기

블로그의 템플릿이 동적뷰로 바꾸고 나니, google-code-prettify가 작동하지 않는다. google-code-prettify가 긴 줄의 표시도 매끄럽지 못하고, 매스매티카 문법도 인식하지 못해서 불편을 겪던 차여서 다른 걸 찾아보기로 했다. 뒤져보니 Alex Gorbatchev가 만든 SyntaxHighlighter란 게 있다. 설치방법은 Way2Blogging에 잘 나와 있고 적용도 잘 된다.

몇 가지 아쉬운 점도 있다.

  • 동적뷰는 html 수정을 하지 못하므로 SyntaxHighlighter도 역시 적용할 수 없다. 그래서 다시 예전 템플릿으로 회귀.
  • 홈페이지에 나온 것과 같이 함수를 써서 깔끔하게 html에 집어넣는 건 실패했다. 일일이 긴 주소를 다 써서 넣어야 한다. 다행히도 Way2Blogging에 스크립트 자동 생성기가 있다.
  • 매스매티카 브러시도 있긴 한데, 내부에 매스매티카 내부 함수 2,200개 정도를 표기해 놓았나 보다. 이것 때문에 브라우저가 느려질 수 있다고 한다. 이 브러시는 본 배포본에 빠져 있어서 추가하려면 별도로 서버에 올려야 한다. 이런 문제로 매스매티카 브러시는 쓰지 않기로 했다.

2012년 3월 14일 수요일

포트란만큼 빠른 C++ 벡터 라이브러리를 파이썬에서 사용하기

GMES의 기하 관련 모듈은 원래 파이썬으로 구현되어 있었는데, 커다란 3차원 구조를 다루기에는 속도가 너무 느렸다. 속도 개선을 위해서 기하 관련 부분을 C++로 포팅하기로 결심했다. 그리곤, 기하 루틴에 많이 들어 있는 벡터 관련 함수를 어떻게 구현해야 할지 고민에 빠졌다. 파이썬에선 벡터의 자료형으로 numpyndarray를 쓰면 되지만, C++에선 어떻게 구현하는 게 가장 좋을까? 시스템 호환성과 관리의 편리성을 고려해 널리 쓰이는 방법 중에서 선택할 수 있는 것들은 아래와 같다. 사용할 벡터는 실수를 원소로 갖는 3차원 벡터로 한정한다.
  1. double *v, int size
  2. std::array<double, 3>
  3. boost::numeric::ublas::bounded_array<double, 3>
  4. blitz::TinyVector<double, 3>
1번은 가장 쉽고 가장 빠른 방법이다. SWIG를 쓴다면, numpy.i를 이용해서 numpy와 연동하기도 쉽다. 하지만 벡터 연산을 일일이 직접 구현해야 하고, 함수의 인자 부분이 못생긴 형태가 되며, 왠지 C++답지 않은 방법이다.

2번은 표준 템플릿 라이브러리에 포함된 방법이며, 훨씬 C++스럽다. 하지만 1번처럼 벡터 관련 연산을 일일이 구현해야 하며 1번보다 느리다는 문제가 있다.

3번은 boost 라이브러리에 들어있는 컨테이너로 사실상 표준이라 할 수 있으며, 벡터 관련 연산도 모두 구현되어 있다. 하지만 속도가 조금 느리다는 단점이 있다. 간단한 벡터 연산뿐만 아니라 다양한 수학연산을 사용해야 한다면 boost 라이브러리를 선택하는 것이 좋다.

4번은 blitz++ 라이브러리에 들어있는 컨테이너로 포트란에 견줄 만한 속도가 장점이다. 과학계산 분야에선 거의 표준이라 할 수 있다.

보는 바와 같이 3번이나 4번이 좋은 선택이다. GMES 구현에는 4번을 선택했는데, 그 이유는 GMES가 SWIG를 이용해서 파이썬과 연동을 하고 있기 때문이다. boost는 자체적인 파이썬 연동 방식을 제공하고 있어서 한 프로그램에서 SWIG와 boost가 동시에 사용하는 것은 뭔가 자연스럽지 못한 느낌이 들었다. 그뿐만 아니라, blitz++가 아직은 더 빠르다.

blitz::TinyVector<double, 3>을 입력이나 출력으로 사용하는 함수를 파이썬에 연결하려면 어떻게 해야 할까? 우선 아래와 같은 간단한 C++ 함수를 생각해보자.

// util.hh

#include <blitz/tinyvec.h>

namespace util {
  typedef blitz::TinyVector<double, 3> Vector3;
  
  double accumulate(const Vector3& v);
  void weight(Vector3& v, double s = 1);
}

util::accumulate는 와 벡터 성분의 합을 구하는 함수이고, util::weight는 벡터에 상수를 곱하는 함수이다. 이들 함수는 아래와 같이 별로 어렵지 않게 구현해볼 수 있다.

// util.cc

#include "util.hh"

using namespace util;

double
util::accumulate(const Vector3& v)
{
  return v[0] + v[1] + v[2];
}

void 
util::weight(Vector3& v, double s)
{
  v *= s;
}

util::accumulate는 상수 인자를 받으니, 파이썬 측의 시퀀스(tuple, list, numpy.ndarray 등)를 C++ 쪽으로 변환해 주기만 하면 된다. 반면, util::weight의 인자는 값이 변경되므로 util::Vector 형을 다시 파이썬의 시퀀스로 변경해 줘야 한다. 일단 파이썬 시퀀스 형태만 만족하면 tuple, list형은 문제가 되지 않는다. numpy.ndarray 형도 numpy가 알아서 처리한다. 우선 blitz::TinyVector<>를 고려하지 않고 기본적인 인터페이스 파일을 만들어 보자.

// util.i

%module util

%{
#include "util.hh"
%}

%include "util.hh"

이렇게만 해도 컴파일이 되고, 파이썬 모듈을 읽어들일 수 있다. 하지만 함수를 실행할 수는 없다.

>>> import util
>>> a=[1,2,3]
>>> util.accumulate(a)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: in method 'accumulate', argument 1 of type 'util::Vector const &'

역시나 함수 인자의 형태가 맞지 않다는 에러를 내보낼 뿐이다. 즉, 파이썬의 시퀀스 형을 util::Vector 형으로 변환하는 방식을 알려줘야 한다. 문제는 SWIG가 blitz::TinyVector<>를 자동으로 처리해 주지 않는다는 점이다. 이건 %typemap을 써서 직접 변환 규칙을 만들어 줘야 한다.

%typemap(in) util::Vector3&
{
  $1 = convert_to_vector3($input);
  if (!$1) return NULL;
}

%typemap(argout) util::Vector3&
{
  for (int i = 0; i < 3; i++) {
    PyObject *o = PyFloat_FromDouble((*$1)[i]);
    PySequence_SetItem($input, i, o);
  }
}

%typemap(freearg) util::Vector3&
{
  if ($1) delete $1;
}

기본적인 역할은 %typemap(in)이 맡는다. 함수 인자의 util::Vector& 부분을 찾아 이 규칙을 적용한다. $1은 C++ 함수의 첫 번째 인자를 뜻하고, $input은 파이썬 측 함수의 인자를 가리킨다. convert_to_vector에 실제 변환 코드가 들어가는데, 이 코드는 아래에서 다룬다. util::weight 함수가 제대로 작동하려면 %typemap(argout)을 써야 한다. %typemap(argout)은 출력 역할을 맡은 인자를 처리할 수 있도록 해준다. 마지막으로 %typemap(freearg)는 형 변환 중에 힙에 생성한 자료 영역을 지울 수 있도록 해준다. 아래의 convert_to_vector를 보면 %typemap(freearg)를 사용한 이유를 알 수 있다.

%{
static util::Vector3*
convert_to_vector3(PyObject* input)
{
  if (!PySequence_Check(input)) {
    PyErr_SetString(PyExc_ValueError, "Expected a sequence");
      return NULL;
  }
  if (PySequence_Length(input) != 3) {
    PyErr_SetString(PyExc_ValueError, "Size mismatch. Expected 3 elements");
    return NULL;
  }

  util::Vector* v = new util::Vector3();
  for (int i = 0; i < 3; i++) {
    PyObject *o = PySequence_GetItem(input, i);
    if (PyNumber_Check(o))
      (*v)[i] = PyFloat_AsDouble(o);
    else {
      PyErr_SetString(PyExc_ValueError, "Sequence elements must be number");
      return NULL;
    }
  }
  return v;
}
%}

파이썬측의 입력이 시퀀스인지, 길이가 3인지를 확인한 후에 util::Vector를 임시로 생성하고 여기에 인자를 하나씩 복사하도록 했다. 복사하기 전에 각 원소가 숫자인지 확인하도록 했다.

아직 조금 더 남아있다. 형식 변환 규칙이 하나 더 필요한데, 바로 %typemap(typecheck)이다. util::weight 함수의 두 번째 인자가 기본값을 가지고 있는데, SWIG은 이럴 경우, util::weight(util::Vector3&)util::weight(util::Vector3&, double)을 각각 만들고, 동적 자료형 검사를 통해서 어느 함수를 사용할지 결정하도록 코드를 생성한다. 그러므로 다음과 같이 간단한 자료형 비교 코드도 만들어 줘야 한다.

%typemap(typecheck, precedence=SWIG_TYPECHECK_POINTER) util::Vector3&
{
  $1 = false;
  if (PySequence_Check($input) && PySequence_Length($input) == 3)
    $1 = true;
}

이제 distutils를 이용해서 컴파일하려면, 다음과 같은 setup.py를 만들고, python setup.py build_ext -i라고 입력하면 파이썬에서 불러올 수 있는 모듈을 만들어준다.

from distutils.core import setup, Extension

util_module = Extension(name = '_util',
                        sources = ['util.i', 'util.cc'],
                        depends = ['util.hh'],
                        swig_opts = ['-c++'])

setup(ext_modules = [util_module])

이제 파이썬 해석기를 다시 시작하고 모듈을 읽어오면(reload로는 안 된다.) 잘 작동하는 것을 확인할 수 있다.

>>> import numpy, util
>>> v1 = [1,2,3]
>>> v2 = numpy.array(v1, float)
>>> util.accumulate(v1)
6.0
>>> util.weight(v1, 2)
>>> v1
[2.0, 4.0, 6.0]
>>> util.weight(v2, 3)
>>> v2
array([ 3.,  6.,  9.])
>>> 

2011년 10월 15일 토요일

두 개의 대전된 진자

울프램 사에선 Wolfram Demonstrations Project를 운영하고 있다. 이 홈페이지에선 매스매티카로 만든 다양한 프로그램을 만날 수 있는데, 이름에서 볼 수 있듯이 여기 있는 프로그램의 목적은 보여주기 위한 것이다. 예를 들어, 과학 책에 등장하던 고정된 그림과 그래프를 다양하게 변화시켜 가며 체험해 볼 수 있다. 여기에 등록할 프로그램은 유료 프로그램인 매스매티카로 만들어야 하지만, 실행해 보는 데에는 무료 프로그램인 Wolfram CDF Player만 있으면 되므로 누구나 프로그램을 실행해 볼 수 있다.

2차원 진자의 운동
최근에 이 프로젝트에 2차원 진자를 전산 모의 실험해 볼 수 있는 프로그램을 하나 올렸다. 진자(pendulum, 흔들이)란 어떤 물체를 줄에 매달아 흔들리게 둔 장치를 말하는데, 쉽게 괘종시계의 추를 생각하면 된다. 이 간단한 동역학 모델은 생각과 달리 정확한 해를 구할 수 없는데, 꽤 정확한 근사는 할 할 수 있다. 물리학도가 처음으로 만나는 진동계로써 교육적으로 중요한 모델일 뿐만 아니라, 물리학자로 살아가는 동안 계속 만나게 되는 진동계로써 과학에 이바지하는 바도 크다.

내가 만든 프로그램에 나오는 진자는 평면상에서 움직이는 2차원 진자이다. 보통 진자의 움직임을 계산할 때 진자의 움직임 폭이 줄의 길이에 비해 짧다는 가정을 하는데, 이렇게 하면 원래 비선형 움직임을 보이는 진자를 선형계로 근사할 수 있다. 하지만, 내 프로그램은 이 근사를 사용하지 않고 더 정확한 계산을 시도한다. 하지만 이 프로그램도 현실과 다른 사항을 몇 개 가정한다. 추를 매단 줄에 관한 건데, 이 줄의 형태는 변하지 않으며 무게가 0이라고 가정한다. 이 밖에 다른 근사도 사용하지만, 이건 아래에서 다루기로 하자.

Two Charged Conducting Pendulums의 실행 화면
프로그램에는 진자가 한 개가 아닌 두 개가 나온다. 프로그램을 실행해 보면 알겠지만, 이 두 개의 진자는 서로 연결되어 있다. 눈에 보이는 장치에 의해 연결된 건 아니고, 전기력에 의해 연결되어 있다. 바로 진자의 추에 대전 된 전하량을 설정할 수 있게 되어 있기 때문이다. 그리고 두 개의 추는 완전 도체로 만들어진 구라고 가정한다. 물체 근처에 전하를 가져가면 전하와 물체 사이엔 서로 끌어당기는 힘이 작용하게 되는데, 이 물체가 완전 도체로 이루어진 구라면, 이 힘을 쉽게 계산할 수 있다. 다만, 여기에서 문제는 어느 한 쪽의 전하가 공기 중에 있지 않고 양쪽 모두 도체 구에 분포한다는 점이다. 이렇게 되면, 무한수열을 계산해야 하고, 정확한 계산을 위해선 시간이 좀 걸린다. 이 프로그램은 실시간으로 미분방정식을 풀어서 움직임을 보여줘야 하는데, 이래서는 사용자가 좀 지루할 것 같다. 그래서 다시 근사를 한다. 이 수열의 각 항은 크기가 급격히 감소하므로, 수열 중 첫 번째 항만을 이용해서 계산한다. 사실 이렇게 해도 꽤 그럴싸한 값을 얻을 수 있기 때문이다.

이 프로그램에선 거의 모든 값을 사용자가 변경해 볼 수 있다. 또한, 전산 모의 실험에선 일반적으로 이러한 매개 변수의 단위를 없애지만, 이 프로그램의 조정 패널에선 실제 단위를 사용하게 하였다. 덕분에 왼편의 조정 패널에 나타나는 숫자가 조금 지저분해 보이긴 하지만, 사용자가 실제 수치에 조금 더 사실적은 감을 얻을 수 있을 거라 여긴다.

2011년 9월 30일 금요일

새로운 파트너


맥북에어의 미려한 라인에 젖어서 기회를 엿보던 중, 한 가지 사항이 날 돌아서게 했다. 파이썬과 C++을 주로 이용해서 프로그램을 개발하는 나에게 SWIG 컴파일에 애를 먹는 시스템은 선택사항이 아니었기 때문! 불가능하진 않겠지만, 그래도 맥을 쭉 써온 친구들이 단번에 컴파일하지 못하는 장면은 맥에 대한 환상을 깨버렸다. 뭐, 그 밖에도 맥의 부담스러운 가격도 한몫을 했지만.

씽크패드X201i 3249-nr2
대안으로 선택한 건 휴대성이 좋은 씽크패드 X 계열에 우분투를 깔아서 쓰는 것이었다. 스펙으로 들어나지 않는 씽크패드의 매력과 우분투라는 OS의 조합은 맥북에어에 대한 미련을 말끔히 날려주리라 믿었다. 그래서 선택한 모델이 X 계열 중 특이하게 100만원 이하의 가격대를 형성한 씽크패드 X201i 3249-nr2였다. 출시된 지 조금 지나기도 했지만, 원래 저가 모델로 개발된 모양이다. 나중에 안 사실이지만, 모델명에 붙은 i가 저가형이란 뜻이란다. 최신이란 수식어가 붙지 않는 모델의 장점은 리눅스에서 지원하지 않는 장치로 고생할 확률이 그만큼 낮다는 것! 같은 계열인 X201은 우분투 11.04의 인증까지 받았다.

노트북을 받은 날과 다음 날은 각종 깔린 윈도7 홈 프리미엄의 업데이트를 하며 보냈다. 하드웨어 이상이 생겼을 때나 바이오스를 업그레이드할 때 노트북에 깔려나온 윈도가 있으면 편하므로 윈도를 삭제하지는 않았다. 레노버에서 바이오스 업그레이드용 부팅 디스크 이미지를 배포하므로 이걸 이용하면 되지만, 역시나 윈도에서 ThinkVantage 시스템 업데이트를 이용하는 편이 편하다. 나온 지 오래된 녀석답게 업데이트도 참 많았다.

설치된 윈도가 64비트이니 우분투 64비트 버전을 깔기로 하고 보니, 2011년 9월에 설치할 수 있는 옵션은 두 가지가 있었다. 10.04 LTS11.04. 메모리 스틱으로 설치하는 방식을 이용했는데, 11.04는 설치 중에 커널 패닉이 발생했다. 남은 유일한 옵션은 10.04 LTS 64비트였고, 이 녀석은 다행히 별다른 문제가 없었다. 복구 영역과 공장 초기화 영역 등은 그냥 두고, 윈도에는 50GB를 할당했다. 스왑은 하드웨어 최대 지원 메모리의 두 배인 16GB를 할당하고 나니 우분투에는 420GB를 쓸 수 있었다.

디스크 공가 분배

설치 후, 바로 10.10을 거쳐 11.04로 업그레이드를 했다. 사용 중에 하드웨어 오류로 보이는 문제가 세 가지 발생했다. 첫 번짼 단 한 번 발생했지만, 무선랜 장치가 사라지는 문제. 이건 콜드 부팅 후에 장치가 살아났고 아직 이 문제가 다시 발생하지는 않았다. 인터넷 검색을 해보니, 무선 네트워크 신호가 잡히지 않거나, 무선 네트워크를 수동으로 끌 때 무선 네트워크 장치의 커널 모듈이 내려가는 현상이 있는 것 같다. 이럴 땐, 아래와 같이 수동으로 커널 모듈을 올려줘야 한다.
$ sudo modprobe r8192se_pci
두 번째는 화면이 갑자기 꺼거나 아예 재부팅되는 현상으로 하루 사용 중에도 몇 번 일어났다. 노트북의 바이오스를 확인해보니 2010년 10월 26일 자 1.31 버전이었고, 이후 바이오스 변경 목록을 살펴보니 발생 조건은 다르지만, 디스플레이 블랙아웃 문제와 재부팅 문제 해결 등의 내용이 있었다. 바이오스를 업그레이드하고 나니 이 문제는 사라졌다.

세 번째는 사용 중에 갑자기 멈추는 문제로, 노트북을 켠 상태로 들고 다니거나 바닥이 평평하지 않고 고정되지 않은 곳에 두고 사용하면 종종 문제가 발생했다. 이건 원인을 정확히 파악하지 못했는데, 배터리의 결합부가 조금 의심이 간다. 다른 씽크패드는 배터리 결합부가 꽉 끼이는 느낌인데, X201i 3249-nr2의 배터리 결합부는 조금 헐겁다. 배터리가 고정부에 조금 유격이 있는 것 같다. 노트북을 켠 상태로 이동하거나 바닥이 고정되지 않은 곳에서 사용하면 전원부의 접촉불량으로 멈추는 것이 아닌지 의심된다.

여기까지 해서 모든 하드웨어가 윈도7에서처럼 다 작동하는 건 아니다. 먼저, 가장 눈에 띄는 지문스캐너. 이건 씽크위키를 참고 해서 잡으면 된다. 하지만 로그인 방식을 지문인식으로 대체하는 것은 추천하지 않는다. 한 손가락의 지문만 등록할 수 있고 인증이 필요할 때마다 지문을 요구하는 등, 윈도보다 매우 불편하다.

충격을 감지해서 하드디스크를 보호하는 Active Protection System도 직접 손봐줘야 한다. 필요한 패키지를 설치하고, hdapsd 서비스를 시작한다.
$ sudo apt-get install tp-smapi-dkms hdapsd
$ sudo /etc/init.d/hdapsd restart
작동 여부는 hdapsd를 직접 실행해서 확인할 수 있다. 아래의 명령어를 입력한 다음, 노트북을 움직여 보면 하드디스크 파킹이 작동하는 것을 확인할 수 있다.
$ sudo hdapsd
또한 find / 명령을 내린 후 노트북을 움직여 보면, 충격이 감지될 때마다 결과 출력이 멈추는 것을 확인할 수 있다.

냉각팬의 속도는 별도의 설정을 하지 않는다면, 일정한 속도를 유지한다. 일반적인 용도에는 충분하고 CPU 사용량이 많으면 부족한 속도다. 씽크패드의 온도에 따라서 회전 속도를 조절하려면 thinkfan을 이용해야 한다. 이 설정은 잘못 설정하면 노트북에 열 손상을 가할 수도 있으니 주의를 기울여야 한다. X201i가 저가 모델이라서 그런지, 장착된 온도 센서가 하나뿐이어서 각 부분별 온도에 맞춰 세밀하게 냉각팬 설정을 할 수 없다. 더욱이 인터넷에서 아직 X201i 용의 thinkfan 설정을 찾을 수 없다. 하지만, 기본 설정만으로도 만족스럽게 작동한다는 보고가 있니 용감하게 시도해보자. 먼저, thinkfan을 설치한다.
$ sudo apt-get install thinkfan
thinkpad_acpi 모듈이 팬의 회전 속도를 조정하도록, /etc/modprobe.d/thinkpad_acpi.conf 파일에 다음 줄을 추가한다.
options thinkpad_acpi fan_control=1
마지막으로 /etc/default/thinkfan의 다섯 번째 줄을 다음과 같이 수정해서 부팅할 때, thinkfan이 시작되도록 한다.
START=yes
이제 노트북을 재부팅하면 된다.

세 가지 장치를 수동으로 설정해야 하지만, 그 외의 다른 모든 장치가 우분투에서 정상으로 작동한다. 씽크패드 답지 않게 배터리 결합이 조금 느신하지만, 이것 때문에 전원에 문제가 생긴 적은 없다. 누군가 우분투를 깔아 쓸 노트북을 추천해 달라고 한다면, 주저하지 않고 씽크패드 X201i 3249-nr2를 소개해 줄 것 같다.

2011년 9월 1일 목요일

파이어폭스 주소창의 검색 엔진 바꾸기

파이어폭스 속도가 느려서 크롬을 이용했는데, 파이어폭스 6를 써보니 크롬에 못지않은 빠른 속도를 보여준다. 크롬이 순간 검색 기능 덕분인지 웹페이지 로딩이 더 빠르긴 하지만.

그래도 이 정도 속도면 쓸만하다 싶어서 파이어폭스로 돌아와 보니, 크롬의 주소창 검색 기능이 못내 그립다. 예전엔 주소창 옆의 검색창을 가지고도 잘 썼건만, 주소창 검색의 편리함에 물들었나 보다. 파이어폭스는 주소창에 검색어를 입력하면 기본적으로 www.google.com에서 검색을 하도록 되어 있지만,  크롬처럼 검색 엔진을 쉽게 바꿀 수 없다. 난 구글의 SSL Search를 이용하고 싶은데... 어떻게 해야 할까? Beyond Technology란 블로그에서 답을 찾았다.

  1. 파이어폭스를 열고 주소창에 about:config를 입력한다. 
  2. 설정을 함부로 바꾸면 안정성이나 보안에 문제가 발생할 수 있다는 의미심장한 경고가 뜬다. 경고를 마음에 새기고 I'll be careful, I promise!를 클릭한다. 
  3. Filter 창에 keyword.URL을 입력한다.
     
  4. 검색 결과로 나온 keyword.URL 항목을 더블클릭한다.
  5. Enter string value 창이 뜨는데, 여기에 https://encrypted.google.com/search?q=를 입력한다. 다른 검색 엔진을 이용하려면 해당 URL을 입력하면 된다. 
  6. OK를 클릭하면 설정 끝! keyword.URL 항목의 Statususer set으로 변경되었고, Value에는 방금 입력한 주소가 들어가 있는 것을 확인할 수 있다.
     
  7. 이제 주소창에 검색어를 입력하고 엔터를 누르면 구글 SSL Search를 이용해서 검색 결과를 볼 수 있다.

2011년 8월 24일 수요일

C++로 간단하게 구현해보는 희소행렬

C++에서 STL을 이용하여 희소행렬(sparse matrix)을 구현한다면, 원소를 저장하기에 가장 좋은 자료형은 뭘까? 아마 map일 거다. 키를 위치 인덱스로 하고, 데이터에는 실제 값을 넣으면 된다.

STL엔 두 개의 map이 있다. 하나는 std::map이고, 다른 하나는 std::unordered_map이다. 이들의 용도는 다음과 같이 간단히 정리할 수 있다. 킷값에 따라 정렬해주는 map이 필요하다면 std::map을 사용하고, 빠른 검색이 필요하다면 std::unordered_map을 사용한다. 우린 키를 정렬할 필요는 없으므로, std::unordered_map을 이용하기로 하자.

이제 2차원 인덱스를 표현할 자료형을 결정해야 한다. C++의 내장 배열을 사용하자니 번거롭고, std::vector를 사용하자니 너무 무겁다. 2011년 8월 12일에 제정된 새로운 C++ 표준에선 std::array를 정의하고 있다. 이건, 고정된 크기의 std::vector라고 생각하면 되는데, std::vector보다 가볍고 C++ 내장 배열보다 편리하다. 행렬의 인덱스는 길이가 2로 고정되므로 std::array는 인덱스의 자료형에 딱 맞는 컨테이너이다.

이제 구현을 해보자. 먼저, 필요한 헤더를 불러온다.
// smat.cc
#include <array>
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <unordered_map>
cstdlib 헤더는 main 함수의 반환 값으로 사용할 EXIT_SUCCESS 매크로를 정의가 들어 있고, numeric 헤더는 해시 값 생성에 사용할 accumulate 함수의 선언이 들어 있다.

다음으로 할 일은 함수자(functor)를 만드는 것이다. std::unordered_map해시표를 사용하는 데, 키로부터 해시 값을 계산해서 해시표를 생성해야 한다. 기본 자료형에 대해서는 해시 값을 생성하는 함수자가 이미 선언되어 있지만, 그 외의 자료형에 대해선 우리가 직접 만들어줘야 한다. std::unary_function을 이용해서 간단하게 인덱스의 두 값을 더하는 해시 함수자를 만든다.
namespace std
{
  template <>
  struct hash<array<int, 2> >: public unary_function<array<int, 2>, size_t>
  {
    size_t operator()(const array<int, 2>& idx) const
    {
      return accumulate(idx.begin(), idx.end(), 0);
    }
  };
}
이제 희소행렬 자체를 구현할 클래스를 선언한다. 행렬 연산을 구현하는 여러 함수도 구현해야겠지만, 여기선 행렬 원소의 읽기와 쓰기에 관련된 연산자 정도만 구현해보자.
template <typename T> class SparseMatrix
{
public:
  SparseMatrix(int i, int j): i_size(i), j_size(j) {}

  T& operator()(int i, int j)
  {
    std::array<int, 2> idx;
    idx[0] = i;
    idx[1] = j;
    return mat[idx];
  }

  T operator()(int i, int j) const
  {
    std::array<int, 2> idx;
    idx[0] = i;
    idx[1] = j;
    typename std::unordered_map<std::array<int, 2>, T>::const_iterator tmp;
    tmp = mat.find(idx);
   
    if (tmp == mat.end())
      return T();
    else
      return tmp->second;
  }
   
private:
  std::unordered_map<std::array<int, 2>, T> mat;
  std::size_t i_size, j_size;
};
눈여겨볼 점은 행렬의 원소를 설정할 때 사용할 operator()와 원소를 조회할 때 사용할 operator() const를 모두 선언해야 한다는 것이다. operator()만 선언한다면, 행렬의 원소를 조회할 때마다 조회하는 인덱스에 해당하는 항목을 map에 만들게 된다. 예를 들어,
SparseMatrix<double> sm(3, 3);
for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      std::cout << sm(i, j) << " ";
    }
    std::cout << std::endl;
  }
처럼 모든 원소를 조회하기만 해도 내부 저장 장소인 mat에 모든 원소에 해당하는 항목이 만들어져 메모리를 낭비하게 된다.

실제로 원소를 설정하고 조회하는 방법은 아래와 같다.
using namespace std;

int main(int argc, char* argv[])
{
  SparseMatrix<double> sm(3, 3);
  sm(1, 2) = 1;
  sm(2, 0) = 2;

  const SparseMatrix<double>& sm_ref = sm;
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      cout << sm_ref(i, j) << " ";
    }
    cout << endl;
  }

  return EXIT_SUCCESS;
}
operator() const를 호출하려면, 상수 레퍼런스나 상수 포인터를 이용해서 SpareMatrix에 접근해야 한다. 뭐, 대충 이렇다. 이 코드는 C++0x 표준인  std::arraystd::unordered_map을 사용하는데, 이 기능이 시험적으로 구현된 거라서 이용하면 컴파일 할 때 -std=c++0x 옵션을 줘야 한다.
$ g++ -Wall -g -pedantic -std=c++0x -o smat smat.cc
실행해보면, 잘 작동하는 것을 확인할 수 있다.
$ ./smat
0 0 0
0 0 1
2 0 0
$
mat의 크기를 검사해 보면, 단 두 개의 항목만 저장하고 있는 것을 확인할 수 있다. 간단한 희소행렬 완성!

2011년 8월 23일 화요일

C++의 반복자(iterator)를 이용하여 파이썬 생성자(generator) 만들기

최근에 GMES의 C++ 모듈 설계를 변경하면서, 내부 자료형으로 STL의 컨네이너를 사용하는 클래스가 필요하게 되었다. 이 글에서 설명하려는 내용과 관계 없는 부분을 제거하면, 대략적인 형태는 아래와 같다.
// itergen.hh
#include <vector>

class A
{
public:
  A(): a(3)
  {
    for (size_t i = 0; i < a.size(); i++)
      a[i] = i;
  }

  std::vector<int>::const_iterator
  begin() const
  {
    return a.begin();
  }

  std::vector<int>::const_iterator
  end() const
  {
    return a.end();
  }

private:
  std::vector<int> a;
};
// itergen.cc
#include "itergen.hh"
이 코드는 파이썬으로 래핑하여 사용하게 되는데, 아래와 같이 생성자로 이용하고자 한다. 어떻게 해야 할까?
>>> for i in A():
...    print i
1
2
3
파이썬 생성자에 관한 API를 살펴봤는데, 이거 잠깐 보고 구현할 난이도는 아닌 것 같다. 이왕 SWIG를 이용한다면, 뭔가 더 간단한 방법이 없을까? Reference Man의 블로그에 방법이 나와 있다. 이 블로그에 나와 있는 내용을 간단하게 정리해 보자.

일단, C++ 클래스에선 시작과 끝 부분의 반복자를 반환하는 begin, end 메서드만 제공하면 된다. 이는 일반적으로 STL에서 사용하는 방식이므로 C++ 클래스에서 제공하는 것이 자연스럽다. C++ 코드에서 할 일은 여기까지다. SWIG가 제공하는 %extend 키워드를 사용하면 C++ 코드를 더럽히지 않고도 파이썬 래핑에 필요한 코드를 추가할 수 있다. swig의 인터페이스 파일은 아래와 같다.
// itergen.i
%module itergen

%{
#include "itergen.hh"
%}

%extend A {
  std::vector<int>::const_iterator* _begin()
  {
    return new std::vector<int>::const_iterator($self->begin());
  }

  std::vector<int>::const_iterator* _end()
  {
    return new std::vector<int>::const_iterator($self->end());
  }

  int _deref(std::vector<int>::const_iterator* it)
  {
    return **it;
  }

  bool _compref(std::vector<int>::const_iterator* lhs,
  std::vector<int>::const_iterator* rhs)
  {
    return *lhs == *rhs;
  }

  void _incref(std::vector<int>::const_iterator* it)
  {
    ++(*it);
  }

  %pythoncode %{
    def __iter__(self):
      it = self._begin()
      while not self._compref(it, self._end()):
          yield self._deref(it)
          self._incref(it)
  %}
};

%include "itergen.hh"
파이썬은 STL의 반복자를 제대로 다루지 못하므로, 이를 처리해 주는 모든 메서드를 C++ 측에서 만들어줘야 한다. C++ 코드를 수정할 것 없이 인터페이스 파일에서 %extend 키워드를 이용해서 관련 메서드를 추가한다.

파이썬 클래스는 __iter__ 메서드를 선언해주면, 생성자로 이용할 수 있다. 이 메서드는 앞에서 만들어준 C++ 메서드를 이용하여 C++의 반복자를 처리한다. 원리는 간단하다. STL에서 흔히 사용하는, 반복자를 이용한 컨테이너 순회를 이용하는 데, 차이점이라면 값의 반환으로 return 대신에 yield를 사용한다는 점이다. yield를 사용하면, 함수의 값은 반환되는 데, 함수는 종료되지 않고 next 메서드가 호출될 때마다 yield를 호출한 다음 지점부터 연속해서 실행한다. __iter__ 메서드는 %pythoncode 키워드를 이용하여 파이썬 프록시 클래스에 추가한다.

컴파일 과정은 아래와 같다. 인터페이스 파일로부터 프록시 클래스와 파이썬 인터페이스를 생성하고, C++ 코드를 컴파일 한 후, 공유 라이브러리로 만들어 주면 된다.
$ swig -c++ -python itergen.i
$ g++ -Wall -g -I/usr/include/python2.6 -c itergen_wrap.cxx
$ g++ -shared itergen.o itergen_wrap.o -o _itergen.so
이제 파이썬 해석기에서 모듈을 올리고 생성자를 사용해보자.
$ python
Python 2.6.5 (r265:79063, Apr 16 2010, 13:09:56)
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import itergen
>>> a=itergen.A()
>>> iter(a)
<generator object __iter__ at 0xb7720234>
>>> for i in a: print i
...
0
1
2
>>>
완료!