Perl/SchwartzianTransform

내용출력

로그인[l]

1. Schwartzian Transform

예를 들어, 파일 이름의 목록을 가지고, 그 파일의 크기를 비교하여 오름차순으로 정렬한다고 할 때, 단순하게는 다음과 같이 작성할 수 있다.

my @sorted = sort { -s $a <=> -s $b } @list;

"-s" 연산은 파일의 stat을 검사하는 매우 expensive한 연산이다. N개의 파일의 sort를 위해서 이 연산을 평균 2NlogN만큼 수행해야 한다.

-s 연산의 결과를 캐시함으로써, -s 연산을 N번만 수행하는 형태로 바꿀 수 있다. 아래와 같은 구조를 Schwartzian Transform이라고 한다.1

my @sorted = map { $_ -> [0] }            # 4)
             sort { $a->[1] <=> $b->[1] } # 3)
             map { [ $_, -s $_ ] }        # 2)
             @list;                       # 1)

1) 파일명 리스트를
2) [ 파일명, 파일크기 ] 쌍으로 된 익명 배열 레퍼런스의 리스트로 바꾸고
3) 파일크기를 비교하여 배열 레퍼런스들을 정렬한 후
4) 각 익명 배열의 첫번째 원소인 파일명만 다시 리스트로 바꾼다.

당연히, 비교를 위해 사용하는 연산이 복잡할(따라서 느릴) 수록 이 변환의 이득이 커진다.

Benchmark 모듈을 사용하여 테스트해보면, 이 GyparkWiki가 있는 서버에서 /bin/ 디렉토리 아래에 있는 102개의 파일을 대상으로 비교했을때, 이 transform을 사용한 경우가 4.3배 빨랐다.

             Rate      normal schwartzian
normal      176/s          --        -77%
schwartzian 759/s        331%          --

일반적인 형태2:

@sorted = map { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map { [$_, foo($_)] }
          @unsorted;

정렬 기준이 여러 단계인 경우3:

@sorted = map { $_->[0] }
          sort { $a->[1] cmp $b->[1] or
                 $a->[2] cmp $b->[2] or
                 $a->[3] cmp $b->[3] }
          map { [ $_, foo1($_), foo2($_), foo3($_) ] }
          @unsorted;

2. Guttman Rosler Transform

한술 더 떠서, ST에서 무수한 익명 배열을 만드는 오버헤드를 피하고, sort에서 기본으로 제공하는 정렬 알고리즘을 사용하게 변환할 수 있다.4

my @words=qw(The time has come the Walrus said to speak of many things);
## 위 리스트를, 각 단어 내의 "e"또는 "E"의 갯수에 따라 정렬하는 경우

# ST
my @sorted=map { pop @$_ }
           sort{ $a->[0] <=> $b->[0] ||
                 $a->[1] cmp $b->[1] }
           map { [tr/eE/eE/,$_] } @words;

# GRT
my @sorted=map  { substr($_,4) }
           sort
           map  { pack("LA*",tr/eE/eE/,$_) } @words;

컴퓨터분류

각주:
1. 알고리즘 자체는 이전부터 있었고, Randal L. Schwartz에 의해 Perl idiom으로 널리 알려짐
2.

Schwartzian_Transform에 있는 형태가 더 짧아서 그걸 사용
3. Intermediate Perl, Chapter 9.5.에 있는 코드를 위키페디아에 있는 형태로 짧게 썼음
4. [Advanced Sorting - GRT - Guttman Rosler Transform -- Advanced Sorting - GRT - Guttman Rosler Transform]

마지막 편집일: 2012-2-11 12:25 am (변경사항 [d])
1378 hits | Permalink | 변경내역 보기 [h] | 페이지 소스 보기