rein’s world

바로 직전에 C++ STL의 std::string.find()의 성능을 테스트했다. 그리고 실망했다 Orz. 이번에는 요즘 널리 사용되고 있는 스크립트 언어 중 하나인 Python의 문자열을 가지고 테스트를 진행해봤다.

이전 테스트와 동등한 머신에서 WindowsXP/Python2.5을 사용하여 테스트를 수행하였다. 실행 결과는 엄청나게 놀라웠다 Python의 문자열 검색이 일정 길이 이상에선 STL의 문자열 검색보다 월등히 빨랐다. 테스트 범위의 문자열에서 100ms초 이하에 검색이 끝나는 결과를 보여줬다 - 짧은 길이에서는 너무 빨리 결과가 나와서 100번 정도 루프를 돌리고 시간을 측정해야 했다. 그리고 가장 중요한 것, 문자열 길이를 늘려가는 것에 대해(이전 테스트처럼 원본 문자열과 패턴 문자열을 모두 증가) 선형으로 복잡도가 증가했다. Python 라이브러리의 문자열 검색은 단순한 (naive) 구현이 아닌 것이다.

확인해 본 결과, Python의 문자열 검색 알고리즘은 2.5 버젼에서 개선되었는데(그 이전에도 선형복잡도인듯하지만), Boyer-Moore 알고리즘을 개선한 알고리즘을 구현했다고 한다. 덕분에 저런 멋진 속도가

C++은 속도를 중시한 언어이긴하지만 라이브러리의 완비성(completeness)은 거의 제공하지 않는다. 반대로 최근에 나온 언어 - 특히 스크립트 언어들 - 는 라이브러리가 완비된 상태로 나온 경우가 대부분이다. 그래서 Python이나 C#, Java 같은 언어에서는 거의 전적으로 라이브러리에 의존하고도 프로그래밍을 할 수 있지만, C++의 문자열 검색같은 부분은 함부로 의존했다가는 (…)

얼마 전에 jstrane군이 std::string.find()가 느리다고 불평하면서 linux/g++로 성능을 테스트해서 포스팅한 것이 있다. 그런 의미에서(?) Win32/VC++ 환경에서도 테스트를 진행해봤다. 옆의 그래프가 WindowsXP/VC++2005를 가지고 테스트한 결과다. (테스트 설계는 jstrane 블로그를 참조하자; naive 입력에 대해서 최악의 성능을 뽑아내는 방식이다)

(그래프를 클릭하면 원본으로 연결됨)

길이에 대한  std::string.find()의 성능 그래프가 아름다운(…) 2차곡선을 그리고 있다. 즉, 원본 문자열의 길이가 m, 찾으려는 패턴의 길이가 n일 때 O(mn)의 성능을 보여준다는 것이다.

jstrane이 테스트한 경우에도 그랬지만  STL의 string.find() 함수 구현이 naive한 형태이기 때문에 생기는 문제다. 그러니 성능이 매우 중요한 문자열 찾기라면 Knuth-Morris-Pratt 알고리즘이나 Boyer-Moore 알고리즘을 상황에 맞게 써 줘야 할 것이다. STL이라고 만능의 무기는 아닌 것이다

Windows Live Writer는 블로그 설정을 자동으로 읽어오는 기능이 있다. 단 해당 블로깅 툴에서 특정 파일을 제공해줘야한다. 바로 wlwmanifest.xml 이란 파일인데, 이 블로그의 경우엔 이런 xml 파일로 제공되고 있다. 이 파일을 잘 사용하면 블로그 개발자와 Live Writer 쪽 개발자의 일이 잘 쪼개지게되고, 사용자의 부담도 줄어들 수 있는 것 같다. 그래서 포스팅을 하나(…)

이 파일이 Live Writer 쪽에서 사용되기 시작한 것은 베타 2 부터인데 (현재 베타 3) manifest 파일에 관한 MSDN의 설명에 따르면,

• 블로깅 툴에서 사용 가능한 기능들의 목록을 알려줄 수 있다. 태깅 같은 세부 기능이 가능한지 여부도 이를 통해 전달 가능.
• 특정 API나 기능을 위해 필요한 URI 정보를 전달해준다.
• Live Writer의 사이드바에서 사용되는 워터 마크 이미지라거나, 아이콘을 제공할 수 있다.(물론 이미지 파일이 있어야하지만)
• 웹페이지의 특정 부분으로의 링크를 버튼 형태로 사이드바에 추가할 수 있다.
• WYSIWYG 테마 템플릿을 제공할 수 있다.

