최근, TimSort 라는 정렬 알고리즘 이 화제가 되었습니다. TimSort 는 빠르고 안정적인 정렬 알고리즘으로, Python(>=2.3) 과 Java SE 7, 그리고 Android 에서 표준 정렬 알고리즘으로 채용되었다고 합니다.

C++ 의 std::sort() 보다도 빠르다는 벤치마크 결과가 화제가 되어(나중에 벤치마크의 오류라고 판명났지만), 그때 TimSort 의 존재를 알았습니다. 실제로 랜덤 데이터에 대해서는 Quick Sort(IntroSort) 보다 빠르지는 않지만, 정렬이라는 단순한 일을 하는 알고리즘 이 지금도 더욱 개량해오며 사람들의 관심을 끌고 있다는 것은 흥미깊은 일입니다.

개요

TimSort 는 한마디로 하면, “STL 의 IntroSort 의 Merge Sort 버젼” 입니다. 조금 더 정확하게 이야기하면 거기에 몇가지의 Heuristic 이라고 할 수 있습니다. 몇가지 테크닉의 집합체이기에, 이런 것들을 어디까지 TimSort 라고 불러야 할지는 모르겠습니다.

IntroSort

IntroSort 란, Quick Sort 의 개량버젼입니다. Quick Sort 는 상당히 빠른 알고리즘이지만, 몇가지 약점이 있습니다.

약점 중 하나는 최악계산량입니다. 피벗(Pivot)의 선택이 잘 이뤄지지 않으면, 요소 수의 2제곱에 비례한 시간이 걸리게 됩니다. 몇가지 요소를 샘플링한 뒤에 중앙값을 Pivot하면, 평균적인 데이터에 대해서는 꽤 양호한 성능을 바타내지만, 그것은 최악계산량을 보증하는 것은 아닙니다. 예를 들어, 특정 구현에 대해서 2 제곱의 시간이 걸리는 데이터를 만드는 것은 쉽고, 그것을 노려서 공격하는 것도 가능합니다.

IntroSort 에서는 이에 대처하기 위해, 재귀탐색이 요소수의 대수를 넘으면 HeapSort 로 바꾸게 됩니다. 이에 의해 최악계산량을 O(n log n)에 대입하고, 평균적인 데이터에서는 QuickSort 에 필적하는 성능을 달성합니다.

다른 하나의 약점은 요소 수가 적은 경우입니다. 적은 요소 수(< 32 정도) 에서는 계산량의 순서가 커도 단순히 오버헤드가 적은 Insert Sort 나 Select Sort 같은 알고리즘이 더 빠릅니다. 그리고 분할이 진행된 요소수가 줄어들면, Insert Sort 로 바뀝니다.

TimSort

Merge Sort 는 최악계산량 O(n log n) 이 안정적인 정렬 알고리즘으로, Quick Sort 같은 최악계산량의 문제는 발생하지 않습니다. 그러나, 요소수가 적은 경우는 오버헤드에 의해 Quick Sort 와 마찬가지로 느려집니다. TimSort는 일반적인 Merge Sort 와는 달리, 미리 어느 정도의 크기의 정렬이 끝난 열(run 이라고 부릅니다) 로 분할하고 병합합니다.

run 크기의 결정

run 크기는 Insert Sort 가 가장 빠른 범위(< 32) 가 되도록 크게 합니다.또, run 의 갯수가 2의 거듭제곱일 때, 뒷단의 병합이 빨리 끝나기 때문에 [16, 32] 의 범위로, run 의 갯수가 2의 거듭제곱이 되는 것을 선택합니다.

run 으로의 분할

우선 처음으로, 입력열의 작은 정렬이 끝난 열로 분해합니다. 입력열을 앞에서 순서대로 놓고, 단순증가하고 있는 최대의 접두사를 요구합니다. 그것이 어느 정도 커지면 그것을 하나의 run 이라고 합니다. 증가열의 크기가 너무 작은 경우는, Insert Sort 를 사용해 확장합니다. 이 때에 사용하는 Insert Sort 는 전방의 요소가 정렬이 끝났기 때문에, 도중에 수행할 수 있습니다.

