Java 순차 탐색 vs 랜덤 탐색, 기본형 vs 참조형 시간 비교

비딴·2024년 3월 9일
Java

작성하는 이유

'가상 면접 사례로 배우는 대규모 시스템 설계 기초' 라는 책을 읽는 중, 2장에서 캐시 연산, 메모리 연산, 디스크 연산 등에 대한 이야기가 나옵니다.
개발자는 대략적인 수치를 알아야 하고 이 수치를 이용하여 사고 실험을 할 줄 알아야 한다고 합니다.
저도 곧 개발자니까 이 포스팅에서 캐시와 메모리를 이용해 가설을 세우고 맞는지 검증해보려 합니다.
많은 시간을 투자하고 싶진 않아 격리되고 완벽한 테스트 환경은 아닙니다.
이 점을 감안하고 봐주시면 감사하겠습니다!(가설이나 테스트 코드가 틀리다면 댓글 부탁드립니다)

가설

  • 순차 탐색을 진행하면 캐시의 지역성(Locality) 덕분에 빠른 탐색을 할 것이고, 랜덤 탐색은 캐시의 지역성을 사용하지 못해 더 오랜 시간이 걸릴 것이다.
  • 기본형 배열이 참조형 배열보다 빠를 것이다.(기본형은 메모리에 연속적으로 쌓여 캐시의 지역성을 이용하고, 참조형은 생성되기 때문에 이용하지 못할 것이다)

위 두 가설을 바탕으로 테스트를 만들고 시간을 측정하여 테스트해보겠습니다.

테스트 구성

  • 순차 탐색과 랜덤 탐색을 진행해보겠습니다.
  • int 배열과 Integer배열, Custom 객체 배열을 사용해보겠습니다.(Integer가 참조형이지만 JVM에서 최적화를 해놓았을 것 같아, Custom 객체 배열도 추가하였습니다)

자바 버전은 17을 사용했습니다.
각 탐색은 100번씩 진행하며 배열의 크기는 100_000_000입니다. 큰 의미 없이 충분히 크다고 생각하는 숫자로 잡았습니다.
랜덤 탐색시 Random.nextint() 를 사용합니다. 운이 좋게 몇몇 인덱스들은 순차적으로 진행할 수도 있지만 이는 본 테스트에서 고려하지 않았습니다.

int[] 테스트

순차탐색

public class sequentialSearch {

    private static final int ARRAY_SIZE = 100000000;
    private static final int SEARCH_COUNT = 100;

    public static void main(String[] args) {
        // 배열 생성 및 초기화
        int[] array = new int[ARRAY_SIZE];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }

        int[] indexes = new int[ARRAY_SIZE];
        for (int i = 0; i < indexes.length; i++) {
            indexes[i] = i;
        }

        int[] copy = new int[ARRAY_SIZE];

        // 순차 탐색 시간 측정
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < SEARCH_COUNT; i++) {
            search(array, indexes, copy);
        }
        long endTime = System.currentTimeMillis();
        long durationInMillis = endTime - startTime; // 총 실행 시간을 밀리초로 계산
        System.out.println("Sequential search time: " + durationInMillis + " ms");
    }

    private static void search(int[] array, int[] indexes, int[] copy) {
        for (int i = 0; i < copy.length; i++) {
            copy[i] = array[indexes[i]];
        }
    }
}

랜덤 탐색

public class RandomSearch {

    private static final int ARRAY_SIZE = 100000000;
    private static final int SEARCH_COUNT = 100;

    public static void main(String[] args) {
        // 배열 생성 및 초기화
        int[] array = new int[ARRAY_SIZE];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }

        int[] indexes = new int[ARRAY_SIZE];
        Random random = new Random();
        for (int i = 0; i < indexes.length; i++) {
            indexes[i] = random.nextInt(array.length);
        }

        int[] copy = new int[ARRAY_SIZE];

        // 랜덤 탐색 시간 측정
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < SEARCH_COUNT; i++) {
            search(array, indexes, copy);
        }
        long endTime = System.currentTimeMillis();
        long durationInMillis = endTime - startTime; // 총 실행 시간을 밀리초로 계산
        System.out.println("Random search time: " + durationInMillis + " ms");
    }

    private static void search(int[] array, int[] indexes, int[] copy) {
        for (int i = 0; i < copy.length; i++) {
            copy[i] = array[indexes[i]];
        }
    }
}

int는 랜덤 탐색시 확실히 시간이 오래 걸리는 걸 볼 수 있습니다.

Integer[] 테스트

1개의 값만 참조

