Perl/SchwartzianTransform

내용출력

로그인[l]

1 번째 수정본
(1 번째 수정본부터 1 번째 수정본까지의 변경사항) (소소한 수정)
(두 수정본의 내용이 동일하거나, 수정본을 비교할 수 없음.)

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

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;

컴퓨터분류

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

Schwartzian_Transform에 있는 형태가 더 짧아서 그걸 사용
3. Intermediate Perl, Chapter 9.5.에 있는 코드를 위키페디아에 있는 형태로 짧게 썼음

이 수정본 편집일: 2007-5-29 3:39 pm (변경사항 [d])
1524 hits | Permalink | 변경내역 보기 [h] | 현재 수정본 보기 | 1 번째 수정본 소스 보기