Perl/SchwartzianTransform 페이지의 소스 보기

내용출력
로그인[l]
수정할 수 없습니다: Perl/SchwartzianTransform 는 읽기 전용 페이지입니다.
== # Schwartzian Transform ==

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

{{{#!vim perl
my @sorted = sort { -s $a <=> -s $b } @list;
}}}
"-s" 연산은 파일의 stat을 검사하는 매우 expensive한 연산이다. N개의 파일의 sort를 위해서 이 연산을 평균 <nowiki>2NlogN</nowiki>만큼 수행해야 한다.

-s 연산의 결과를 캐시함으로써, -s 연산을 N번만 수행하는 형태로 바꿀 수 있다. 아래와 같은 구조를 Schwartzian Transform이라고 한다.<footnote(알고리즘 자체는 이전부터 있었고, Randal L. Schwartz에 의해 [[Perl]] idiom으로 널리 알려짐)>
{{{#!vim perl
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%          --
}}}

일반적인 형태<footnote(WikiPedia:Schwartzian_Transform""에 있는 형태가 더 짧아서 그걸 사용)>:
{{{#!vim perl
@sorted = map { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map { [$_, foo($_)] }
          @unsorted;
}}}

정렬 기준이 여러 단계인 경우<footnote(Intermediate Perl, Chapter 9.5.에 있는 코드를 위키페디아에 있는 형태로 짧게 썼음)>:
{{{#!vim perl
@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;
}}}

== # Guttman Rosler Transform ==
한술 더 떠서, ST에서 무수한 익명 배열을 만드는 오버헤드를 피하고, sort에서 기본으로 제공하는 정렬 알고리즘을 사용하게 변환할 수 있다.<footnote([http://www.perlmonks.org/?node_id=145659 Advanced Sorting - GRT - Guttman Rosler Transform -- Advanced Sorting - GRT - Guttman Rosler Transform])>

{{{#!vim perl
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;
}}}

<div class="comments">
<longcomments(100)>
----

</div>
----
[[컴퓨터분류]]
Perl/SchwartzianTransform 페이지로 돌아가기 | 다른 수정본 보기