[JAVA] Collections.sort()에 대해서

Collections.sort()

    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> void sort(List<T> list) {
        list.sort(null);
    }

collections.sort()는 List 안에 있는 sort()를 불러온다.

 

List sort(Comparator<? super E> c) 

    @SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

 

여기서 재밌는 부분은 List 객체를 배열로 변환한다는 점

그리고 안에서 Arrays.sort(a, (Comparator) c); 를 부른다는 점이다.

 

 

Arrays.sort(T[] a, Comparator<? super T> c)

    public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

여기서 기본은 c가 null 이므로 sort(a); 부분을 보도록 하겠습니다.

 

 

Arrays.sort(Object[] a)

    public static void sort(Object[] a) {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
    }

저는 여기서 legacyMergeSort(a)를 보도록 하겠습니다.

 

 

legacyMergeSort(Object[] a)

    /** To be removed in a future release. */
    private static void legacyMergeSort(Object[] a) {
        Object[] aux = a.clone();
        mergeSort(aux, a, 0, a.length, 0);
    }

여기서 볼 포인트는 두가지가 있습니다.

• 기존 배열을 복사한다는 점
• 병합정렬을 한다는 점

과거 전공수업에서 듣기로는 병합정렬이 항상 시간 복잡도가 nlog_n 을 유지하는 것이 장점이지만 여타 다른 정렬에 비해 메모리 사용량이 많다는 것이 단점입니다. 그러한 특징을 제대로 보여주고 있는 것 같습니다.

 

 

 

mergeSort(Object[] src, Object[] dest, int low, int high, int off)

    private static final int INSERTIONSORT_THRESHOLD = 7;


    @SuppressWarnings({"unchecked", "rawtypes"})
    private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        int length = high - low;

        // Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

    /**
     * Swaps x[a] with x[b].
     */
    private static void swap(Object[] x, int a, int b) {
        Object t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

 

mergeSort를 구현하고 있는 메소드를 보실 수 있습니다.

 

여기서 재밌는 포인트 하나가 있습니다.

INSERTIONSORT_THRESHOLD 보다 작은 사이즈는 삽입정렬로 해결한다는 점입니다.

그래서 궁금해서 찾아보았습니다.

https://stackoverflow.com/questions/6650048/why-does-java-6-arrayssortobject-change-from-mergesort-to-insertionsort-for

Why does Java 6 Arrays#sort(Object[]) change from mergesort to insertionsort for small arrays?

요약하자면 배열의 크기가 8정도 된다고 생각해봅시다. 그럴 때 병합정렬을 하게 되면 재귀적인 call을 하게 되고 그렇게 되면 런타임 시간 동안 불필요한 오버헤드가 발생하게 됩니다. 그리고 병합정렬 특성상 배열에 대한 복사 작업이 진행되다 보니 배열의 크기가 작을 경우 병합정렬보다는 삽입정렬이 더 나은 선택이 됩니다. 

 

 

** 정리 **
1. Collections의 sort는 기본적으로 List의 sort를 불러온다.
2. List의 sort에서는 List 에서 array로 변환을  하고 , Arrays.sort()를 진행한다.
3. Arrays.sort() 에서는 기본적으로 병합정렬을 선택한다. ( 퀵정렬을 사용하지 않는 이유는 제 추측으로는 최악의 시간복잡도가 n^2 이 될 수도 있기 때문에 그렇게 한게 아닐까?)
4.Arrays private으로 선언되어 있는 mergeSort를 재귀적으로 실행하는데 이 때 배열의 크기가 7미만은 삽입정렬로 해결한다. 그 이유는 재귀적으로 접근하면서 생기는 불필요한 오버헤드로 인하여 성능이 떨어질 수 있기 때문이다.

 

---

그냥 넘어가기에는 아쉬운 것 같아서 실제로 성능 테스트 해보는 시간을 가져 보았다.

 

간편하게 Arrays, List를 sort 할 때 필요한 요소들만 재구성하여 만들었다.

 

1. CustList.java

import java.util.*;

public class CustomList<E> extends AbstractList<E> {
    Object[] elementData;

    private int size;

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public static final int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

    public CustomList() {
        this.elementData = new Object[]{};
    }

    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

    E elementData(int index) {
        return (E) elementData[index];
    }

    public E set(int index, E element) {
        Objects.checkIndex(index, size);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    @Override
    public E get(int index) {
        Objects.checkIndex(index, size);
        return elementData(index);
    }

    @Override
    public int size() {
        return this.size;
    }

    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    @Override
    public void sort(Comparator c) {
        Object[] a = this.toArray();
        CustomArrays.sort(a, (Comparator)c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

    private Object[] grow() {
        return grow(size + 1);
    }

    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(10, minCapacity)];
        }
    }

    public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // assert oldLength >= 0
        // assert minGrowth > 0

        int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
        if (newLength - MAX_ARRAY_LENGTH <= 0) {
            return newLength;
        }
        return hugeLength(oldLength, minGrowth);
    }

    private static int hugeLength(int oldLength, int minGrowth) {
        int minLength = oldLength + minGrowth;
        if (minLength < 0) { // overflow
            throw new OutOfMemoryError("Required array length too large");
        }
        if (minLength <= MAX_ARRAY_LENGTH) {
            return MAX_ARRAY_LENGTH;
        }
        return Integer.MAX_VALUE;
    }

}