…라고 한다.

계속 읽기: “Live Writer manifest 파일을 보면서” »

특히나 영/미권에서 제작된 프로그램에서 자주 보이는 실수인데 - 그렇다고 다국어 프로그래밍을 좀 해야되는 한국의 프로그래머들이 범하지 않는 것도 아니다 - ASCII나  Latin1 인코딩이 아닌 이상 글자 수 ≠ 바이트 수 라는 것.

캡쳐된 화면은 WordPress.com 에서 제공해주는 통계 기능 중 일부인데, 마지막 행의 title 항목을 보면 좀 이상한 것을 찾아 볼 수 있다.

Title 항목의 경우 원래 포스팅 제목부분이 일정 길이보다 길면 적당히 잘라서 출력되는데, 마지막 행의 경우 잘린 부분이 이상한 곳이었다. (원본의 문자열은 “게임을 만든다는 것, 문화를 만든다는 것”임)

즉 단순히 strlen 같이 바이트 수를 세는 함수로 문자열 길이를 구하고 한 문자의 중간에서 잘라버리면 저렇게 알 수 없는 문자가 마지막에 출력되게 된다. 마지막 문자나 잘라붙인 (다국어문자인) 중간 문자가 이상하게 보이면 일단 이걸 의심하자.

계속 읽기: “다국어 프로그래밍에서 흔히 범하는 실수” »

…베타 버젼의 블로깅 툴에는 스팸 트랙백이 잘 안달린다. 반대로 정식 릴리즈 버젼에서는 …(후략)

얼마 전까지는 Wordpress 2.3 Beta 혹은 RC1 이었지만 지난 화요일부터 베타 버젼 딱지를 떼고 정식 버젼이 되었다. (물론 이 블로그도 정식 버젼으로 업데이트) 사실 베타 버젼으로 쓰는 동안 일정 기간(8주?)이 경과한 포스팅에는 댓글이나 트랙백을 달지 못하게 했더니 스팸 트랙백과 댓글이 현저하게 줄었다. 덤으로 중간의 어느 버젼업에선가 댓글/트랙백을 다는 구조가 조금 바뀐 듯한거랑, rein.upnl.org 기반이 아니면 HTTP 301 응답을 통해서 한 번 redirection되게 했더니  HTTP GET으로 댓글만 달고 사라지던 스팸봇 하나가 아무 것도 못하는 눈치였다(…).

즉, 베타 버젼이 되면서 댓글이나 스팸 처리 부분에 변화가 생기는 경우도 있고 스팸 처러 메커니즘이 추가되는 경우도 있는데 이런 베타 버젼의 블로그는 보통 그 수가 적기 때문에 스팸 생성 툴들의 타겟이 되지 않는다. 그렇지만 정식 버젼이 되는 순간 (후략)

그렇다, 그래서 한 동안 스팸 댓글과 스팸 트랙백이 없는 4주간을 보냈다. 그러나 정식 버젼이 되어버린 순간, 바로 스팸 트랙백이 오기 시작했다. 물론 Akismet 이라는 플러그인의 도움으로 실제로 외부에서는 볼 일이 없긴하지만 가~끔 뚫리는 관계로 좀 귀찮다. 여튼 정식 버젼으로 변경(?)되면서 다시 영문 스팸 트랙백의 홍수에 시달리기 시작했다 Orz

WP 2.3 에 추가된 태깅 기능을 사이드바에 태그 구름 (tag cloud)로 보여주는 기능이 있다. 이 부분이 매우 단순하게 구성되어 있어서, 호출하는 PHP 함수의 인자도 조작하지 못하게 되어 있다 (내부적으로는 조작할 수 있지만 해당하는 인터페이스가 위젯 인터페이스에 없다). 그래서 그런 부분을 외부에서 조작할 수 있는 플러그인을 짜보자라고 생각했는데, 어느새 내가 만들고 싶었던 기능을 수행하는 플러그인이 나와버렸더라.  그것도 무려 2가지† (물론 포스팅에서 말했던 것을 몽땅 구현한건 아니지만 최소한의 무언가는 확실히 충족된다)

역시 해야지 하는 순간에 하지 않으면 기회는 사라지는가 보다.

*

