[JAVA] 무지성 배열 생성하지 않기.

저번에 옆에 이 문제를 풀다가 https://www.acmicpc.net/problem/16946

 

무지성 배열 생성을 하여 시간초과가 계속해서 생긴 경험이 있어서 글을 작성하게 되었습니다. 

 

배열 생성하는 데 걸리는 시간이 O(1)로 얼고 있었는데 과연 그럴까요? 

 

이를 실험해보기 위해 간단한 코드 2가지를 작성했습니다. 

 

1 매 실행마다 배열을 생성하는 메서드

public static void resetArray(int cnt){
        while(cnt-->0){
            int[] arr = new int[100_000_000];
            arr[cnt] = cnt;
        }
    }
// 1.9587517s

 

2. 배열을 새로 선언하지 않는 메서드

    public static void maintainArray(int[] arr,int cnt){
        while (cnt -->0){
            arr[cnt] = cnt;
        }
    }
// 0.1311488s

 

위 두 코드를 비교해 봤을때, 배열을 생성하는데 대략 O(N)의 시간이 걸립니다. 

 

그 이유는 

https://stackoverflow.com/questions/5640850/java-whats-the-big-o-time-of-declaring-an-array-of-size-n

Java: what's the big-O time of declaring an array of size n?

의 답변을 중 일부를 가져 왔습니다. 

A new array whose components are of type atype and of length count is allocated from the garbage-collected heap. A reference arrayref to this new array object is pushed into the operand stack. 
Each of the elements of the new array is initialized to the default initial value for the type of the array (§2.5.1).

 

즉 배열을 선언할때, 각 메모리에 값을 디폴트 값으로 초기화 함으로 시간 복잡도가 O(n)이 나오는 것 같습니다. 

 

오늘의 결론

 

배열 생성에 신경을 쓰도록 하자. 

 

+ 그렇다면 List는 어떨까요?

 

1. 기본 생성자

    public static void resetList(int cnt){
        while(cnt-->0){
            List<Integer> list = new ArrayList<>();
            list.add(cnt);
        }
    }
 // 0.0001126s

 

2. 초기 공간을 할당 

public static void resetList(int cnt){
    while(cnt-->0){
        List<Integer> list = new ArrayList<>(100_000_000);
        list.add(cnt);
    }
}
// 10.1507521s

 

List 또한 초기 용량이 클수록 시간이 오래 걸립니다.