처음의 두 요소가 내림차순이 되었을 경우, 증가열에서는 되도록 감소열을 위해 반전합니다. 이에 의해 Insert Sort 의 횟수를 줄일 수 있습니다. 여기에서 주의할 것은, 안전성을 위해서 감소열은 strict(<) 이어야 합니다.

입력열의 정렬이 끝난 후, 이 상태로 한번 데이터를 훑어 보는 것만으로 정렬이 끝납니다. 이 때문에 속도가 빠른 것입니다.

2분할 Insert Sort

TimSort 에서는 단순한 Insert Sort 가 아닌, 2분할 Insert Sorrt 가 사용됩니다. 이것은 요소의 삽입위치의 결정을 위해서, 정렬이 끝난 부분을 2분할 탐색하는 것입니다. 안전성을 가지도록 삽입위치를 정할 필요가 있다는 것에 주의해야 합니다.

Merge

어느 정도의 사이즈의 run 이 만들어졌다면, 이것을 병합(Merge)합니다. 병합은 평상시대로 2개씩 병합합니다. 이것을 효율있게 수행하기 위해서, 스택을 사용해 run 을 관리합니다. 앞의 상황에서 작성된 run 은 우선 스택에 올려지고, 다음과 같은 불변상황을 만족하도록 병합됩니다.

• length[top] + length[top -1] < length[top -2]
• length[top] < length[top -1]

이것을 만족하는 스택의 깊이는 가장 큰 것이라도 요소 수의 대수가 됩니다. 또, 작은 것 끼리 병합되기에, 계산량 O(n log n)을 보증할 수 있습니다 (TimSort 의 경우는 거의 대부분 같은 크기의 run 이 병합되기에 실용적으로도 충분히 빠르다고 말할 수 있습니다).

2개의 run 의 병합

TimSort 에서는 2개의 run 의 병합에도 많이 고려되어 있습니다.

연속영역

TimSort 에서는 반드시 마주 보고 있는 메모리 영역을 병합합니다. 이것은 앞의 스택의 불변조건에 의해 run의 병합을 수행하면 자연스레 만족됩니다. 옆에 있는 메모리의 영역을 병합하면

* 앞 줄 중 뒷 줄의 선두보다 적은 것
* 뒷 줄의 뒤의 요소 중, 앞 줄의 맨 뒤의 요소보다 큰 것

의 복사를 생략할 수 있습니다. 연속한 영역의 부분열만 병합하면 되는 것입니다.

범위없는 2분할 탐색

생략하는 요소를 계산하기 위해서도 2분할 탐색을 이용합니다. 단, 일반적인 2분할 탐색과는 달리, 맨 처음 범위를 고정하지 않고, 다음의 두 단계로 탐색을 수행합니다.

* 1, 2, 4, 8, ... 처럼 2의 거듭제곱 순서의 요소를, 요소가 커질때까지 본다
* 원하는 요소가 어느 범위에 있는 지 요구하기 때문에 (예를 들어, 8번째의 요소가 큰 것이라면, \[4,8\] 에 원하는 요소가 있습니다) 다시 그 범위로 2분할 탐색

병합에 있어서는, 원하는 요소는 꽤 앞에 있을 것이기에, 일반적인 2분할 탐색보다 비교횟수는 적을 것입니다( 평균적인 데이터에 대해서는 선형검색이 빠르다고 생각합니다)

Galloping Mode

남은 부분의 병합은 평상시대로, 맨 앞의 요소를 비교해서 병합해나가지만, 같은 열에서 연속해서 많이 채용되기 시작하면 (>=7), 갤로핑 모드(Galloping Mode)라고 불리는 모드로 들어갑니다.

