Schwartzian Transform

Tags:

http://en.wikipedia.org/wiki/Schwartzian_transform

sorting시 두개의 item을 비교하기 위한 변환 함수 호출의 수를 줄이는 방법.

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

1. 각 아이템 $_를 받아 foo($_)를 통해 순서값(대소를 비교하기 위해 사용하는 수치)을 부여. 그 뒤 [원래값, 순서값]의 ordered pair로 만듦.
2. 순서값에 따라서 소팅.
3. [원래값, 순서값]에서 첫번째 아이템(즉 [0])만 꺼냄.

이 코드를 non-functional로 다시 쓰되, 파일의 변경시간에 따라 소팅하는 예를들어본다면 다음과 같음.

for each file in filesArray {
insert array(file, modificationTime(file)) at end of transformedArray
}

function simpleCompare(array a, array b) {
return a[2] < b[2] } transformedArray := sort(transformedArray, simpleCompare) for each file in transformedArray insert file[1] at end of sortedArray [/code] 따라서 먼저 변환하고, 변환된 값으로 소팅하고, 변환된 값들은 다 제거한다는 것이 요점. 반면 Naive approach 는 다음과 같을 것임. [code lang="cpp"] function naiveCompare(file a, file b) { return modificationTime(a) < modificationTime(b) } // Assume that sort(list, comparisonPredicate) sorts the given list using // the comparisonPredicate to compare two elements. sortedArray := sort(filesArray, naiveCompare) [/code] 이 경우 변환함수의 호출회수는 O(nlogn). 하지만 Schwartzian Transform의 경우 변환함수의 호출 회수가 O(n).

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *