'Java/java.util'에 해당되는 글 2건

  1. 2008.03.31 java.util.Arrays의 정렬 알고리즘 (2)
  2. 2008.03.18 ArrayList
2008.03.31 20:04
Arrays는 7 미만의 작은 배열의 경우 insertion sort를 하고,
integer 등의 정수는 merge sort를
float 등의 부동 소수점 수는 quick sort를 합니다.

시작은 Collections.sort(List<T> lis즘t, Comparator<? supter T>) 에서 하겠습니다.
Collections class의 소스코드를 보시면
사용자 삽입 이미지
Arrays.sort()를 호출하고 있습니다.
이제 그럼 Arrays.sort로 가보겠습니다.
Arrays class의 api를 보시면, byte, char, double, float, int, long,  short, Object 그리고 Generic T의 배열에 대해 Sort method를 정의해 놓은 것을 확인하실 수 있습니다.

우선 위에서 사용된 Arrays.sort(Object[], Comparator)를 먼저 살펴보겠습니다.
이 method의 API를 읽어보면,
정렬의 결과가 stable하며, 수정된 merge sort를 사용한다고 되어 있습니다.
작은 쪽 리스트의 가장 큰 값이 큰 쪽 리스트의 가장 작은 값보다 작으면 merge를 생략하도록 수정되어 있다고 나와 있습니다.그리고 merge sort가 그렇듯, n*log(n) performance를 보장한다고 되어 있습니다.

자 그럼 ArrayList.sort(Object[], Comparator) method의 source code를 살펴보겠습니다.
사용자 삽입 이미지
바로 mergeSort를 하고 있습니다. 자 그럼 바로 mergeSort(Object[] src, Object[] dest, int low, int high, int off) 의 declaration이 있는 곳으로 가겠습니다.
사용자 삽입 이미지
흠. 이제 재밌는 부분이 나왔네요.
작은 배열은 Insertion Sort를 하게 되어 있습니다.
INSERTIONSORT_THRESHOLD 값은 static final int 타입으로 7이 선언되어 있습니다.
왜 7인지는 잘 모르겠습니다. 어쨌거나 7보다 작으면 Insertino Sort를 하게 되어 있습니다.

제일 먼저 정렬할 배열의 크기를 확인하고, 충분히 작으면 Insertion Sort를 하고 return; 이 호출됩니다. 그렇지 않을 경우, Merge Sort를 하게 되며, 배열을 반으로 나누어 Merge Sort를 하게 됩니다.
그런데 잘 사용하지 않은 operator가 나왔습니다.
>>>  이 operator를 뭘하는 걸까요. 찾아보니 unsigned bit shift right이네요. 응? 그게 모지..
java spec을 읽어봐야 할 것 같아서 패스하겠습니다.
일단 floor( the greatest integer less thatn or equal to )의 의미로 알고 넘어가겠습니다.

recursive 하게 mergeSort를 호출한다음,
merge하거나 그냥 Destination Array에 복사하거나 입니다.

그런데 Arrays class에는 정말 재밌어 보이는 method들이 많네요.
천천히 계속 살펴봐야겠습니다.
이런 소스가 그냥 공개되어 있다는 것이 신기할 뿐입니다. ^^:;;;
Posted by 나야

댓글을 달아 주세요

  1. 에이쥬어 2009.01.28 18:18  댓글주소  수정/삭제  댓글쓰기

    컴퓨터에서 정수는 2진수로 표현되죠. 한 2진수를 오른쪽으로 한 칸 밀고 맨 오른쪽 자리를 버린다는 것은 곧 2로 나누는 것을 뜻합니다. 나누기 연산보다 시프트가 더 빠르기 때문에 이용됩니다.

  2. 나야 2009.01.29 08:31 신고  댓글주소  수정/삭제  댓글쓰기

    아 그렇군요. 감사합니다. ^^

2008.03.18 23:06
java.util.ArrayList

 평소에 많이 사용했었는데, 소스를 보는 것을 처음인 것 같습니다.
윈도우에서 이클립스를 사용할 때 소스를 보려면  jdk폴더에 들어 있는
src.zip 파일을 연결해줘야 하는데 이 방법을 구글에서 검색해보기 귀찮아서
잊은 척하고 있다가 어제 프로젝트 데모가 끝나서 여유로운 마음으로
소스를 연결해줬습니다.

ArrayList  코드는 생각보다 간단하더군요.
그리고 정말 ArrayList가 들어 있습니다. ㅡㅡㅋ 당연한건가.

Josh Bloch, Neal Gafter가 author로 되어 있네요.

AbstractList<E>를 확장하고, List<E>, RandomAccess, Cloneable, java.io.Serializable을 구현하고 있습니다.

Serializable을 구현하기 위한 serialVersionUID가 설정되어 있고,
Object[] elementData 가 선언되어 있습니다.
이 elementData가 transient 로 선언되어 있는데, 지금까지 transient 가 뭔지도 모르고 있었다니.
자 검색검색
직렬화를 원하지 않는 변수에 선언한다고 하는 군요.
근데 왜 elementData에 transient가 선언되어 있는거지 ㅡㅡㅋ
직렬화를 잘 모르므로 패스

그리고
private int size가 선언되어 있고,

생성자들이 있습니다.
생성자들은 세 개가 선언되어 있는데,
우선 초기 저장 공간의 크기를 정해주는
public ArrayList(int initialCapacity)

근데 super();를 하고 있네요
음. 잠시 AbstractList를 보고 와야 겠네요.

AbstractList에서는 protected로 생성자가 하나 있고...
보니깐 ArrayList보다 AbstractList가 더 복잡하네요.

AbstractList가 200줄 정도 소스도 길고.
AbstractList부터 고고씽.






Posted by 나야

댓글을 달아 주세요