갤로핑 모드란, 한쪽의 맨 앞의 요소보다도 작은 요소가 다른 쪽의 맨앞에 몇개 있는지를 위의 범위없는 2분할 탐색으로 구하는 것입니다. 같은 줄에서 어느정도 이상의 연속한 경우, 더 많이 연속한다고 예상할 수 있기에, 이것이 제대로 작동할 것입니다.

Conclusion

이상이 TimSort 의 알고리즘입니다. 실질적으로는 Merge Sort 라고 할 수 있습니다. 랜덤한 데이터에 대해서는 IntroSort 나 C++ 의 std::stable_sort() 와 비교해서 속도에 우위성이 있지는 않지만(std::stable_sort() 도 Merge Sort + 작은 요소로 Insert Sort), 정렬이 끝난 데이터, 또는 거의 정렬이 끝난 데이터에 대해서는 맨 처음의 run 작성 및 갤로핑 모드에서 큰 폭의 생략이 예상되기 때문에, 실제 데이터에 그런 경향이 있다면 좋은 성능을 얻을 수 있습니다. 또, Quick Sort 처럼 최악계산량이 문제가 되는 일이 없기 때문에, 이것을 표준으로 채용하는 것은 보안상의 관점에서도 충분히 메리트가 있다고 할 수 있습니다.

참고자료

• 高速な安定ソートアルゴリズム “TimSort”の解説
• Wikipedia TimSort

Jenkins 를 사용하기 까지

사실 지난주에 NHN 에서 주최하는 공개개발자 교육에 갔다왔었습니다. 평소 Jenkins 에 대해서 약간 환상 같은 게 있다고 할까, 필요성이 있다고 할까요. 좀 더 프로젝트의 품질이 나아지고 있다는 환상, 그런 걸 보면서 나름 보람을 느끼고 싶다라는 생각도 있었습니다.

아무튼 Jenkins 교육은 Java 위주의 프로젝트에 적용하는 얘기였지만, 다른 언어에서도 충분히 지원된다라는 얘기를 익히들어왔기에 대강 실습을 따라하면서 감을 익히고 회사에 와서 본격적으로 Jenkins 를 만지기 시작했습니다.

Perl & Jenkins

Jenkins 교육에서는 Maven 을 위주로 여러가지 옵션(?) 을 추가하는 것으로 간단하게 각종 Report 를 뽑아내기 위한 xml 들을 생성할 수 있었습니다. 아쉽게도 Perl 로는 Maven 만큼 쉽게 그렇게 만들기는 어려웠지요.

일단 Perl 에는 기본적으로 TAP 형식을 따르고 있기 때문에 Java 류의 JUnit 으로 결과를 뽑아낼 필요가 있었습니다. 그래서 TAP 를 JUnit 으로 쉽게 바꿔줄 수 있는 방법이 필요했죠.

bash $ prove —formatter —timer TAP::Formatter::JUnit t

위와 같은 형식으로 t 디렉토리 아래의 테스트파일들을 테스트하며 결과는 TAP::Formatter::JUnit 에 의해서 xml 파일로 나오게 됩니다.

~~~ xml <testsuite failures=“0”

         errors="0"
         time="25.6525909900665"
         tests="1"
         name="Catalyst_controller_Admin-Activity_t">
<testcase time="0"
          name="1 - Request should succeed"></testcase>
<system-out><![CDATA[ok 1 - Request should succeed

1..1 ]]></system-out>

<system-err></system-err>
</testsuite>

~~~

Task::Jenkins

사실은 Jenkins 에서 Perl 프로젝트를 올릴 때의 주요한 모듈의 묶음은 Task::Jenkins 모듈로 제공되고 있습니다. Task::Jenkins 에 있는 모듈들은,

• TAP::Formatter::JUnit
• App::Prove
• Devel::Cover

입니다.

