들어가며
Collection 프레임워크를 공부해보다가, 문득 생각이 들었다.
Collection 은 종류는 엄청 다양하고 많지만, 위 인터페이스 별로 성능이 얼마나 차이가 날까?? 라는 궁금증이 생겼다.
누가봐도 Collection 은 배열보다 많이 쓰일 것이고, 안 쓰는 사람이 없을 것이다.
그리고 간단하게 보면 그냥 Collection 은 성능은 둘째 치고, 본인 비즈니스에 맞게 즉 상황에 맞게 사용하는 것이 베스트다.
그래서 어떤 상황에서 어떤 Colleciton 을 써야 성능이 더 좋을까 라는 주제를 가지고 글을 써보았다.
본론
List 는 인터페이스로 위 List 를 구현하는 구현체는 아주 다양하게 존재한다.
위 사진은 List 의 간단한 Hierarchy 로 List 는 순서가 존재해야 하니 SequencedCollection(=순차 컬렉션) 을 상속받고,
Collection 을 상속 받고 최상위에는 Iterable 인터페이스가 있다.
이외에 List 를 구현하는 ArrayList, LinkedList 등이 있습니다.
테스트 방법으로는 Junit 테스트 코드를 작성해서, 직접 시간을 측정하는 방식으로 진행을 했습니다.
(확실한 정확도가 필요하다면 위 방법이 아닌 JMH 툴을 사용하는 것이 좋습니다)
* List 에 더하기 성능 테스트
public class ListTest {
final int LOOP_COUNT = 100000;
final int REPEAT_COUNT = 100;
List<Integer> arrayList;
List<Integer> linkedList;
int result = 0;
@Test
public void addArrayList() {
long totalTime = 0;
arrayList = new ArrayList<Integer>();
for (int i = 0; i < REPEAT_COUNT; i++) {
long start = System.nanoTime();
for (int j = 0; j < LOOP_COUNT; j++) {
arrayList.add(j);
}
long end = System.nanoTime();
totalTime += (end - start);
}
System.out.println("ArrayList_Average time: " + (totalTime / REPEAT_COUNT) + "ns");
}
@Test
public void addLinkedList() {
long totalTime = 0;
linkedList = new LinkedList<Integer>();
for (int i = 0; i < REPEAT_COUNT; i++) {
long start = System.nanoTime();
for (int j = 0; j < LOOP_COUNT; j++) {
linkedList.add(j);
}
long end = System.nanoTime();
totalTime += (end - start);
}
System.out.println("LinkedList_Average time: " + (totalTime / REPEAT_COUNT) + "ns");
}
}
위 테스트 코드를 2중 for 문으로 돌린 이유는 외부 요인에 의한 변동성을 줄이기 위해 사전 작업으로 100번을 실행 시킨 후 모든
작업을 실행하게 하였습니다.
[결과]
ArrayList_Average time: 5231959ns
LinkedList_Average time: 19519331ns
단순 더하기에서는 ArrayList 가 조금 더 나은 성능을 가지고 있는 걸 확인했습니다.
여기서 ns 단위는 나노세컨드로, 1초를 100,000,000 으로 나눈 것을 의미합니다.
일단은 사실 위 성능 차이는 크게 나지 않는다.
* List 에 꺼내기 성능 테스트
public class ListTest {
final int LOOP_COUNT = 1000;
final int REPEAT_COUNT = 100; // 반복 횟수 추가
List<Integer> arrayList;
List<Integer> linkedList;
int result = 0;
@BeforeEach
public void setUp() {
arrayList = new ArrayList<>();
linkedList = new LinkedList<>();
for (int i = 0; i < LOOP_COUNT; i++) {
arrayList.add(i);
linkedList.add(i);
}
}
@Test
void ArrayList_가져오기_테스트() {
long totalTime = 0;
for (int j = 0; j < REPEAT_COUNT; j++) {
long start = System.nanoTime();
for (int i = 0; i < LOOP_COUNT; i++) {
result = arrayList.get(i);
}
long end = System.nanoTime();
totalTime += (end - start);
}
System.out.println("ArrayList_Average time: " + (totalTime / REPEAT_COUNT) + "ns");
}
@Test
void LinkedList_가져오기_테스트() {
long totalTime = 0;
for (int j = 0; j < REPEAT_COUNT; j++) {
long start = System.nanoTime();
for (int i = 0; i < LOOP_COUNT; i++) {
result = linkedList.get(i);
}
long end = System.nanoTime();
totalTime += (end - start);
}
System.out.println("LinkedList_Average time: " + (totalTime / REPEAT_COUNT) + "ns");
}
}
[결과]
ArrayList_Average time: 449954ns
LinkedList_Average time: * ns
위 결과에서 LinkedList 를 * 로 표시한 이유는 10분 이상 결과를 기다렸는데 나오지 않았다..
왜 그런것 일까요??
LinkedList는 데이터를 꺼낼 때 오래 걸리는 이유는 노드를 순차적으로 탐색해야 하기 때문입니다.
인덱스를 사용하여 접근하려면 첫 번째 노드부터 차례로 탐색해야 하므로 O(n) 의 시간이 걸립니다.
반면, ArrayList는 인덱스 기반 배열이므로 O(1) 로 바로 데이터를 가져올 수 있습니다.
위 문제를 해결하기 위해서는 순차적으로 결과를 받오게 peek() 메소드를 사용해야 한다.
* List 삭제 성능 테스트
public class ListTest {
final int LOOP_COUNT = 100000;
final int REPEAT_COUNT = 100; // 반복 횟수 추가
List<Integer> arrayList;
List<Integer> linkedList;
int result = 0;
@BeforeEach
public void setUp() {
arrayList = new ArrayList<>();
linkedList = new LinkedList<>();
for (int i = 0; i < LOOP_COUNT; i++) {
arrayList.add(i);
linkedList.add(i);
}
}
@Test
void remove_ArrayList_First() {
long totalTime = 0;
for (int j = 0; j < REPEAT_COUNT; j++) {
ArrayList<Integer> tempList = new ArrayList<Integer>(arrayList);
long start = System.nanoTime();
for (int i = 0; i < LOOP_COUNT; i++) {
tempList.remove(0);
}
long end = System.nanoTime();
totalTime += (end - start);
}
System.out.println("ArrayList_First_Average time: " + (totalTime / REPEAT_COUNT) + "ns");
}
@Test
void remove_LinkedList_First() {
long totalTime = 0;
for (int j = 0; j < REPEAT_COUNT; j++) {
var tempList = new LinkedList<Integer>(linkedList);
long start = System.nanoTime();
for (int i = 0; i < LOOP_COUNT; i++) {
tempList.remove(0);
}
long end = System.nanoTime();
totalTime += (end - start);
}
System.out.println("LinkedList_First_Average time: " + (totalTime / REPEAT_COUNT) + "ns");
}
@Test
void remove_ArrayList_Last() {
long totalTime = 0;
for (int j = 0; j < REPEAT_COUNT; j++) {
var tempList = new ArrayList<Integer>(arrayList);
long start = System.nanoTime();
for (int i = LOOP_COUNT-1; i >=0 ; i--) {
tempList.remove(i);
}
long end = System.nanoTime();
totalTime += (end - start);
}
System.out.println("ArrayList_Last_Average time: " + (totalTime / REPEAT_COUNT) + "ns");
}
@Test
void remove_LinkedList_Last() {
long totalTime = 0;
for (int j = 0; j < REPEAT_COUNT; j++) {
var tempList = new ArrayList<Integer>(linkedList);
long start = System.nanoTime();
for (int i = 0; i < LOOP_COUNT ; i++) {
tempList.removeLast();
}
long end = System.nanoTime();
totalTime += (end - start);
}
System.out.println("LinkedList_Last_Average time: " + (totalTime / REPEAT_COUNT) + "ns");
}
}
LinkedList_First_Average time: 682585ns
LinkedList_Last_Average time: 543823ns
ArrayList_First_Average time: 732975473ns
ArrayList_Last_Average time: 270460ns
LinkedList 는 맨 처음이랑, 맨 마지막 삭제하는 시간대는 비슷하다.
하지만 ArrayList 에서 첫번째 삭제랑 마지막 삭제는 성능차이가 엄청 나다.
ArrayList 는 삭제 후 배열의 인덱스를 원상태로 맞춰야 하기 때문에, 그 시간이 오래걸린다.
ex) 0번 인덱스 삭제시, 1번 인덱스가 0번이 되어야 하기 때문에 시간이 상대적으로 오래 걸릴 수 밖에 없다.
결론
뭔가 이런 테스트를 해보는데 흥미를 가지게 되는 시간이였다.
내 코드를 주기적으로 테스트 해보는 것도 재미가 있을 것 같다.