카톡 방에서, Arrays.sort를 호출했을 때, compare 함수에서 키 순서가 바뀌는 거 같다고 누군가 질문을 해 주셨습니다. 이 질문에 대한 답을 상세 분석에서 정리하고자 합니다. 당연하게도, 이 글은 java나 python에서 쓰는 timsort에 대한 내용은 아닙니다. 그런데, 설명을 보다 보면, 팀소트가 상당히 많이 언급됩니다. 즉, 알아두면 좋으니 이해하기 쉽게 되어 있는 이 사이트나, 네이버 d2에 올라온 글을 먼저 읽고 오시는 것을 권해드립니다.
여기에 팀소트 전체를 쓰기에는 넘사급으로 길어지기 때문입니다. java 8u41에서 실행하였습니다.
해당 상황을 재현하기 위해서, 간단하게 MyObj 클래스를 만들어 보았습니다. 여기에는 간단하게 getx하고, toString만 재정의 되어 있습니다.
다음에, MyObj 객체 배열을 Comparator를 이용해서, 정렬할 겁니다.
키 2개가 역순으로 들어갔음을 알 수 있습니다. 처음에 저는 그냥 정렬 정책 때문에 그런 게 아니냐고 답을 주었습니다. 그런데, 이 이야기만 하기에는 무책임 한 듯 하여, 디버그를 해 보았습니다.
Trace를 걸어보면, 아래와 같이 호출 스택이 보입니다.
먼저, Timsort라는 친숙한 대상이 보이는데요. 해당 부분만 보겠습니다.
MIN_MERGE는 32입니다. 예제 프로그램의 배열 크기는 2였고, 이는 MIN_MERGE보다 한참 작은 수치이므로, 216번째 줄로 들어옵니다. countRunAndMakeAscending을 수행하고, binarySort를 수행하게 되는데요. 여기서 후자는 binary search를 이용한 인서션 소트를 이용합니다.
사실 비슷한 트릭을 이 글에서도 소개한 적이 있습니다. 이것은 참고용으로만 보셔도 좋겠습니다.
이 때, lo와 hi는 각각 0, 2입니다. 이게 그대로 countRunAndMakeAscending으로 들어오게 됩니다. 그러면 이 메서드에서는 대체 무엇을 할까요?
먼저, runHi는 lo보다는 큽니다. 이것이 무엇인지는 모르겠지만, lo < runHi임을 유추할 수 있습니다.
다음에, 351번째 줄을 보면, a[runHi], a[lo]를 비교합니다. 여기서 runHi > lo이므로, 거꾸로 비교하는 셈이 되어버립니다. 351번째 줄에 언급된 c.compare는, 무엇을 의미할까요? c는 Comparator이고 이것은 제가 새로 생성한 비교자의 참조값을 의미합니다. 제가 9번째 줄에서 호출한, 그 비교자를 봅시다.
그러면 여기에, compare가 재정의가 되어 있는데요. 이것을 불러옵니다. a[runHi], a[runHi-1]을 불러왔을 겁니다. 처음에는 2개의 키, a[lo+1]과 a[lo]를 비교할 겁니다. 다음에는 a[lo+2]와 a[lo+1]. 이런 식으로 계속 비교를 하게 되는데요. 거꾸로 비교하고 있습니다.
노란색이 1번째 인자, 군청색이 2번째 인자로 들어간 상황입니다. 이 예에서는 증가하는 상황이므로, 바뀌지 않습니다.
해당 메서드가 끝난 직후 상태를 보면, 3, 30 순으로 재배열이 되었음을 알 수 있습니다.
그러면 이 경우는 어떨까요? 30, 3 순서로 들어왔습니다. 천천히 생각해 봅시다.
3, 30 순으로 들어옵니다. 여기서, 3이 30보다는 앞서는데요. 이 때, runHi 값은 1입니다. 어디까지 내림차순일까요? 를 보니까 runHi가 2일 때는 이미 끝입니다. 따라서, 30, 3을 reverse 시킵니다.
위와 같이 재 정렬이 됩니다.
이 경우에는 어떨까요? 일단, 5도 MIN_MERGE 값인 32보다는 작거나 같으므로, countrunandmakeascending 메소드가 1번 수행되고, binarysort 메소드가 수행될 겁니다. 중요한 것은 전자는, if, else문으로 이루어진 메서드라는 겁니다. if나 else 안에는 해당 위치로부터 연속으로 감소, 혹은 증가하는 길이를 찾기 위해서 쓰고 있습니다.
그러므로, 증가나 감소 구간이 여러개가 나타난다고 해도, 아래와 같이 수행될 겁니다.
lo 부터 연속으로 감소, 혹은 증가하는 구간은 군청색으로 칠한 부분입니다.
그러므로 이 부분만 오름차순으로 바뀝니다.
디버그 트레이스를 해 봐도 똑같이 나옵니다. 이 문서에 나온 대로 수행을 하지 않는데 괜찮을까요? run이 오름차순으로 정렬이 되지 않습니다. 그에 대해서 간단한 이유를 설명하면, MIN_MERGE인 32보다 작기 때문입니다. 나머지 일은 binarysort에 맡기는 셈입니다. 그리고 정렬할 배열의 크기가 32 이하일 때, n^2짜리 알고리즘이 생각보다 비용이 크지도 않고, 그 중 하나는 System.Arraycopy 등으로 최적화 할 여지도 남아 있습니다.
'레퍼런스 > 분석' 카테고리의 다른 글
| java computeifpresent 메소드 : 이미 있는 키의 대응 값에 새 값을 적용한다. (0) | 2021.03.15 |
|---|---|
| java compareTo 메소드 : 순서가 중요한 곳에서 잘 쓰인다. (0) | 2021.02.17 |
| java 두 배열 비교할 때 어떻게 하면 좋을까요? (4) | 2021.01.19 |
| java UnmodifiableCollection : 무엇이 다른가요? (0) | 2020.11.08 |
| Java의 String.valueOf 메서드의 동작과 lombok의 ToString 어노테이션의 스택 오버플로우 (0) | 2020.11.05 |
최근댓글