TAP::Formatter::JUnit 의 경우는 위에서 설명했고, App::Prove 는 위의 테스트코드를 실행하는 커맨드인 prove 를 사용하기 위한 모듈입니다. Devel::Cover 는 Code Coverage 를 확인할 수 있는 모듈이구요.

일단 Jenkins 에서 Perl 프로젝트를 적용하는 준비는 기본적으로 위의 Task::Jenkins 를 설치함으로 어느 정도 끝났다고 볼 수 있습니다.

Jenkins 설치

회사내의 서버에 Jenkins 를 설치했습니다. Ubuntu 10.10 Server 버젼이며, Jenkins 의 설치는 그렇게 어렵지 않습니다.

쉽게 Google 에서 Jenkins Ubuntu 로 검색해서 나온 것들 중 첫번째를 골라봤습니다.

• Installing Jenkins on Ubuntu

apt source 추가하고 aptitude 로 설치하고, Apache 에서 Proxy 설정해주고, 이에 대한 자세한 이야기는 위의 링크에 자세히 나와 있으니 참고하시길 바랍니다.

NHN 공개개발자 교육에서는 보안상의 문제로 Tomcat 위에다가 얹어놓기를 권하셨지만, Jenkins 자체의 Standalone Server 로 충분하지 않나 생각됩니다. 뭐 어차피 사내 네트워크 안에서 사용할 것인데… 라며… =3

아무튼 이렇게 띄워서 실제로 사내에서 사용하고 있는 Jenkins Top Page 는 아래와 같습니다.

한번에 적으려니 좀 길고 해서, 일단 밑밥깔기부터 하고 다음 글부터는 좀 더 자세한 Jenkins 에서 Perl 프로젝트 적용에 대해서 상세한 캡쳐와 함께 설명하고자 합니다.

회사 선배이신 @mintegrals 께서 최근에 사내 버그질라에 올려놓은 내용을 보고 약간 코드를 수정해봤습니다.

내용인즉슨, 파일 첨부한 메일을 어떻게 보낼 수 있냐라는 것이었지요. 기존에 써놨던 메일송신을 하는 모듈이 파일첨부를 고려하지 않았던 것이었는데, 그런 상황등을 고려해서 좀 더 수정해봤습니다.

MyApp::Mail

~~~ perl package MyApp::Mail; use Moose; use namespace::autoclean; use Email::MIME; use Email::Sender::Simple ‘sendmail’; use Email::Sender::Transport::SMTP; use Encode; use MIME::Types ();

has to => (

is      => 'ro',
isa     => 'Str',
default => sub {
    Encode::encode( "MIME-Header", $_\[0\] );
},
required => 1,

);

has from => (

is      => 'ro',
isa     => 'Str',
default => sub {
    Encode::encode( "MIME-Header", $_\[0\] );
},
required => 1,

);

has subject => (

is      => 'ro',
isa     => 'Str',
default => sub {
    Encode::encode( "MIME-Header", $_\[0\] );
},
required => 1,

);

has body => (

is  => 'ro',
isa => 'Str',

);

has transport => (

is  => 'ro',
isa => 'HashRef'

);

has attachments => (

is => 'ro',
isa => 'ArrayRef\[Path::Class::File\]',
default => sub { \[\] },

);

sub _get_parts {

my $self = shift;

my @parts;
push @parts, 
    Email::MIME->create(
        attributes => {
            content_type => 'text/plain',
            charset      => 'utf8',
        },
        body => Encode::encode_utf8($self->body),
    );

for my $attachment (@{ $self->attachments }) {
    confess "File Not Found : $attachment" unless -f $attachment;
    my ($mime_type, $encoding) = MIME::Types::by_suffix($attachment->basename);
    $mime_type ||= 'multipart/mixed';
    my $file_body = $attachment->slurp;
    push @parts, Email::MIME->create(
        attributes => {
            content_type => $mime_type,
            name         => $attachment->basename,
            filename     => $attachment->basename,
            encoding     => 'base64',
            disposition  => 'attachment',
        },
        body => $file_body,
    );
}
\@parts;

}

