내가 가장 좋아하는 만화였지..
http://comics.com/peanuts?DateAfter=1950-10-02&DateBefore=2008-11-07&Order=s.DateStrip+DESC&PerPage=10&Search=&x=52&y=15
2008년 12월 10일 수요일
JAVA의 Collections.sort
리스트를 분류하고 섞기 위한 COLLECTIONS의 메소드 이용하기
java.util.Collections 클래스에는 List 인터페이스를 구현하는 객체를 실행하기 위해 만들어진 메소드들이 많이 있다. 이 유틸리티 클래스에는 특정 객체 리스트에서의 이진법적 검색, 한 리스트에서 다른 리스트로의 요소(elements) 복사, 리스트의 특정 위치로의 요소 변환 등을 실행하는 메소드가 포함되어 있다. 이번 테크팁에서는 Collections 클래스 중 shuffle()과 rotate()라는 두가지 간단한 메소드와, 리스트 안의 아이템들을 분류하는 sort() 메소드에 대해 알아본다. 아이템의 분류를 위해선 반드시 대상을 비교할 방법이 있어야 하는데, 여기서는 Comparable 과 Comparator를 사용하게 될 것이다.
다음 예제를 보자. 0부터 5까지 쓰여진 6장의 카드 한 벌이 있다. 처음 카드 상태를 보여주고 카드를2개씩 옮기게 되는데, 이것은 즉 rotate(2)를 호출하는 것이다. 이는 맨 밑의 카드 두 장을 맨 위로 올려놓게 된다. n개의 카드가 있을 때 n보다 작은 수 r개의 카드를 옮긴다. 결과적으로 n-r개의 카드를 맨 위에서 맨 밑으로 보내는 셈이 된다.
rotate(-r)를 대신 호출하면 r개의 카드를 맨 위에서 맨 아래로 옮기게 된다. 이것은 r개의 카드를 반대로 옮긴다고 생각하거나, rotate(n-r)이 rotate(-r)과 같다고 여길 수 있다.
이 때, 카드를 섞으면 다른 결과를 얻게 된다. Collections 클래스의 자바다큐멘테이션을 보면, 동일한 가능성을 갖는 모든 가능한 순열을 생성해내는 것으로 카드를 섞는 알고리즘을 설명하고 있다.
다음은 한 벌의 카드를 초기화하고 섞는 간단한 프로그램이다.
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class CutAndShuffle {
private static List miniDeck = new ArrayList(6);
private static void initializeDeck() {
for (int i = 0; i < 6; i++) {
miniDeck.add(new Integer(i));
}
}
private static void printDeck(String message) {
System.out.println(message + "\n");
for (int i = 0; i < 6; i++) {
System.out.println("card " + i +
" = " + miniDeck.get(i));
}
System.out.println("============");
}
public static void main(String[] args) {
initializeDeck();
printDeck("Initialized Deck:");
Collections.rotate(miniDeck, 2);
printDeck("Deck rotated by 2:");
Collections.rotate(miniDeck, -2);
printDeck("Deck rotated back by 2:");
Collections.shuffle(miniDeck);
printDeck("Deck Shuffled:");
}
}
CutAndShuffle 프로그램을 실행하면 다음과 유사한 결과를 얻을 것이다. 앞에서 말해듯이, shuffle() 명령어를 호출한 결과는 다를 것이다.
Initialized Deck: card 0 = 0 card 1 = 1 card 2 = 2 card 3 = 3 card 4 = 4 card 5 = 5 ============ Deck rotated by 2: card 0 = 4 card 1 = 5 card 2 = 0 card 3 = 1 card 4 = 2 card 5 = 3 ============ Deck rotated back by 2: card 0 = 0 card 1 = 1 card 2 = 2 card 3 = 3 card 4 = 4 card 5 = 5 ============ Deck Shuffled: card 0 = 1 card 1 = 2 card 2 = 4 card 3 = 5 card 4 = 0 card 5 = 3 ============
Collections의 shuffle()과 rotate() 메소드는 요소들을 서로 비교할 수 있는지 없는지의 가능성 여부와 관계가 없다. 그러나 분류는 요소들을 비교하는 방법이 필요하다. sort() 메소드를 구현하기 위해서는 먼저 서로 다른 두개의 객체 중 누가 우선순위인지를 판단해야한다. 이를 위해선 다음과 같은 두가지 방법이 있다.
- 분류된 대상의 타입이
java.lang.Comparable인터페이스를 구현하는지 확인한다. 이를 위해선 다음과 같은 메소드가 들어있는 클래스가 필요하다.
public int compareTo(Object o)
Comparator를 실행하는 클래스를 만들고 특정 타입의 두 대상을 비교하는 규칙을 캡슐화한다.
첫번째로, o1과 o2가 Comparable를 구현하는 클래스라면, 두 대상이 동일할 때 o1.compareTo(o2)는 0이 된다. o1이 o2보다 작으면 음수가 되고 o2보다 크면 양수가 된다. 이 때, 숫자의 값보다 음수인지 양수인지가 중요하다. 따라서 o1.compareTo(o2)와 o2.compareTo(o1)의 부호는 서로 달라야 한다. 세 개의 객체가 있을 때에도 compareTo()는 기본적인 이행성 규칙을 따른다. 다시 말해 o1.compareTo(o2)>0 이고 o2.compareTo(o3)>0이면, o1.compareTo(o3)>0이다.
두번째 접근법은 Integer 클래스를 포함하고 Comparable 인터페이스를 실행하는 래퍼 클래스의 장점을 이용하는 것이다. 결과적으로 Collections.sort() 메소드를 사용하여 Integer타입의 클래스들을 포함한 List를 쉽게 분류할 수 있다. 그 예는 다음과 같다.
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class ShuffleAndSort {
List miniDeck = new ArrayList(6);
void initializeDeck() {
for (int i = 0; i < 6; i++) {
createCard(i);
}
}
void printDeck(String message) {
System.out.println(message);
for (int i = 0; i < 6; i++) {
System.out.println("card " + i +
" = " + miniDeck.get(i));
}
System.out.println("============");
}
void createCard(int i) {
miniDeck.add(new Integer(i));
}
void sort(){
Collections.sort(miniDeck);
}
void exerciseDeck() {
initializeDeck();
Collections.shuffle(miniDeck);
printDeck("Deck Shuffled:");
sort();
printDeck("Deck Sorted:");
}
public static void main(String[] args) {
new ShuffleAndSort().exerciseDeck();
}
}
ShuffleAndCode 프로그램은 초과된 메소드를 갖는 것처럼 보인다. 물론 createCard()과 sort()는 반드시 포함되어야 한다. 각각의 메소드들을 분리해서 만드는 것은 ShuffleAndSort 클래스를 상속하기 쉽게 만들어준다. 어떤 객체들이 카드들에 추가되고, 카드들이 어떻게 분류되는지 수정하기 위해서는 이러한 메소드들을 오버라이딩함으로써 가능하게 된다. 이 경우 카드들이 섞이는 결과를 얻는다. 그런 다음 Collections.sort(miniDeck) 라고 불리는 메소드를 호출하여 카드를 분류할 수 있다.
ShuffleAndSort에서 나온 결과물은 반드시 다음과 같아야한다.
Deck Shuffled: card 0 = 4 card 1 = 2 card 2 = 1 card 3 = 3 card 4 = 5 card 5 = 0 ============ Deck Sorted: card 0 = 0 card 1 = 1 card 2 = 2 card 3 = 3 card 4 = 4 card 5 = 5 ============
Integer 클래스가 Comparable 인터페이스를 구현하므로 miniDeck은 자체적으로 분류가 가능하다. 또한, sort() 메소드의 다른 구현을 통해 다르게 분류할 수도 있다. 이 다른 구현은 List를 첫번째 인수로써 분류하고 Comparator을 두 번째 객체로 분류한다.ShuffleAndSort의 sort() 메소드를 다음과 같이 바꿀 수 있다.
void sort(){
Collections.sort(miniDeck,
Collections.reverseOrder());
}
이번에는 서열이 높은 카드부터 낮은 카드까지 분류해보자.
Comparable를 구현하지 않는 타입의 객체들을 분류하는 것을 상상해보자. 예를 들어 다음과 같은 Rank 클래스를 만들자.
public class Rank {
private int rank;
public Rank(int rank) {
this.rank = rank;
}
public int getRankInt(){
return rank;
}
public String toString() {
return "" + rank;
}
}
이제 ShuffleAndSort에서 상속되고, Rank 타입의 객체들을 생성하는 클래스를 만들자. 이는 다음과 같다.
public class UseRank extends ShuffleAndSort {
void createCard(int i) {
miniDeck.add(new Rank(i));
}
public static void main(String[] args) {
new UseRank().exerciseDeck();
}
}
UseRank을 컴파일하고 실행하면 ClassCastException이 발생한다. 이 문제를 해결하는 데에는 두가지 방법이 있다.
Comparable버전의Rank를 만든다.int타입으로 랭크를 축적하고 직접compareTo()를 구현한다.
첫번째 해결책은 Integer클래스가 Comparable을 실행한다는 사실을 이용하여 실제 랭크를 int가 아닌 Integer로 축적하는 것이다. 그러면 compareTo() 메소드가 Integer 클래스의 compareTo()를 불러온다. 이 접근법은 다음과 같다.
public class ComparableRank implements Comparable {
private Integer rank;
public ComparableRank(int rank) {
this.rank = new Integer(rank);
}
public String toString() {
return "" + rank;
}
public int compareTo(Object o) {
ComparableRank cr = (ComparableRank) o;
return (rank.compareTo(cr.rank));
}
}
두번째 해결책으로는, int로 랭크를 저장하고 다음과 같이 compareTo()를 구현하는 방법이 있다.
public int compareTo(Object o) {
ComparableRank2 cr = (ComparableRank2) o;
return (rank - cr.rank);
}
이 팁의 목적은 rank와 cr.rank 간의 차이를 잘 돌려준다는 것을 보여주는 것이다. rank의 애트리뷰트는 음수가 아니며, 카드의 사이즈가 231-1보다 작아야만 한다. 다음은 compareTo()를 구현하는 좀 더 심화된 예이다.
public int compareTo(Object o) {
ComparableRank2 cr = (ComparableRank2) o;
if (rank < cr.rank) return -1;
else return 1;
}
이것으로 한 벌의 카드 안에서 rank 애트리뷰트의 값이 고유하다는 것을 추측해 볼 수 있다. 이와 같은 비교를 확장하여 동일성도 확인해볼 수 있게 만들 수 있다. 즉 이런 경우에는 0을 리턴시키면 된다.
두 가지 접근법에서 모두 toString()을 오버라이딩함으로써 앞에서 제시했던 예시들의 포맷과 맞는 결과를 얻을 수 있도록 해야한다. 다음은 두번째 접근법에 대한 예시이다. :
public class ComparableRank2 implements Comparable {
private int rank;
public ComparableRank2(int rank) {
this.rank = rank;
}
public String toString() {
return "" + rank;
}
public int compareTo(Object o) {
ComparableRank2 cr = (ComparableRank2) o;
return (rank - cr.rank);
}
}
이 버전들은 createCard() 메소드의 내용을 변경하여 ComparableRank타입 또는 ComparableRank2타입의 객체를 로딩함으로써 구동될 수 있다.
두 개의 동등하지 않은 대상물이 최우선적으로 분류되도록 했던 두 번째 방법을 되새겨보자. Comparator를 실행하는 클래스를 만들고 특정 타입의 두 대상을 비교하기위한 규칙을 캡슐화한다. Rank타입의 객체를 가지고 이 방법을 사용해보자. 먼저 그 타입의 객체들을 만든다. 그리고 나서 객체들을 분류하기 위해 사용하는 Comparator를 만든다. 이 솔루션은 변환할 수 없거나 하위 분류하기 어려운 클래스들을 사용하는데 유용하다. 다음에 제시되는 RankComparator 클래스의 compareTo() 메소드는 ComparableRank2의 Comparator 메소드처럼 필수적이다. 이 compare() 클래스에서 지원하는 객체타입으로 캐스팅한 후 비교로직을 구현해라.
import java.util.Comparator;
public class RankComparator implements Comparator {
public int compare(Object o1, Object o2) {
Rank r1 = (Rank) o1;
Rank r2 = (Rank) o2;
return r1.getRankInt() - r2.getRankInt();
}
}
이 새로운 RankComparator를 사용하기 위해서는 UseRank의 sort() 메소드를 오버라이딩하고 두 번째 인수로 RankComparator를 패스하기만 하면 된다.
import java.util.Collections;
public class UseRankComparator extends UseRank {
void sort() {
Collections.sort(miniDeck, new RankComparator());
}
public static void main(String[] args) {
new UseRankComparator().exerciseDeck();
}
}
UseRankComparator의 결과는 다음과 같아야한다.
Deck Shuffled: card 0 = 0 card 1 = 4 card 2 = 5 card 3 = 3 card 4 = 1 card 5 = 2 ============ Deck Sorted: card 0 = 0 card 1 = 1 card 2 = 2 card 3 = 3 card 4 = 4 card 5 = 5 ============
List를 분류하기 위해서는 그 리스트 안의 아이템들이 반드시 비교될 수 있어야 한다는 사실을 배웠다. Comparable를 구현하는 타입의 아이템들을 사용할 수 있다. 다행히, 이것은 단순한 타입들을 랩핑하는 것을 포함한다. 두번째 접근법은 Comparator를 실행하는 클래스를 만들고 특정타입의 두 대상을 비교하기 위한 규칙을 캡슐화한다.
Collections에 대한 좀 더 많은 정보를 얻으려면, 자바 튜토이얼의 Collections trail를 참고하기 바란다.
피드 구독하기:
글 (Atom)