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

비딴·2024년 3월 9일
Java
1

작성하는 이유

'가상 면접 사례로 배우는 대규모 시스템 설계 기초' 라는 책을 읽는 중, 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 사용률 상승 문제

다음 포스트

asdasd

0개의 댓글