sub send {

my $self = shift;

my $opt = {};
if ($self->transport) {
    $opt->{transport} = Email::Sender::Transport::SMTP->new( $self->transport );
}

my $email = Email::MIME->create(
    header => \[
        From    => $self->from,
        To      => $self->to,
        Subject => $self->subject
    \],
    parts => $self->_get_parts, 
);
sendmail($email, $opt);

}

PACKAGE–>meta->make_immutable;

1; ~~~

파일첨부를 위한 attachments 접근자를 추가로 지정합니다. 첨부파일은 하나가 아닌 여러개가 가능하기에 ArrayRef 를 기본형식으로 합니다. 각 요소는 반드시 Path::Class::File 로 받도록 했습니다.

MIME::Types 로 첨부파일의 확장자를 통해서 MIME-TYPE 을 뽑아내도록 하고, 알 수 없다면 multipart/mixed 로 지정했습니다.

transport 레이어를 별도로 지정할 수 있으며, transport 의 지정이 없을 경우는 당연히 로컬호스트의 smtp 를 이용하도록 합니다.

Using MyApp::Mail

위의 MyApp::Mail 을 이용하기 위해서 아래와 같이 sendmail.pl 이라는 스크립트를 준비했습니다.

~~~ perl

sendmail.pl

use strict; use warnings; use MyApp::Mail; use Path::Class::File;

my $to = ‘your@email.com’; my $from = ‘my@email.com’; my $subject = ‘MailSender Test Subject’; my $body = ‘MailSender Test Body’;

my $mailer = MyApp::Mail->new(

to => $to,
from => $from,
subject => $subject,
body    => $body,
attachments => \[
  Path::Class::File->new('test.doc'),
  Path::Class::File->new('text.pdf')
\],
transport => {
    host => 'smtp.gmail.com',
    port => 465,
    sasl_username => 'YOUR_GOOGLE EMAIL',
    sasl_password => 'YOUR_GOOGLE_PASS',
    ssl  => 1,
},

);

$mailer->send; ~~~

위에서 언급한 transport 레이어에 지메일의 smtp 를 사용하도록 합니다. 이를 위해서 물론 Google 계정정보를 입력할 필요가 있습니다.

How to Test?

Email::Sender::Manual::QuickStart 문서를 확인 해보면 Testing 관련 내용이 나옵니다.

~~~ perl use Test::More; BEGIN { $ENV{EMAIL_SENDER_TRANSPORT} = ‘Test’ } use YourCode;

YourCode->run;

my @deliveries = Email::Sender::Simple->default_transport->deliveries; ~~~

위와같은 샘플코드가 제시되어 있는데,

perl BEGIN { $ENV{EMAIL_SENDER_TRANSPORT} = ‘Test’ }

가 지정되면, 실제로 메일 송신이 이뤄지지 않습니다.

perl my @deliveries = Email::Sender::Simple->default_transport->deliveries;

에서 그동안 송신한 메일건수당 성공실패를 판별할 수 있고, 작성된 메일 내용 또한 확인이 가능합니다. 테스트코드를 작성함에 있어서 위의 두 부분이 절대적으로 필요합니다.

위처럼 테스트 코드를 작성할 시에는 실제로 메일 송신을 하지 않았기에 transport 레이어에서 발생하는 어떤 불상사는 감지할 수 없습니다.

Conclusion

• Perl 로 메일보내기 … SSMTP 와 MIME::Lite 를 사용해서!

이전에 메일보내기 관련해서 SSMTP + MIME::Lite 를 사용하는 그런 코드를 2008년쯤에 썼었네요. 부끄럽습니다. 2009년부터는 아마 MIME::Lite 를 안 썼던 것 같네요.

뭐 당장 필요로 하는 부분만 구현을 한 것일 뿐인지라, 차후에 다른 어떤 요구사항이 있다면 그에 맞춰서 다시 한번 소개를 해볼까 합니다.