Java ArrayList Class Speed Issue

자바에서 단순히 배열과 관련된 작업을 할 때 많이 쓰이는 Class로 ArrayList<T> 가 있다. 정적인 배열에 비해, 정보를 동적으로 리스트에 추가 할 수 있기 때문에 편리하기때문에 그동안은 별 생각 없이 사용해왔다. C 언어를 배울 때 가장 기초적인 자료구조인 Linked List 의 형태와 유사한 클래스이다. ArrayList 클래스의 간단한 사용법은 아래와 같다.

ArrayList<String> array = new ArrayList<String>();
array.add("data");
array.remove(0);

위의 예제와 같이 ArrayList 는 배열 형태로 데이터를 저장할 때 유용하다. 동적으로 데이터를 추가하고 삭제 할 수 있기 때문에, 안드로이드 등에서 간단한 리스트뷰를 이용할 때 ArrayList 를 많이 사용한다. 하지만 최근 이미지에서 패턴 분석을 하는 작업을 하다가 우연히 ArrayList 의 index 에 따른 삭제 속도가 다르다는 것을 알게되었다.

for(int i=0;i<array.size();i++) {
    // Something Code
    if(isNotCandidate)
        array.remove(i);
}

위의 코드와 같이, 처음에는 C 로 구현했던 링크드리스트를 떠올리며 당연히 index 를 0 번 부터 삭제면서 알고리즘을 진행을 하였는데, List 의 size 가 커질수록 기하급수적으로 수행시간이 오래걸렸던 것이다. 혹시나 해서 마지막 부터 탐색을 하면 속도가 어떨지 테스트 해보니 마지막 인덱스의 삭제를 먼저 수행하면 수행 속도가 빨라졌다.

위의 표는 ArrayList 에서 맨 처음 index 부터 삭제한 것과 마지막 index 부터 삭제한 것을 비교한 차트이다. List 의 size 가 커질 수록 처음 index 부터 삭제한 경우는 시간이 급격이 오래걸리는 것을 알 수 있다.

이러한 원인을 JRE Library 에서 코드를 확인해보니 다음과 같았다.

private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;

JRE Library 에서 ArrayList 의 코드를 보면, 객체간의 링크를 통해 서로 데이터를 연결해 주는 것이 아닌 배열을 이용하여 데이터를 관리한다. 따라서 데이터를 추가하거나 삭제할 때마다 배열의 위치나 크기를 바꾸어 기존의 데이터를 대입하여야한다.

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

삭제와 관련된 코드를 살펴보면 배열을 카피하여 붙여넣는 것을 볼 수 있다. 만약 맨 처음 위치의 배열을 삭제한다면, ArrayList 에 배열의 형태로 저장된 자료를 각각 한칸씩 shift 해주어야 하기때문에 연산 숫자가 늘어나게된다. 따라서 몇 개의 데이터를 삭제할 때는 문제가 없겠지만 다수의 데이터를 비교/삭제해야하는 경우에는 ArrayList 가 적합하지 않을 수도 있다.

ArrayList 가 편리한 도구이기는 하지만 적절하게 이용해야 할 것이다. 이미지 패턴을 분석하면서 처음에는 아무생각없이 ArrayList 를 이용하여 좌표를 관리하고 비교했는데, 이러한 경우에는 비교시 배열을 이용하여 비교하고 해당 좌표에 특정 값을 대입하여 표시해 놓는 것이 더 좋은 방법일 것이다.