Integer[]의 순차 탐색을 진행하기 전에 1개의 값만 참조하여 복사하는 테스트를 먼저 진행해보겠습니다.
이 테스트를 하는 이유는 객체는 원시 타입과 다르게 힙 영역에 만들어지고 참조 주소를 참조하여 값을 가져옵니다.
이 과정에서 시간이 소요될 수도 있기 떄문에 원시 타입과 시간 차이가 날 것입니다.
최대한 캐시의 지역성을 사용하도록 1개의 값만 참조하여도 어느 정도의 시간 차이가 나는지 확인해보겠습니다.
(Integer는 값이 같은 Integer가 존재한다면 재활용됩니다)

public class WrapperClassSequentialSearch {

    private static final int ARRAY_SIZE = 100000000;
    private static final int SEARCH_COUNT = 100;

    public static void main(String[] args) {
        // 배열 생성 및 초기화
        Integer[] array = new Integer[ARRAY_SIZE];
        for (int i = 0; i < array.length; i++) {
            array[i] = 0;
        }

        int[] indexes = new int[ARRAY_SIZE];
        for (int i = 0; i < indexes.length; i++) {
            indexes[i] = 0;
        }

        int[] copy = new int[ARRAY_SIZE];

        // 순차 탐색 시간 측정
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < SEARCH_COUNT; i++) {
            search(array, indexes, copy);
        }
        long endTime = System.currentTimeMillis();
        long durationInMillis = endTime - startTime; // 총 실행 시간을 밀리초로 계산
        System.out.println("WrapperClassSequentialSearch time: " + durationInMillis + " ms");
    }

    private static void search(Integer[] array, int[] indexes, int[] copy) {
        for (int i = 0; i < copy.length; i++) {
            copy[i] = array[indexes[i]];
        }
    }
}

Integer 는 참조 주소를 참조하는 과정에서 약간이 시간이 걸립니다.

순차 탐색

public class WrapperClassSequentialSearch {

    private static final int ARRAY_SIZE = 100000000;
    private static final int SEARCH_COUNT = 100;

    public static void main(String[] args) {
        // 배열 생성 및 초기화
        Integer[] array = new Integer[ARRAY_SIZE];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }

        int[] indexes = new int[ARRAY_SIZE];
        for (int i = 0; i < indexes.length; i++) {
            indexes[i] = i;
        }

        int[] copy = new int[ARRAY_SIZE];

        // 순차 탐색 시간 측정
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < SEARCH_COUNT; i++) {
            search(array, indexes, copy);
        }
        long endTime = System.currentTimeMillis();
        long durationInMillis = endTime - startTime; // 총 실행 시간을 밀리초로 계산
        System.out.println("WrapperClassSequentialSearch time: " + durationInMillis + " ms");
    }

    private static void search(Integer[] array, int[] indexes, int[] copy) {
        for (int i = 0; i < copy.length; i++) {
            copy[i] = array[indexes[i]];
        }
    }
}

랜덤 탐색

public class WrapperClassRandomSearch {

    private static final int ARRAY_SIZE = 100000000;
    private static final int SEARCH_COUNT = 100;

    public static void main(String[] args) {
        // 배열 생성 및 초기화
        Integer[] array = new Integer[ARRAY_SIZE];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }

        int[] indexes = new int[ARRAY_SIZE];
        Random random = new Random();
        for (int i = 0; i < indexes.length / 2; i++) {
            indexes[i] = random.nextInt(array.length);
        }

        int[] copy = new int[ARRAY_SIZE];

        // 랜덤 탐색 시간 측정
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < SEARCH_COUNT; i++) {
            search(array, indexes, copy);
        }
        long endTime = System.currentTimeMillis();
        long durationInMillis = endTime - startTime; // 총 실행 시간을 밀리초로 계산
        System.out.println("WrapperClassRandomSearch time: " + durationInMillis + " ms");
    }

    private static void search(Integer[] array, int[] indexes, int[] copy) {
        for (int i = 0; i < copy.length; i++) {
            copy[i] = array[indexes[i]];
        }
    }
}

CustomClass[]

1개의 객체만 참조

CustomClass도 순차 탐색을 진행하기 전에 1개의 객체만 참조해보겠습니다.

public class CustomClassSequentialSearch {

    private static final int ARRAY_SIZE = 100000000;
    private static final int SEARCH_COUNT = 100;