실제 ArrayList에서 쓰이는 메소드를 추려서 넣어놨다. 기본적으로 AbstractList를 상속 받아서 구현하였다.

 

2. CustomArrays.java

import com.sun.istack.NotNull;
import com.sun.istack.Nullable;

import java.util.Comparator;

public class CustomArrays {
    private CustomArrays () {}
    public static<T> void sort(@NotNull T[] a, @Nullable Comparator<? extends T> c) {
        sort(a);
    }
    public static void sort(@NotNull Object[] a){
        legacyMergeSort(a);
    }
    private static void legacyMergeSort(Object[] a) {
        Object[] aux = a.clone();
        mergeSort(aux,a,0,a.length,0);
    }
    private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        int length = high - low;

        if (length<2)
            return;


        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }
    
}

 

원래 Arrays 안에 있는 mergeSort는 다음 아래와 같이 구현되어 있다.

 

        if (length < 7) {	//삽입정렬
            for(destLow = low; destLow < high; ++destLow) {
                for(destHigh = destLow; destHigh > low && ((Comparable)dest[destHigh - 1]).compareTo(dest[destHigh]) > 0; --destHigh) {
                    swap(dest, destHigh, destHigh - 1);
                }
            }

 

 

그럼 실제 테스트를 진행해보겠습니다.

 

class SimpleTest {
    private static final Random RANDOM = new Random();
    private static final int SIZE = 20000000;

    @Test
    void testPureMerge() {
        long start2 = System.currentTimeMillis();
        CustomList<Integer> customList = new CustomList<>();
        for (int i = 0; i < 2000000; i++) {
            customList.add(randomInt());
        }
        customList.sort(null);
        long finish2 = System.currentTimeMillis();
        System.out.println("순수하게 2미만으로 가기 전까지 병합정렬을 했을 때: "+ (finish2-start2)); //878, 884
    }

    @Test
    void testOriginArraysSort() {
        long start = System.currentTimeMillis();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 2000000; i++) {
            list.add(randomInt());
        }
        list.sort(null);
        long finish = System.currentTimeMillis();
        System.out.println("기본으로 제공하는(7미만이 삽입정렬로 돌아갈 때) : "+ (finish-start));   //817, 826
    }



    private int randomInt() {
        return 1 + RANDOM.nextInt(SIZE);
    }

}

보시면 2백만 개 일때 저정도의 성능 차이가 발생하는데 갯수가 억 단위로 된다면 초 단위의 성능 차이가 발생할 수 있다는 것을 감안하면 확실히 7개 미만일 때 삽입정렬을 쓴다면 더 빠른 성능으로 사용할 수 있다.

 

근데 일정 갯수가 커지니깐 순수하게 병합정렬한 시간이 더 짧은 것을 볼 수가 있다. 음....

이 테스트에서 사용한 갯수: 200_000_000

좀 더 나중에 확인해봐야 할 것 같다. 

 

---

2차 테스트

전문가를 위한 파이썬을 읽다가 이러한 부분을 보게 되었다.

sorted()와 list.sort()에 사용된 정렬 알고리즘은 팀정렬이다. 팀정렬은 데이터의 정렬된 정도에 따라 삽입 정렬과 병합 정렬 사이를 전환하는 적응형 알고리즘이다. 실세계 데이터에는 정렬된 데이터 덩어리들이 들어 있는 경우가 많기 때문에 상당히 효율적이다.

오?! 그래 그럼 진짜 한 번 확인해보자

 

이번에는 더 정밀하게 테스트 하기 위해서 nanoTime을 쓰기로 했다.

 

    @Test
    void testPureMerge() {
        long start2 = System.nanoTime();
        CustomList<Integer> customList = new CustomList<>();
        int value = 0;
        for (int i = 0,j=0; i < THRESHOLD; i++,j++) {
            value += randomInt();
            customList.add(value);
            if (j==5){
                value = 0;
                j=0;
            }
        }
        customList.sort(null);
        long finish2 = System.nanoTime();
        System.out.println("순수하게 2미만으로 가기 전까지 병합정렬을 했을 때: "+ (finish2-start2)); //797_125_740
    }

    @Test
    void testOriginArraysSort() {
        long start = System.nanoTime();
        List<Integer> list = new ArrayList<>();
        int value = 0;
        for (int i = 0,j=0; i < THRESHOLD; i++,j++) {
            value += randomInt();
            list.add(value);
            if (j==5){
                value = 0;
                j=0;
            }
        }
        list.sort(null);
        long finish = System.nanoTime();
        System.out.println("기본으로 제공하는(7미만이 삽입정렬로 돌아갈 때) : "+ (finish-start));   //590_920_861
    }

진짜로 어느정도 정렬된 리스트에서는 기본으로 제공하고 있는 팀정렬(삽입정렬 + 병합정렬)이 더 빠르다는 것을 알 수 있다!

 

결론
1. 완전 정렬이 안된 리스트에서는 일정크기 이상에서는 오히려 병합 정렬이 더 빠르다.
2. 일정 부분마다 정렬되어 있을 경우에는 팀정렬(삽입정렬 +병합정렬)의 속도가 훨씬 빠른 것을 볼 수가 있다.