비교자 가이드
비교자 가이드 (Comparators Guide)
Clojure로 데이터를 정렬하다 보면 sort가 기본으로 붙여주는 정렬 순서가 내가 원하는 순서가 아닐 때가 꽤 있어요. 이때 내가 원하는 순서로 값을 배열해 주는 함수를 직접 만들어 쓸 수 있는데, 그 함수를 **비교자(comparator)**라고 불러요. 이 문서는 Andy Fingerhut가 쓴 공식 가이드로, 비교자가 뭔지, 어떤 규칙을 지켜야 하고 어떤 실수를 피해야 하는지를 함께 다뤄요. 2016-02-22에 작성됐고, Clojure 1.10과 Java 8을 기준으로 설명하지만 대부분의 다른 버전에도 그대로 적용돼요.
출처: Clojure 공식문서
본문
요약
비교자는 두 인자 x와 y를 받아서 둘을 어떻게 정렬해야 하는지를 나타내는 값을 돌려주는 함수예요. 비교자에는 두 종류가 있어요. 정수를 돌려주는 3-way 비교자와, 불리언을 돌려주는 2-way 비교자죠. x, y의 순서에 따라 어떤 값을 돌려줘야 하는지는 아래의 "하면 되는 것"에서 자세히 설명해요.
Clojure에서 비교자는 값들을 정렬할 때, 또는 어떤 컬렉션을 원하는 정렬 순서로 유지할 때 필요해요. 예를 들어 sorted-map, sorted-set, priority-map(우선순위 큐라고도 불러요) 같은 것들이죠.
기본 비교자인 compare는 여러 경우에 잘 작동해요. 숫자를 오름차순으로 정렬하거나, 문자열·키워드·심볼을 사전(lexicographic) 순서로 정렬할 때 그리고 몇 가지 다른 경우에요. 예시와 자세한 내용은 아래에서 확인할 수 있어요.
compare가 원하는 대로 동작하지 않는다면, 직접 만든 비교자를 제공해야 해요. 아래의 권장사항은 각각 나중에 문서에서 더 자세히 설명돼요.
하면 되는 것(DOs):
- 비교자는 비교하려는 값 위에서 **전체 순서(total order)**에 기반을 둬야 해요. 데이터 세트에 나타날 수 있는 어떤 값의 쌍이든 비교할 수 있어야 하고, 어떤 값이 먼저 와야 할지(또는 같다고 볼지)를 판별할 수 있어야 해요.
- 3-way 비교자 또는 불리언 비교자를 작성하세요:
- 3-way 비교자는 두 값
x,y를 받아서 Java의 32비트int를 돌려줘요.x가y보다 앞이면 음수, 뒤면 양수, 같으면 0을 돌려주죠. 딱히 다른 반환값을 쓸 이유가 없다면 -1, 0, 1을 쓰면 돼요. - 불리언 비교자는 두 값
x,y를 받아서x가y보다 앞이면true, 그 외에는false를 돌려줘요.x와y가 같은 경우도false예요.<와>가 좋은 예시이고,<=와>=는 좋은 예시가 아니에요. 성능 참고: 불리언 비교자는 "뒤에 오는" 경우와 "같은" 경우를 구분하기 위해 두 번 호출될 수 있어요.
- 3-way 비교자는 두 값
- 기존 비교자에 인자를 반대로 넘겨서 정렬 순서를 뒤집을 수 있어요.
- "정렬 키"를 담은 같은 길이의 Clojure 벡터를 순서대로 비교하면 값들 간의 다중 필드 비교를 할 수 있어요.
- 컬렉션을 정렬하기 전에 데이터에서 "숫자가 아님"(
##NaN)을 없애거나 다른 값으로 바꾸고, 정렬 컬렉션의 키로 쓰는 것도 피하세요.
하지 말아야 할 것(DO NOTs):
- 값이 같을 때
true를 돌려주는 불리언 비교자를 작성하지 마세요. 그런 비교자는 일관성이 없어요. 정렬 컬렉션이 잘못 동작하게 만들고, 정렬도 예측할 수 없는 순서를 만들어요. - 두 값을 같은 것으로 취급하는 비교자를 정렬 세트와 정렬 맵에 쓰지 마세요. 그 두 값 중 하나만 정렬 컬렉션에 나타나게 하고 싶지 않다면 말이에요.
- 3-way 비교자를 작성할 때 정말로 알고 있는 게 아니라면 뺄셈을 쓰지 마세요.
함께 보면 좋은 것들: compare, sort, sort-by, sorted-set, sorted-set-by, sorted-map, sorted-map-by, subseq, rsubseq.
소개
여기서는 compare 함수가 제공하는 기본 정렬 순서를 먼저 설명하고, 그 다음에 다른 비교자들의 예시를 보여 주면서 직접 비교자를 작성할 때 따라야 할 지침과 피해야 할 실수를 다룰게요.
Clojure의 기본 비교자
비교자를 직접 지정하지 않으면 정렬은 내장 함수 compare가 수행해요. compare는 여러 타입의 값에 대해 다음과 같은 특정한 방식으로 정렬해요:
- 숫자: 숫자 값이 큰 순서로 정렬돼요. 두 숫자가
==로 수치적으로 같으면=가false를 돌려줘도 0을 돌려줘요. 예외: 모든 숫자x에 대해(== ##NaN x)는false인데도,##NaN자신을 포함해 모든 숫자x에 대해(compare ##NaN x)는 0이에요. - 문자열: UTF-16 코드 유닛의 시퀀스로 표현된 형태를 사전 순서(사전식 순서라고도 불러요)로 정렬해요. ASCII 부분집합으로 제한하면 알파벳 순서(대소문자 구분)예요.
- 심볼: 네임스페이스가 있으면 먼저 네임스페이스로, 같은 네임스페이스라면 그다음 이름으로 정렬해요. 네임스페이스와 이름 모두 문자열 표현이 사전 순서로 비교돼요. 네임스페이스가 없는 심볼은 모두 네임스페이스가 있는 심볼보다 앞에 정렬돼요.
- 키워드: 심볼과 같은 방식으로 정렬되지만, 키워드를 심볼과 비교하려 하면 예외가 던져져요.
- 벡터: 요소가 적은 벡터부터, 같은 길이의 벡터끼리는 사전 순서로 정렬돼요.
- Clojure ref: 만들어진 순서대로 정렬돼요.
- Comparable 인터페이스를 구현하는 모든 Java 타입: 문자, 불리언, File, URI, UUID 같은 것들이 이에 해당하는데, 각자의
compareTo메서드로 비교돼요. nil: 위의 모든 값과 비교될 수 있고, 어떤 값보다 작은 것으로 간주돼요.
compare는 타입이 "너무 다른" 두 값을 받으면 예외를 던져요. 예를 들어 정수, long, double끼리는 비교할 수 있지만, 문자열과 키워드, 키워드와 심볼은 비교할 수 없어요. 그리고 리스트, 시퀀스, 세트, 맵은 비교할 수 없죠.
아래의 sort, sorted-set, sorted-map 예시는 모두 기본 비교자를 사용해요.
user> (sort [22/7 2.71828 ##-Inf 1 55 3N])
(##-Inf 1 2.71828 3N 22/7 55)
user> (sorted-set "aardvark" "boo" "a" "Antelope" "bar")
#{"Antelope" "a" "aardvark" "bar" "boo"}
user> (sorted-set 'user/foo 'clojure.core/pprint 'bar 'clojure.core/apply 'user/zz)
#{bar clojure.core/apply clojure.core/pprint user/foo user/zz}
user> (sorted-map :map-key 10, :amp [3 2 1], :blammo "kaboom")
{:amp [3 2 1], :blammo "kaboom", :map-key 10}
user> (sort [[-8 2 5] [-5 -1 20] [1 2] [1 -5] [10000]])
([10000] [1 -5] [1 2] [-8 2 5] [-5 -1 20])
user> (import '(java.util UUID))
java.util.UUID
user> (sort [(UUID. 0xa 0) (UUID. 5 0x11) (UUID. 5 0xb)])
(#uuid "00000000-0000-0005-0000-00000000000b"
#uuid "00000000-0000-0005-0000-000000000011"
#uuid "00000000-0000-000a-0000-000000000000")
user> (sort [:ns2/kw1 :ns2/kw2 :ns1/kw2 :kw2 nil])
(nil :kw2 :ns1/kw2 :ns2/kw1 :ns2/kw2)
서로 다른 타입으로 compare를 호출하면 예외가 던져져요. 위의 숫자 타입들은 서로 비교할 수 있지만, 숫자 타입이 아닌 것과는 비교할 수 없어요. 그리고 리스트, 세트, 맵 또는 위에서 언급되지 않은 다른 타입에 compare를 쓰면 예외가 던져져요. 그런 값을 정렬하고 싶다면 직접 비교자를 구현해야 해요.
기성 비교자(Off-the-shelf comparators)
먼저, 특히 복잡한 비교자가 필요하다면 다른 사람들이 만들고 잘 검증된 비교자를 쓰는 걸 고려해 보세요.
이것의 완벽한 예시가 로케일별로 다른 순서로 서로 다른 언어의 Unicode 문자열을 정렬하는 경우예요. Java의 Collator 클래스와 ICU(International Components for Unicode)가 이런 라이브러리를 제공해요.
나만의 비교자 작성하기
역순(Reverse order)
숫자를 내림차순으로 정렬하려면 compare를 인자 순서만 바꿔서 호출하는 비교자를 작성하면 돼요.
user> (sort [4 2 3 1])
(1 2 3 4)
user> (defn reverse-cmp [a b]
(compare b a))
#'user/reverse-cmp
user> (sort reverse-cmp [4 3 2 1])
(4 3 2 1)
이렇게 짧은 함수는 Clojure의 #() 표기법으로 자주 쓰는데, 그때 두 인자는 각각 %1, %2 순서예요.
user> (sort #(compare %2 %1) [4 3 2 1])
reverse-cmp는 compare가 작동하는 모든 다른 타입에서도 잘 동작해요.
다중 필드 비교자
같은 길이의 Clojure 벡터가 사전 순서로 비교되기 때문에, 맵이나 레코드 같은 값에 대해 다중 필드 정렬을 하는 데 쓸 수 있어요. 단, 필드들이 이미 compare로 원하는 순서(또는 그 역순)에 정렬돼 있는 경우에만 가능해요.
먼저 벡터를 비교하지 않는 방법을 보여 드릴게요.
(def john1 {:name "John", :salary 35000.00, :company "Acme"})
(def mary {:name "Mary", :salary 35000.00, :company "Mars Inc"})
(def john2 {:name "John", :salary 40000.00, :company "Venus Co"})
(def john3 {:name "John", :salary 30000.00, :company "Asteroids-R-Us"})
(def people [john1 mary john2 john3])
(defn by-salary-name-co [x y]
;; :salary 값은 x와 y가 이 compare에서 바뀌어 있으므로 내림차순으로 정렬된다
(let [c (compare (:salary y) (:salary x))]
(if (not= c 0)
c
;; :name 과 :company 는 오름차순으로 정렬된다
(let [c (compare (:name x) (:name y))]
(if (not= c 0)
c
(let [c (compare (:company x) (:company y))]
c))))))
user> (pprint (sort by-salary-name-co people))
({:name "John", :salary 40000.0, :company "Venus Co"}
{:name "John", :salary 35000.0, :company "Acme"}
{:name "Mary", :salary 35000.0, :company "Mars Inc"}
{:name "John", :salary 30000.0, :company "Asteroids-R-Us"})
아래는 Clojure 벡터를 비교하는 더 짧은 방법이에요. 위와 정확히 같은 동작을 해요. 위와 마찬가지로 :salary 필드는 x와 y가 바뀌어 있기 때문에 내림차순으로 정렬되는 것에 주목하세요.
(defn by-salary-name-co2 [x y]
(compare [(:salary y) (:name x) (:company x)]
[(:salary x) (:name y) (:company y)]))
user> (pprint (sort by-salary-name-co2 people))
({:name "John", :salary 40000.0, :company "Venus Co"}
{:name "John", :salary 35000.0, :company "Acme"}
{:name "Mary", :salary 35000.0, :company "Mars Inc"}
{:name "John", :salary 30000.0, :company "Asteroids-R-Us"})
위 방식은 정렬 대상 값에서 키를 계산하는 비용이 싸다면 충분해요. 키 값을 계산하는 데 비용이 많이 든다면, 각 값에 대해 한 번만 계산하는 게 좋아요. sort-by 문서에 설명된 "decorate-sort-undecorate" 기법을 참고하세요.
불리언 비교자
Java의 비교자는 모두 3-way예요. 즉 첫 인자가 두 번째 인자보다 작다고 봐야 하는지, 같다고 봐야 하는지, 크다고 봐야 하는지에 따라 음수, 0, 양수 정수를 돌려줘요.
Clojure에서는 불리언 비교자도 쓸 수 있어요. 첫 인자가 두 번째 인자보다 먼저 와야 하면 true, 그 외(뒤에 와야 하거나 같은 경우)에는 false를 돌려주죠. 숫자만 비교하면 되는 경우 < 함수가 아주 좋은 예시예요. >는 숫자를 내림차순으로 정렬할 때 쓰면 돼요.
이런 Clojure 함수 bool-cmp-fn이 "비교자로 호출"되면, Clojure는 내부에서 대신 int를 돌려주기 위해 아래와 같은 코드를 실행해요.
(if (bool-cmp-fn x y)
-1 ; x < y
(if (bool-cmp-fn y x) ; 인자 순서가 뒤바뀐 것에 주목
1 ; x > y
0)) ; x = y
이 동작이 실제 보이는 것을 확인하려면 아무 Clojure 함수의 compare 메서드를 호출해 보면 돼요. 아래는 호출될 때 인자를 출력하는 <의 커스텀 버전 my-< 예시라, 그 함수가 두 번 이상 호출되는 경우를 눈으로 볼 수 있어요.
user> (defn my-< [a b]
(println "(my-<" a b ") returns " (< a b))
(< a b))
#'user/my-<
;; (. o (compare a b)) 는 객체 o 에 대해 인자 a, b 로 이름이 compare 인
;; 메서드를 호출한다. 이 경우 객체는 Clojure 함수 my-< 다.
user> (. my-< (compare 1 2))
(my-< 1 2 ) returns true
-1
user> (. my-< (compare 2 1))
(my-< 2 1 ) returns false
(my-< 1 2 ) returns true
1
user> (. my-< (compare 1 1))
(my-< 1 1 ) returns false
(my-< 1 1 ) returns false
0
;; Clojure 함수를 보통 방식으로 호출하면 compare 가 아니라 invoke 메서드를 쓴다.
user> (. my-< (invoke 2 1))
(my-< 2 1 ) returns false
false
더 자세한 내용이 궁금하다면 Clojure 소스 파일 src/jvm/clojure/lang/AFunction.java의 compare 메서드를 확인해 보세요.
비교자의 일반 규칙
어떤 비교자든(3-way든 불리언이든) 비교하려는 값 위에서 전체 순서와 일관된 답을 돌려줘야 해요.
전체 순서는 모든 값을 가장 작은 것부터 가장 큰 것 순으로 배열한 것인데, 일부 값들의 묶음은 서로 모두 같을 수 있어요. 어떤 값의 쌍이든 서로 비교 가능해야 해요(즉 비교자가 "이 둘을 어떻게 비교해야 할지 모르겠다" 같은 답을 내면 안 돼요).
예를 들어 정수 m과 n에 대해 m/n 형태로 쓰인 모든 분수를 수학에서 평소 하는 방식대로 작은 것부터 큰 것 순으로 배열할 수 있어요. 분수들 중 많은 것들은 서로 같을 텐데, 예를 들어 1/2 = 2/4 = 3/6 이죠. 그 전체 순서를 구현하는 비교자는 그것들을 모두 같게 취급하는 것처럼 동작해야 해요.
3-way 비교자 (cmp a b)는 a가 b보다 전체 순서에서 앞이면 음수, 뒤면 양수, b와 같다고 간주되면 0인 int를 돌려줘야 해요.
불리언 비교자 (cmp a b)는 a가 전체 순서에서 b보다 앞이면 true, a가 b보다 뒤이거나 같다고 간주되면 false를 돌려줘야 해요. 즉 숫자에 대한 <처럼 작동해야 해요. 나중에 설명하겠지만, 숫자에 대한 <=처럼 작동하면 안 돼요("정렬 세트와 맵용 비교자 실수하기 쉬움" 섹션 참고).
피해야 할 실수
정렬 컬렉션에서 비교 대상으로 쓰는 "숫자가 아님" 값 주의
Clojure의 기본 비교자 compare는 "숫자가 아님"(##NaN) 값을 모든 다른 숫자와 같은 것으로 취급해요. ##NaN이 포함된 숫자 시퀀스에 sort를 호출하면 예외가 던져질 수 있어요.
user> (sort [##NaN 5 13 ##NaN 3 7 12 ##NaN 8 4 2 20 6 9 ##NaN 50 83 19 -7 0 18 26 30 42 ##NaN 57 90 -8 -12 43 87 38])
Execution error (IllegalArgumentException) at java.util.TimSort/mergeHi (TimSort.java:899).
Comparison method violates its general contract!
예외가 던져지지 않더라도 돌려받은 시퀀스가 정렬되어 있지 않을 가능성이 커요. 그 이유는 sort가 올바르게 작동하려면 비교자가 그래야 하듯이, compare가 ##NaN을 다른 숫자들과 전체 순서로 배열하지 않기 때문이에요.
user> (sort [##NaN 10 5 13 ##NaN 3 7 12 ##NaN 8 4 2 20 6 9 ##NaN 50 83 19 -7])
(##NaN -7 2 3 4 5 6 7 8 10 12 13 ##NaN ##NaN 9 19 20 ##NaN 50 83)
##NaN은 어떤 다른 값과도 같지 않기 때문에, 아래 같은 코드로 숫자 시퀀스에서 그 값을 제거할 수 없어요.
user> (remove #(= % ##NaN) [9 3 ##NaN 4])
(9 3 ##NaN 4)
값이 ##NaN인지 판별하려면 NaN? 함수를 사용할 수 있어요. NaN? 함수는 Clojure 1.11.0에서 추가됐어요. Clojure의 모든 버전에서는 Java의 Double/isNaN 메서드를 쓸 수 있어요.
user> (remove NaN? [9 3 ##NaN 4])
(9 3 4)
user> (remove #(Double/isNaN %) [9 3 ##NaN 4])
(9 3 4)
정렬 세트와 맵용 비교자는 실수하기 쉬워요
"비교자는 실수하기 쉬워요"라고 말하는 것도 맞지만, 나쁜 비교자를 정렬 세트와 정렬 맵에 쓸 때 더 눈에 띄게 문제가 드러나는 경우가 많아요. 이 섹션에 나온 나쁜 비교자들을 써서 sort를 호출하면 대개 별문제 없거나 거의 문제가 없어요(일관성이 없는 비교자는 정렬에도 좋지 않지만요). 그런데 정렬 세트와 맵에서는 이런 나쁜 비교자 때문에 값이 정렬 컬렉션에 추가되지 않거나, 추가돼도 검색할 때 찾을 수가 없어요.
두 요소를 가진 벡터(문자열 뒤에 숫자가 오는, 예를 들어 ["a" 5] 같은)를 담는 정렬 세트를 만들고 싶다고 해 볼게요. 세트를 숫자로 정렬하고 싶고, 같은 숫자에 다른 문자열이 있는 여러 벡터를 허용하고 싶어요. 첫 시도로는 by-2nd 같은 함수를 쓸 수 있겠죠.
(defn by-2nd [a b]
(compare (second a) (second b)))
그런데 같은 숫자를 가진 여러 벡터를 추가하려 하면 어떤 일이 벌어지나 봐 볼게요.
user> (sorted-set-by by-2nd ["a" 1] ["b" 1] ["c" 1])
#{["a" 1]}
세 개의 벡터를 by-2nd가 모두 같은 것으로 취급하기 때문에 세트에는 딱 하나의 요소만 들어 있어요. 세트는 중복 요소를 담지 않아야 하므로 나머지 요소들은 추가되지 않은 거예요.
이런 경우 흔히 드는 생각이 < 대신 <=에 기반한 불리언 비교자를 쓰는 거예요.
(defn by-2nd-<= [a b]
(<= (second a) (second b)))
불리언 비교자 by-2nd-<=는 세트를 만드는 첫 단계에서는 올바르게 작동하는 것처럼 보이지만, 요소가 세트에 들어 있는지 테스트할 때는 실패해요.
user> (def sset (sorted-set-by by-2nd-<= ["a" 1] ["b" 1] ["c" 1]))
#'user/sset
user> sset
#{["c" 1] ["b" 1] ["a" 1]}
user> (sset ["c" 1])
nil
user> (sset ["b" 1])
nil
user> (sset ["a" 1])
nil
여기서 문제는 by-2nd-<=가 일관성 없는 답을 내기 때문이에요. ["c" 1]이 ["b" 1]보다 앞에 오는지 묻으면 true를 돌려주고(Clojure의 불리언→정수 비교자 변환이 이것을 -1로 바꿔요), ["b" 1]이 ["c" 1]보다 앞에 오는지 묻으면 또 true를 돌려주죠(역시 Clojure가 -1로 변환해요). 일관성 없는 비교자를 주면 정렬 데이터 구조의 구현이 어떤 동작도 보장해 주리라고 기대할 수는 없어요.
위의 "다중 필드 비교자"에서 설명한 기법들이 이 예시에 대한 올바른 비교자를 제공해요. 일반적으로 값의 일부만 서로 비교하는 것은 조심하세요. 관심 있는 필드를 모두 비교한 다음에는 어떤 종류의 동점 해소(tie-breaking) 조건을 두는 것을 고려해 보세요.
여담으로, 세트에 같은 숫자를 가진 여러 벡터를 넣고 싶지 않다면 by-2nd가 바로 써야 할 비교자예요. 정확히 원하는 동작을 제공하거든요. (미결 사항(TBD): 여기에 주의점이 있나요? sorted-set은 어떤 이유로든 요소를 =로 비교할까요, 아니면 제공된 비교자 함수만 쓸까요?)
비교자에 뺄셈 쓰기 주의
Java의 비교자는 첫 인자가 두 번째보다 작다고 취급되면 음수 int, 크다고 취급되면 양수 int, 같으면 0을 돌려줘요.
user> (compare 10 20)
-1
user> (compare 20 10)
1
user> (compare 20 20)
0
이 때문에 한 숫자 값에서 다른 숫자 값을 빼서 비교자를 작성하고 싶은 유혹이 생길 수 있어요.
user> (sort #(- %1 %2) [4 2 3 1])
(1 2 3 4)
많은 경우에 이게 작동하긴 하지만, 이 기법을 쓰기 전에 두 번(아니 세 번) 생각해 보세요. 명시적인 조건 검사로 -1, 0, 1을 돌려주거나 불리언 비교자를 쓰는 편이 오류 가능성이 적어요.
왜일까요? Java의 비교자는 32비트 int 타입을 돌려줘야 하기 때문에, Clojure 함수가 비교자로 쓰여서 어떤 종류의 숫자를 돌려주면 그 숫자는 내부에서 Java의 intValue 메서드로 int로 변환돼요. 자세한 내용은 Clojure 소스 파일 src/jvm/clojure/lang/AFunction.java의 compare 메서드를 보면 돼요.
부동소수점 숫자와 ratio를 비교할 때는, 이 때문에 1보다 작은 차이가 나는 숫자들이 같은 것으로 취급돼요. -1과 1 사이의 반환값이 int 0으로 잘려 버리기 때문이죠.
;; 이것은 올바른 답을 준다
user> (sort #(- %1 %2) [10.0 9.0 8.0 7.0])
(7.0 8.0 9.0 10.0)
;; 그런데 이것은 아니다. 나쁜 비교자가 모든 값을 같게 취급하기 때문이다.
user> (sort #(- %1 %2) [1.0 0.9 0.8 0.7])
(1.0 0.9 0.8 0.7)
;; .intValue 는 -1.0 과 1.0 사이의 모든 값을 0 으로 변환한다
user> (map #(.intValue %) [-1.0 -0.99 -0.1 0.1 0.99 1.0])
(-1 0 0 0 0 1)
이런 문제는 32비트 int로 자를 때(최하위 32비트만 남기고 나머지를 버리므로) 부호가 바뀌는 크기만큼 차이가 나는 정수 값을 비교할 때도 버그를 만들어요. long 값의 쌍 중 대략 절반은 뺄셈을 비교자로 쓰면 잘못 비교돼요.
;; 이건 괜찮아 보인다
user> (sort #(- %1 %2) [4 2 3 1])
(1 2 3 4)
;; 이건 도대체 뭐지?
user> (sort #(- %1 %2) [2147483650 2147483651 2147483652 4 2 3 1])
(3 4 2147483650 2147483651 2147483652 1 2)
user> [Integer/MIN_VALUE Integer/MAX_VALUE]
[-2147483648 2147483647]
;; .intValue 가 몇몇 선택된 값을 어떻게 자르는지. 특히 첫 번째와 마지막에 주목.
user> (map #(.intValue %) [-2147483649 -2147483648 -1 0 1
2147483647 2147483648])
(2147483647 -2147483648 -1 0 1 2147483647 -2147483648)
Java 자체도 문자열과 문자 등을 비교할 때 뺄셈 비교자를 써요. 이것은 문제를 일으키지 않는데, int로 변환된 임의의 16비트 문자 쌍을 뺀 결과는 반드시 int에 들어갈 수 있고 감싸기(wrapping around)가 발생하지 않기 때문이에요. 비교자가 그렇게 제한된 입력만 받는 게 보장되지 않는다면, 위험을 감수하지 않는 게 좋아요.
서로 다른 타입 사이에서 작동하는 비교자
가끔은 값의 컬렉션을 어떤 키로 정렬하고 싶은데, 그 키가 유일하지 않을 때가 있어요. 같은 키를 가진 값들을 어떤 예측 가능하고 반복 가능한 순서로 정렬하고 싶지만, 그 순서가 정확히 무엇인지는 크게 신경 쓰지 않는 경우죠.
간단한 예로, 두 요소를 가진 벡터들의 컬렉션이 있는데 첫 요소는 항상 문자열이고 두 번째는 항상 숫자라고 해 볼게요. 숫자 값을 오름차순으로 정렬하고 싶은데, 데이터에 같은 숫자를 가진 벡터가 두 개 이상 있을 수 있어요. 그런 경우 여러 번의 정렬에서 일관되게 동점을 해소하고 싶죠.
이 경우는 앞 섹션에서 설명한 다중 필드 비교자로 쉽게 구현돼요.
(defn by-number-then-string [[a-str a-num] [b-str b-num]]
(compare [a-num a-str]
[b-num b-str]))
모든 벡터가 같은 길이이고 각 대응 요소의 타입을 compare로 서로 비교할 수 있다면, 벡터 전체 값을 최종 동점 해소자로 쓰는 방식도 가능해요.
(defn by-number-then-whatever [a-vec b-vec]
(compare [(second a-vec) a-vec]
[(second b-vec) b-vec]))
그런데 벡터의 어떤 요소 위치에 compare로 처리하기엔 너무 다른 타입이 들어 있고, 그 벡터들이 같은 두 번째 요소를 가진다면 이 코드는 예외를 던져요.
;; 문자열과 키워드를 비교하려 하면 compare 는 예외를 던진다
user> (sort by-number-then-whatever [["a" 2] ["c" 3] [:b 2]])
Execution error (ClassCastException) at user/by-number-then-whatever (REPL:2).
class java.lang.String cannot be cast to class clojure.lang.Keyword
아래의 cc-cmp("cross class compare")는 이런 경우에 유용할 수 있어요. 다른 타입의 값들을 비교할 수 있고, 값의 타입을 나타내는 문자열을 기준으로 정렬해요. 이때 단순한 (class x)가 아니라서 Integer와 Long 같은 숫자들이 숫자 순서로 정렬될 수 있어요. clj-arrangement 라이브러리도 유용할 수 있어요.
;; comparison-class 는 포함하면 유용할 수도 있는 몇몇 타입에 대해 예외를 던진다.
(defn comparison-class [x]
(cond (nil? x) ""
;; Clojure 의 compare 가 숫자들을 모두 적절히 비교할 수 있으므로
;; 모든 숫자를 한 덩어리로 묶는다.
(number? x) "java.lang.Number"
;; sequential? 에는 리스트, cons, 벡터, 그리고 거의 모든 컬렉션의
;; seq 가 포함된다. 다만 세트나 맵 같은 순서 없는 컬렉션의 seq 를
;; 비교하는 데 쓰는 것은 권장하지 않는다(벡터는 괜찮다).
;; 이것이 아래 cmp-seq-lexi 로 비교하고 싶은 전부여야 한다.
;; 미결 사항(TBD): 빠뜨린 것이 있나? 빠지면 안 되는 것이 포함돼 있나?
(sequential? x) "clojure.lang.Sequential"
(set? x) "clojure.lang.IPersistentSet"
(map? x) "clojure.lang.IPersistentMap"
(.isArray (class x)) "java.util.Arrays"
;; Comparable 에는 Boolean, Character, String, Clojure ref,
;; 그 외 많은 것들이 포함된다.
(instance? Comparable x) (.getName (class x))
:else (throw
(ex-info (format "cc-cmp does not implement comparison of values with class %s"
(.getName (class x)))
{:value x}))))
(defn cmp-seq-lexi
[cmpf x y]
(loop [x x
y y]
(if (seq x)
(if (seq y)
(let [c (cmpf (first x) (first y))]
(if (zero? c)
(recur (rest x) (rest y))
c))
;; y 가 먼저 끝났으므로 x > y
1)
(if (seq y)
;; x 가 먼저 끝났으므로 x < y
-1
;; 시퀀스가 같은 요소를 담고 있다. x = y
0))))
;; cmp-seq-lexi 를 두 벡터에 호출해도 같은 결과를 얻을 수 있지만,
;; cmp-vec-lexi 는 벡터를 비교할 때 메모리를 덜 할당해야 한다.
(defn cmp-vec-lexi
[cmpf x y]
(let [x-len (count x)
y-len (count y)
len (min x-len y-len)]
(loop [i 0]
(if (== i len)
;; 0..(len-1) 의 모든 요소가 같다면 더 짧은 벡터가 먼저 온다.
(compare x-len y-len)
(let [c (cmpf (x i) (y i))]
(if (zero? c)
(recur (inc i))
c))))))
(defn cmp-array-lexi
[cmpf x y]
(let [x-len (alength x)
y-len (alength y)
len (min x-len y-len)]
(loop [i 0]
(if (== i len)
;; 0..(len-1) 의 모든 요소가 같다면 더 짧은 배열이 먼저 온다.
(compare x-len y-len)
(let [c (cmpf (aget x i) (aget y i))]
(if (zero? c)
(recur (inc i))
c))))))
(defn cc-cmp
[x y]
(let [x-cls (comparison-class x)
y-cls (comparison-class y)
c (compare x-cls y-cls)]
(cond (not= c 0) c ; 다른 클래스
;; 세트들을 정렬된 요소 순서의 시퀀스로 서로 비교한다.
(= x-cls "clojure.lang.IPersistentSet")
(cmp-seq-lexi cc-cmp (sort cc-cmp x) (sort cc-cmp y))
;; 맵들을 키로 정렬된 [key val] 쌍의 시퀀스로 서로 비교한다.
(= x-cls "clojure.lang.IPersistentMap")
(cmp-seq-lexi cc-cmp
(sort-by key cc-cmp (seq x))
(sort-by key cc-cmp (seq y)))
(= x-cls "java.util.Arrays")
(cmp-array-lexi cc-cmp x y)
;; 두 벡터에 대한 특별 검사. cmp-vec-lexi 가 cmp-seq-lexi 보다
;; 벡터를 비교할 때 메모리를 덜 할당해야 한다.
;; 여기서도 시퀀스를 비교할 때와 마찬가지로 요소에 대해
;; cc-cmp 를 재귀적으로 써야 한다. compare 를 쓰면 다른 타입의
;; 요소를 비교하는 능력을 잃게 되기 때문이다.
(and (vector? x) (vector? y)) (cmp-vec-lexi cc-cmp x y)
;; 둘 다 벡터가 아니면 두 시퀀스를 비교한다.
;; 예를 들어 벡터와 리스트는 여기서 비교된다.
(= x-cls "clojure.lang.Sequential")
(cmp-seq-lexi cc-cmp x y)
:else (compare x y))))
다음은 cc-cmp가 다른 타입의 값들을 비교할 수 있는 능력을 보여 주는 간단한 예시예요.
user> (pprint (sort cc-cmp [true false nil Double/MAX_VALUE 10
Integer/MIN_VALUE :a "b" 'c (ref 5)
[5 4 3] '(5 4) (seq [5]) (cons 6 '(1))
#{1 2 3} #{2 1}
{:a 1, :b 2} {:a 1, :b -2}
(object-array [1 2 3 4])]))
(nil
{:a 1, :b -2}
{:a 1, :b 2}
#{1 2}
#{1 2 3}
:a
#<Ref@1493d9b3: 5>
(5)
(5 4)
[5 4 3]
(6 1)
c
false
true
-2147483648
10
1.7976931348623157E308
"b"
[1, 2, 3, 4])
nil