† 우선 먼저 나온 Configurable Tag Cloud Widget : 태그 구름을 출력하는 함수의 모든 인자를 조작하게 해줌

그리고 New Tag Cloud : 거의 비슷한데 일부 옵션이 빠져있고, 사이드 바에 출력하는 부분에서 타이틀 앞 / 뒤에 출력하는 태그가 제멋대로인듯하다. (그러니까 테마에서 등록해놓은 옵션을 쓰는게 아니다)

Java 프로그래밍 언어를 처음 접한게 아마 학부 1학년 2학기의 컴퓨터 프로그래밍 수업이었던 것 같다. 당시 Java의 기능 중에 마음에 들었던 것이  - 이미 골수 C++ 프로그래머였던 rein에게는 맘에 안드는게 더 많았지만  - final 키워드의 존재였다.

Java의 final 키워드는 해당 함수를 static 하게 바인딩(binding)하게 해주거나, 상속받지 못하게 하거나 등등의 역할을 하는데, 주목했던 부분은 바로 상속을 금지하는 것. C++의 특성상, 특정 class를 상속받지 못하게하는게 필요할 때가 있다. 예를 들어서 virtual function table (가상 함수 테이블; 일명 vtable) 포인터를 위한 포인터 공간이 아까워서(매우 작은 데이터 클래스가 필요한 경우) 이러는 경우도 있고, 라이브러리의 요구사항에 의해서 그런 경우도 있을 수 있다. 그렇지만 C++의 키워드만으로는  혹은 boost::noncopyable 같이 간단한 방법으로는 이 문제를 해결할 수 없다.

그렇다면 어떤 방법으로 해결해야하는가? C++의 아버지인 Bjarne Stroustrup이 조금 복잡한 우회 방법을 하나 제시하고 있다. class DontWantDerivation 이라는 class가 상속이 되지 않게하려면 다음과 같은 클래스가 하나 필요하다.

class DontWantDerivation; // forward declaration

class Trick { 
    friend class DontWantDerivation;
    private: Trick() { } Trick( const Trick& ) { }
};

class DontWantDerivation : public virtual Trick { // class 선언 };

감이 오는가?

계속 읽기: “C++에는 final 키워드가 있는가?” »

고어핀드군의 파랜드 택틱스(FT) 포스팅을 보고 삘받아서 나도 밴티지 마스터 택틱스(VMT)에 관한 포스팅을 하나.

Falcom에서 제작했으며 시기를 1998년에 발매되어 한동안 즐겼었던 게임이다. 일본식 RPG의 명가 Falcom에서 제작되어서인지   SRPG에 속한다고 주장하고(…) 있으나 실상은 일종의 턴방식 전략 시뮬레이션 게임.

게임 자체는 구조가 굉장히 단순하다. 우선 자기 자신의 아바타인 "마스터"가 있으며, 이 마스터는 네이티얼이라는 소환수를 소환하여 전투를 벌이게 된다. 4 속성의 소환수와 그 안에서의 상성관계, 그리고 각 계열의 다양한 소환수를 사용할 수 있다. 자원은 딱 하나 마나인데, 이 마나는 점령한 마법석 수에 마스터의 마법 능력에 관한 상수를 곱해서 일정 턴마다 들어오게 된다. (마스터들은 몇 가지 직업이 있으며, 턴이 돌아오는 속도나 이동거리, 마법/물리 방어/공격 능력 등에서 차이가 남)

그제 IRC에서 채팅을 하다가 Azyu님의 제보(?)로 VMT v2 영문판이 무료로 공개되어있는 것을 발견하고 다시 플레이 - 그렇다 rein은 문명 IV를 자취방에 두고 온 것이다 Orz. 물론 VMT v2 한글판 역시 서울에 Orz

제한된 자원의 제약을 받는 유닛을 적정한 상성에 잘 맞게(…) 뽑아서 상대를 격파한다는 전형적인 전략 시뮬레이션 게임이지만, 98년에도 약간 나쁜 수준이라고 생각되던 픽셀 기반의 그래픽 - 640 480 해상도에 256 컬러다 -_-; - 을 바탕으로 한 점은 조금 문제였다고 생각된다. (그런 의미에서 국내에는 거의 알려지지 않았었고, 나중엔 잡지 부록으로 나왔던 것 같다)

계속 읽기: “밴티지 마스터 택틱스의 추억” »