    public static void main(String[] args) {
        // 배열 생성 및 초기화
        CustomInt[] array = new CustomInt[ARRAY_SIZE];
        for (int i = 0; i < array.length; i++) {
            array[i] = new CustomInt(i);
        }

        int[] indexes = new int[ARRAY_SIZE];
        for (int i = 0; i < indexes.length; i++) {
            indexes[i] = 0;
        }

        int[] copy = new int[ARRAY_SIZE];

        // 순차 탐색 시간 측정
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < SEARCH_COUNT; i++) {
            search(array, indexes, copy);
        }
        long endTime = System.currentTimeMillis();
        long durationInMillis = endTime - startTime; // 총 실행 시간을 밀리초로 계산
        System.out.println("CustomClassSequentialSearch time: " + durationInMillis + " ms");
    }

    private static void search(CustomInt[] array, int[] indexes, int[] copy) {
        for (int i = 0; i < copy.length; i++) {
            copy[i] = array[indexes[i]].value;
        }
    }

    private record CustomInt(int value) {

    }
}

Integer[]가 1개의 객체를 참조할 때보다 시간이 조금 더 걸렸습니다.

순차 탐색

public class CustomClassSequentialSearch {

    private static final int ARRAY_SIZE = 100000000;
    private static final int SEARCH_COUNT = 100;

    public static void main(String[] args) {
        // 배열 생성 및 초기화
        CustomInt[] array = new CustomInt[ARRAY_SIZE];
        for (int i = 0; i < array.length; i++) {
            array[i] = new CustomInt(i);
        }

        int[] indexes = new int[ARRAY_SIZE];
        for (int i = 0; i < indexes.length; i++) {
            indexes[i] = i;
        }

        int[] copy = new int[ARRAY_SIZE];

        // 순차 탐색 시간 측정
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < SEARCH_COUNT; i++) {
            search(array, indexes, copy);
        }
        long endTime = System.currentTimeMillis();
        long durationInMillis = endTime - startTime; // 총 실행 시간을 밀리초로 계산
        System.out.println("CustomClassSequentialSearch time: " + durationInMillis + " ms");
    }

    private static void search(CustomInt[] array, int[] indexes, int[] copy) {
        for (int i = 0; i < copy.length; i++) {
            copy[i] = array[indexes[i]].value;
        }
    }

    private record CustomInt(int value) {

    }
}

랜덤 탐색

public class CustomClassRandomSearch {

    private static final int ARRAY_SIZE = 100000000;
    private static final int SEARCH_COUNT = 100;

    public static void main(String[] args) {
        // 배열 생성 및 초기화
        CustomInt[] array = new CustomInt[ARRAY_SIZE];
        for (int i = 0; i < array.length; i++) {
            array[i] = new CustomInt(i);
        }

        int[] indexes = new int[ARRAY_SIZE];
        Random random = new Random();
        for (int i = 0; i < indexes.length; i++) {
            indexes[i] = random.nextInt(array.length);
        }

        int[] copy = new int[ARRAY_SIZE];

        // 순차 탐색 시간 측정
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < SEARCH_COUNT; i++) {
            search(array, indexes, copy);
        }
        long endTime = System.currentTimeMillis();
        long durationInMillis = endTime - startTime; // 총 실행 시간을 밀리초로 계산
        System.out.println("CustomClassRandomSearch time: " + durationInMillis + " ms");
    }

    private static void search(CustomInt[] array, int[] indexes, int[] copy) {
        for (int i = 0; i < copy.length; i++) {
            copy[i] = array[indexes[i]].value;
        }
    }

    private record CustomInt(int value) {

    }
}

결과

타입순차 탐색랜덤 탐색랜덤 탐색 / 순차 탐색
int[]3727ms52916ms14.198...
Integer[]10970ms160590ms14.639...
CustomInt[]11397ms180715ms15.856...

완벽하게 고립된 환경한 테스는 아니었지만 유의미한 결과를 얻었다고 생각합니다.
각 다른 타입들이 순차 탐색과 랜덤 탐색에서 일정한 배율의 관계를 보였습니다.
또한, 객체는 참조하고 힙 메모리 상에 분산되어 만들어 질 수 있어 성능 저하를 보였습니다.

결론

배열을 사용할 때는 특별한 이유가 없다면 기본형 > 참조형 을 하는 것이 바람직합니다.
배열을 참조하는 순서도 특별한 이유가 없다면 순차 > 랜덤 이 바람직합니다.

profile
비딴
비 온 뒤 딴딴
이전 포스트

EC2 메모리 부족으로 인한 CPU 사용률 상승 문제

다음 포스트

[네이버 부스트캠프 챌린지 10기] 1주차 회고

0개의 댓글