[JAVA] [Collections] binarySearch에 대해서

알고리즘 문제를 풀면서 은근 많이 쓰이는 Collections 프레임워크!

오늘 볼 것은 binarySearch 입니다.

 

우선 형태는 다음과 같습니다.

Collections.binarySearch

    public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

 

1. RandomAccess

RandomAccess는 인터페이스로서 ArrayList나 Vector와 같이 중간의 값을 알고 싶을 때 순차적으로 가는 것이 아닌 바로 갈 수 있는 형태를 표시하는 인터페이스라고 생각하시면 됩니다.

 

a. ArrayList.java

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
}

b. LinkedList.java

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
}

c. Vector.java

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
}

위의 세가지 List를 구현한 클래스를 보시면 ArrayList와 Vector 2 클래스만 RandomAccess를 포함하고 있는 것을 알 수 있습니다.

 

2. BINARYSEARCH_THRESHOLD

크기에 대한 임계점으로서 값은 5000에 해당한다. 5000 이상의 큰 이분탐색일 경우에는 iterator를 통해 찾게 된다고 한다.(단 ArrayList와 Vector와 같이 RandomAccess가 있을 경우에는 제외)

this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.

 

 

3. indexedBinarySearch

    private static <T>
    int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
        int low = 0;
        int high = list.size()-1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = list.get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }

저희가 흔히 아는 이분탐색의 구현인 것 같다.

• 중간 지점을 구한다.
• 중간 값과 구하고자 하는 값의 비교를 통해 중간값이 작다면 low를 중간값+1을 한다.
• 만일 더 크다면 high를 mid-1을 한다.
• 같을 경우에 반환한다.
• 만일 값이 없을 경우 음의 값을 반환한다.

 

 

4. iteratorBinarySearch

    private static <T>
    int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
    {
        int low = 0;
        int high = list.size()-1;
        ListIterator<? extends Comparable<? super T>> i = list.listIterator();

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = get(i, mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }

차이점이 있다면 함수 이름대로 iterator를 통해 이분탐색을 한다는 것 정도 이다.

 

그러면 실제로 얼마만큼의 성능의 차이가 있을 지 확인해보자!

---

여기서 주목할 점은 ArrayList, Vector와 같이 RandomAccess를 가지고 있는 클래스일 경우에는 indexedBinarySearch로 넘어가기 때문에 LinkedList로 테스트를 진행했다는 점 고려해주시면 될 것 같습니다.

 

public class CustomCollections {
    private CustomCollections() {}
    public static <T extends Comparable<? super T>> void sort(@NotNull CustomList<T> list) {list.sort(null);}

    public static <T>
    int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
        int low = 0;
        int high = list.size()-1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = list.get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }

    public static <T>
    int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
    {
        int low = 0;
        int high = list.size()-1;
        ListIterator<? extends Comparable<? super T>> i = list.listIterator();

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = get(i, mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }

    private static <T> T get(ListIterator<? extends T> i, int index) {
        T obj = null;
        int pos = i.nextIndex();
        if (pos <= index) {
            do {
                obj = i.next();
            } while (pos++ < index);
        } else {
            do {
                obj = i.previous();
            } while (--pos > index);
        }
        return obj;
    }
}

 

 

import java.util.*;

class SimpleTest {
    private static final Random RANDOM = new Random();
    private static final int SIZE = 3000;
    private static final int THRESHOLD = 5000;
    @Test
    void test() {
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < THRESHOLD; i++) {
            list.add(randomInt());
        }
        list.sort(null);
        int key = randomInt();
        System.out.println("key : "+ key);
        long start = System.nanoTime();
        int i = CustomCollections.indexedBinarySearch(list, key);
        long end = System.nanoTime();
        System.out.println("location의 위치는 "+i+"이고 그 위치의 값은 "+list.get(i));
        System.out.println("size가 "+THRESHOLD+" 일때 index기반 이분탐색 시간: "+(end-start));

    }

    @Test
    void test2() {
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < THRESHOLD; i++) {
            list.add(randomInt());
        }
        list.sort(null);
        int key = randomInt();
        System.out.println("key : "+ key);
        long start2 = System.nanoTime();
        int i = CustomCollections.iteratorBinarySearch(list, key);
        long end2 = System.nanoTime();
        System.out.println("location의 위치는 "+i+"이고 그 위치의 값은 "+list.get(i));
        System.out.println("size가 "+THRESHOLD+" 일때 iterator기반 이분탐색 시간: "+(end2-start2));


    }


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

}

 

크기가 20000 일 때

저는 무조건 iterator가 더 빠를 줄 알았는데 꼭 그런 것만은 아니였다.

 

크기가 5001일 때

크기가 2,000,000 일 때

크기가 확실히 커질 때에는 iterator의 속도가 더 빠른 것을 볼 수가 있다.

 

그럼 왜 빠른 걸까?(특정 임계시점을 지나면)

 

그럴려면 우선 iterator가 가져오는 속도와 일반 linkedList에서 get 했을 때의 속도를 비교해보자.

 

    @Test
    @DisplayName("iterator의 속도 계산")
    void test3() {
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < THRESHOLD; i++) {
            list.add(randomInt());
        }
        int half = THRESHOLD>>>1;
        int quarter = THRESHOLD>>>2;
        int pivot = half + quarter;
        System.out.println("THRESHOLD = " + THRESHOLD);
        System.out.println("pivot = " + pivot);
        long start = System.nanoTime();
        ListIterator<Integer> i = list.listIterator();
        Integer location = CustomCollections.get(i, pivot);
        long end = System.nanoTime();
        System.out.println("iterator 시간은 "+(end-start));
        System.out.println("위치의 값은 "+location);
    }

    @Test
    @DisplayName("기본 get() 의 속도 계산")
    void test4() {
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < THRESHOLD; i++) {
            list.add(randomInt());
        }
        int half = THRESHOLD>>>1;
        int quarter = THRESHOLD>>>2;
        int pivot = half + quarter;
        System.out.println("THRESHOLD = " + THRESHOLD);
        System.out.println("pivot = " + pivot);
        long start = System.nanoTime();
        Integer location = list.get(pivot);
        long end = System.nanoTime();
        System.out.println("get() 시간은 "+(end-start));
        System.out.println("위치의 값은 "+location);
    }

순수하게 봤을 때에는 get()의 속도가 훨씬 빠른 것을 알 수 있다.

그러면 왜 갯수가 클 때에는 listiterator를 쓸까?

 

그림으로 설명해보겠습니다.

listiterator의 경우에는 해당 기준점으로 뒤로 가거나 앞으로 가면 되는데 get의 경우에는 무조건 처음부터 시작하여 해당 지점까지 가기 때문에 리스트의 길이가 클 경우에는 listiterator를 쓰게 된다. ( 단, 이것은 RandomAccess 인터페이스를 가지고 있지 않은 LinkedList같은 경우에만 해당한다.)

 

결론
RandomAccess을 가지고 있는 ArrayList나 Vector의 경우에는 indexedBinarySearch로 구현되고 LinkedList같은 클래스는 일정 크기까지는 get() 형식으로 움직이는  indexedBinarySearch로 움직이지만 그 이상의 크기가 되는 경우에는 iteratorBinarySearch로 구현됩니다.
그러므로 binarySearch를 할 때에는 RandomAccess를 가지고 있는 클래스로 사용하는 것이 베스트!!